Python: 有效地扩展具有定义列表的计数器键并刷新

Question

我正在扩展带有替换的独特组合及其频率的列表，虽然我已经看到使用 itertools 的更优雅的解决方案，但这些方法不够快，或者当组合变得庞大时需要太多内存。下面，我采用了自下而上的方法，显着减少了列表中的元素。

这里的答案是一个很好的方法，但是当迭代器太大时，减少唯一性变得笨拙：

例如，对于 5 个对象和 15 个样本，itertools 将创建 300 亿个组合，但只有 3,876 ( Cr(5,15) ) 个独特组合。在下一轮中，下面将构建 3,876*5 个新组合并拉取之前的计数以创建 Cr(5,16)。这比从 300 亿次迭代中缩减要快得多。

但是，我觉得我的代码根本没有效率，它开始花费大量时间比我预期的要早得多（如果说唯一性，总共 50k）在 Cr(5,30) .那时的迭代器将是 9e+20 组合，而不是从上一轮的 45k 唯一值构建。

以下是我用来暴力破解的内容；有没有一种方法可以通过相同的新选择（例如 0:5）、排序、重新计数来有效地扩展每个 Counter 键？下面的循环将输入一个种子计数器，其中包含我从之前的运行.

中保存的一组初始元组和计数

round_list = previously_loaded_counter
start_time = time.time()
#expanding build
for i in range(round_count - 1):  ## Number of rounds added
    loop_time = time.time()
    print(f"Round: {i + 1}")
    round_list.append(collections.Counter())
    for item, count in round_list[i].items():  ## e.g., item = (1, 1), count = 1
        for choice in range(choice_count):
            next_item = item + (choice,)  ## new tuple, (1, 1, 0)
            next_item_sorted = tuple(sorted(next_item))  ## clearly could combine with above, (0, 1, 1)
            round_list[i + 1] += collections.Counter({next_item_sorted: count})  ## fill counter with new tuple, use previous iterations count as seed
    print(f"Loop time: {round(time.time() - loop_time, 2)} seconds")
    print(f"Record count: {len(round_list[i+1])}")

输出要点（其中 (0,1) 和 (1,0) 不是唯一的）：

Counter({(0, 0): 1, (0, 1): 2, (1, 1): 1)})

并输出：

Counter({(0, 0, 0): 1, (0, 0, 1): 3, (0, 1, 1): 3, (1, 1, 1): 1)})

如您所见，它只是为每个添加 0，然后为每个添加 1，然后重新组合它们。

如有任何想法，我们将不胜感激！一切正常，我只是觉得我添加了很多不必要的循环...

Answer 1

我设法想出了一个相当有效的解决方案，运行速度相当快

choices = (0, 1, 2, 3, 4)
repeat = 40
counter = Counter()
counter.update({(x, ): 1 for x in choices})

for i in range(1, repeat):
    new_counter = Counter()
    for sorted_combination, previous_count in (
        (tuple(sorted(k + (choice, ))),  v)
        for k, v in counter.items()
        for choice in choices
    ):
        new_counter[sorted_combination] += previous_count
    counter = new_counter

print(counter.most_common(10))

Python: 有效地扩展具有定义列表的计数器键并刷新

Python: Efficiently expand Counter keys with defined list and refresh

python

counter

dictionary

probability