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

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

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

Логическое решение, казалось бы, было бы просто реализовать itertools.combinations() локально. Основываясь на «эквивалентной» реализации python itertools.combinations() в документах python, время примерно в два раза медленнее, потому что itertools.combinations вызывает реализацию уровня C, а не родную python.

Вопрос (наконец) заключается в том, как я могу передать результаты itertools.combinations() один за другим, чтобы я мог проверять объединения множеств, пока я продолжаю работать в почти эквивалентное время, как реализация python of itertools.combinations(). В ответ я был бы признателен, если бы вы могли включить результаты вашего нового метода, чтобы доказать, что он работает в то же время, что и реализация на основе 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()

источник

2016-11-22 jaykk128

Просто перебирайте его ... –

Другими словами, itertools.combinations делает * not * возвращать все возможные комбинации, он возвращает генератор, который * предназначен для создания всех возможных комбинаций один за другим *. –

Вам повезло ... 'itertools.combinations' уже делает именно то, что вы хотите! – kindall

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

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

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

источник

2016-11-22 22:54:52 Prune

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

ответ

Смежные вопросы