python - 从列表列表(如计数器)中计算每个组合的最快方法是什么？

Question

我里面有一个包含超过 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.

最慢且不可能的方法是通过从 80 中取 1 生成所有组合，然后从 80 中取 2，然后从 80 中取 3 等等，直到生成 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}

但是几乎只对 80 中的 1 的组合有效。对于其他组合如何做到这一点？以及如何比这种方式更快地做到这一点？

附注我只需要它们共有的组合，我对所有列表中 1 或 0 匹配的组合不感兴趣。因此，也许这可以帮助您加快速度。

Answer 1

您可以使用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 的最有效方法

P.S: powerset 也是 itertools Recipies 的一部分