Оптимизация результатов Itertools в Python

Question

Я называю itertools в Python (см. Ниже). В этом коде snp_dic это словарь с целочисленными ключами и набором значений. Цель здесь - найти минимальный список ключей, объединение значений которых представляет собой комбинацию объединений множеств, эквивалентную set_union, (Это эквивалентно решению для глобального оптимума для популярного набора задач теории теории NP-сложных графов для тех, кто вас заинтересовал)! Алгоритм ниже работает, но цель здесь - оптимизация.

Самая очевидная оптимизация, которую я вижу, связана с itertools. Скажем, для длины r в snp_dic существует комбинация из r наборов, у которых union = set_union. Базовая вероятность диктует, что, если эта комбинация существует и распределена где-то равномерно случайным образом по комбинациям, ожидается, что в среднем потребуется только итерация по этим комбинациям, чтобы найти эту комбинацию покрытия наборов. Однако Itertools возвращает все возможные комбинации, что занимает вдвое больше ожидаемого времени проверки set_unions путем проверки на каждой итерации.

Казалось бы, логичным решением было бы просто реализовать itertools.combination () локально. Однако на основе "эквивалентной" реализации на python функции itertools.combination () в документации по python время примерно вдвое медленнее, поскольку itertools.combination вызывает реализацию уровня C, а не нативную для Python.

Вопрос (наконец-то) заключается в том, как я могу передавать результаты itertools.combination () один за другим, чтобы я мог проверять наборы союзов, когда я иду вперед, так что он все еще работает почти в то же время, что и реализация на python itertools.combination. (). В ответ я был бы признателен, если бы вы включили результаты синхронизации вашего нового метода, чтобы доказать, что он работает в то же время, что и нативная реализация Python. Любые другие оптимизации также приветствуются.

def min_informative_helper(snp_dic, min, set_union):
    union = lambda set_iterable : reduce(lambda a,b: a|b, set_iterable) #takes the union of sets
    for i in range(min, len(snp_dic)):
       combinations = itertools.combinations(snp_dic, i)
       combinations = [{i:snp_dic[i] for i in combination} for combination in combinations]
       for combination in combinations:
           comb_union = union(combination.values())
           if(comb_union == set_union):
           return combination.keys()

Answer 1

itertools предоставляет генераторы для вещей, которые он возвращает. Для потоковой передачи их просто используйте

for combo in itertools.combinations(snp_dic, i):
    ... remainder of your logic

Модуль комбинаций возвращает один новый элемент каждый раз, когда вы получаете к нему доступ: по одному на каждую итерацию цикла.