itertools.ifilter с IPython Parallel

Question

Для некоторых проблем [доказано, что NP трудно] У меня нет другого выбора, кроме исчерпывающего поиска. У меня есть набор данных - для простоты, S = ['A', 'B', 'C', ... ,'Z'] и хочу применить функцию f ко всем подмножествам длины N < len(S) этого набора. Я не могу использовать списки здесь, поскольку биномиальные коэффициенты binom(len(S),N) - это несколько миллиардов. Но результат f(x), x∈S равен нулю для почти все значения S. Поэтому в простых случаях все прекрасно работает с

from itertools import ifilter, combinations 
    answer = list(ifilter(lambda x: f(x) > 0, combinations(S,N))) 

Но в реальной жизни, len(S) ~ 10⁴ и N ~ 10². Я хочу распространять работу среди процессоров ЦП с использованием ipyparallel. У меня небольшой кластер с сотней процессорных ядер. Но я все еще не могу позволить себе хранить комбинации в виде списков, поэтому мне нужно что-то вроде отдельных генераторов.

Есть целый coupleexamples из того, как разделить генератор на куски, но, насколько я понимаю, они все еще последовательные генераторов. Существует также idea @minrk, что связано, но по какой-то причине оно действительно очень плохое.

Так вопросы:

• есть ли способ реализовать itertools.ifilter непосредственно ipyparallel? или
• возможно отделить генератор питона в набор независимых генераторов (направить их в ipcluster двигателей самостоятельно)?

Answer 1

Исчерпывающий поиск здесь совершенно безнадежен, независимо от того, как вы его распараллеливаете. С len(S) и N на таком высоком уровне вам нужно будет найти около 6e241 кандидатов. Это намного превосходит возможности любой вычислительной системы, которую человечество может когда-либо надеяться построить.

Вам понадобится использовать более разумный алгоритм.