高效地计算大型Python列表中的项目

Question

我有两个非常大的Python列表，看起来像这样：

List A: [0,0,0,0,0,0,0,1,1,1,1,2,2,3,3,3,4.........]
List B: [0,0,0,0,0,0,2,2,2,2,3,3,4,4.........]

这些列表可能包含非常大的数字，但我会指定一个最大值，比如100，在这之后我可以丢弃剩下的数字。

现在我需要计算每个值（0、1、2.. 100）的比率：列表 A 中出现的次数 / 列表 B 中出现的次数。由于这个值并不总是可行的，我决定只有在每个列表中都有超过 5 次出现该值时才计算此值，如果不符合此条件，则将先前值的出现次数相加，并在满足此条件时为组合值给出相同的比率。 例如对于上述列表，我想创建一个类似于以下内容的系列：

0 : 7/6=1.166 
1 : 9/6 = 1.5
2 : 9/6 = 1.5
3 : 9/6 = 1.5
.
.
.
100 : some_number

- Triple Nipple

---

列表A中“0”的数量为7，列表B中“0”的数量为6。7/6 = 1.166。 - Triple Nipple

为什么1 1: 9/6 = 1.5 而不是 1: 4/0 = ...？ - Nick stands with Ukraine

如果你有两个列表，那么我认为无论如何都必须至少查看列表中的每个元素一次。因此，具有N个元素的2个列表意味着您正在查看2N运行时间。只需循环遍历您的列表即可。 - bassxzero

回答 Nick A：因为如上所述，只有在每个列表中该值出现超过5次时才应计算比率。数字1只在列表A中出现了4次，并且从未出现在列表B中，因此它应与下一个值2合并。即使将这两个值合并起来也无法满足要求，因此还需合并数值3，然后1 + 2 + 3的出现次数在列表A中为9，在列表B中为6-因此计算出的比率为9/6 = 1.5。 - Triple Nipple

这些列表已经排序了吗？如果是的话，使用二分查找方法来找到每个步骤可能是可行的。 - Eric Duminil

Answer 1

你可以使用 Counter 来计算出现次数，使用 takewhile 以满足在 100 停止的要求。

与其丢弃不在列表 b 中的值，注意我是如何使用 nan 的。

from collections import Counter
from itertools import takewhile

def get_ratios(a, b, max_=None, min_count=0):
    if max_ is not None:
        a = takewhile(lambda x: x <= max_, a)
        b = takewhile(lambda x: x <= max_, b)

    count_a, count_b = Counter(a), Counter(b)

    return {k: float('nan') if not count_b[k] else count_a[k] / count_b[k]
            for k in set(count_a) | set(count_b)
            if count_a[k] >= min_count <= count_b[k]}

示例

a = [1, 1, 1, 2, 3, 101]
b = [1, 1, 2, 2, 4, 101]

print(get_ratios(a, b, max_=100))

输出

{ 1: 1.5,
  2: 0.5,
  3: nan,
  4: 0.0 }

忽略一些不常见的值，可以将min_count设置为5，如您在问题中提到的。

请注意，我没有用前一个值的比率填充空槽。除非您有非常特定的用例需要它，否则我建议您不要这样做，因为这会混合实际数据和推算数据。最好在找不到前一个值时默认使用前一个值，但不要污染实际数据。

- Olivier Melançon