Какой самый быстрый способ подсчитать каждую комбинацию из списка списков, например, Counter? - PullRequest
Новая
       3

Какой самый быстрый способ подсчитать каждую комбинацию из списка списков, например, Counter?

2 голосов
/ 21 февраля 2020

У меня есть огромный список из более чем 200 000 списков внутри. Например: 

huge_list = [
    [23, 18, 19, 36, 42],
    [22, 18, 19, 36, 39],
    [21, 18, 19, 37, 42]
]

Имеет следующие свойства:

  1. каждое число в каждом списке уникально;
  2. каждый список имеет отсортированные номера; // в данном случае это не так, ПРОСТО для примера.
  3. каждое число из каждого списка является случайным значением от 1 до 80;
  4. каждый список имеет предопределенный размер 20 элементов. Не меньше, не больше.
  5. числа не всегда находятся в одной и той же позиции в списке. это может быть [1,2,3] или [1, 3, 5], но имеют общие 1, 3 и (1,3).

Я хочу, чтобы результат был сколько раз каждую комбинацию можно найти во всех списках: 

 18:3(times),
 19:3(times), 
 36:2(times), 
(18,42):2(times), 
(19,42):2(times), 
(18, 36):2(times), 
(19, 36):2(times), 
(18,19):2(times), 
(18,19,36):2(times), 
(18, 19, 42):2(times) etc.

Самый медленный и невозможный способ - сгенерировать все комбинации по 1, взятой из 80, затем по 2, взятой из 80, затем по 3, взятой из 80 и т. д. до комбинации на 20, взятой на 80, что является почти бесконечным числом. Это невозможно сделать, но также невозможно из-за того, что число списков в огромный_листике превышает 200 000.

Мне нужно что-то вроде счетчика, но быстрее. Как можно быстрее, пожалуйста, потому что это станет намного медленнее, начиная с комбо из 12, взятых 80 или даже меньше.

Это то, что я пытался сделать до сих пор: 

mydict = {}
while len(huge_list) > 1:
    to_check = huge_list[0]
    del huge_list[0]
    for draw in huge_list:
        for num in to_check:
            # one:
            if num in draw:
                if num in mydict:
                    mydict[num] += 1
                else:
                    mydict[num] = 1
    if 1 in mydict.values():
        for key in mydict.keys():
            if mydict[key] == 1:
                mydict[key] += 1

print mydict

Результат : 

{18: 3, 19: 3, 36: 2, 42: 2}

Но почти работает только для комбинаций 1, взятых из 80. Как это сделать для других комбинаций? И как сделать это быстрее, чем этот путь?

PS Мне нужна только общая комбинация, меня не интересуют комбинации с 1 или 0 совпадением во всех списках. Так что, может быть, это поможет вам в скорости, чтобы быть еще быстрее.

1 Ответ

2 голосов
/ 21 февраля 2020

Вы можете использовать алгоритм powerset, найденный в more_itertools, и поместить их в collections.Counter

from more_itertools import powerset
from collections import Counter
from itertools import chain

huge_list = [
    [23, 18, 19, 36, 42],
    [22, 18, 19, 36, 39],
    [21, 18, 19, 37, 42]
]

c = Counter(chain.from_iterable(map(powerset, huge_list)))

print({k if len(k) > 1 else k[0]: v for k, v in c.items() if v > 1 and k})

Результаты 

{18: 3, 19: 3, 36: 2, 42: 2, (18, 19): 3, (18, 36): 2, (18, 42): 2, (19, 36): 2, (19, 42): 2, (18, 19, 36): 2, (18, 19, 42): 2}

Вероятно, это можно ускорить, используя pandas, хотя это кажется наиболее эффективным способом сделать это без pandas

PS: powerset также часть itertools Recipies

...