Python集合计数器用于大数据

Question

我有两个文本文件，每个文件大约有70万行。

第二个文件包含对应行的第一个文件中语句的响应。

我需要计算在匹配行中出现的每个词对的Fisher精确得分。

例如，如果文件中的第n行是

how are you

并且

fine thanx

接下来我需要为(how,fine), (how,thanx), (are,fine), (are,thanx), (you,fine), (you,thanx)计算Fisher的分数。

为了计算Fisher的精确分数，我使用了collections模块的Counter方法，统计了每个单词出现的次数以及它们在两个文件中的共同出现情况，如下所示：

with open("finalsrc.txt") as f1, open("finaltgt.txt") as f2:
    for line1, line2 in itertools.izip(f1, f2):
        words1 = list(set(list(find_words(line1))))
        words2 = list(set(list(find_words(line2))))
        counts1.update(words1)
        counts2.update(words2)
        counts_pair.update(list(set(list(itertools.product(words1, words2)))))

然后我使用scipy模块计算每对数据的Fisher精确分数

from scipy import stats
def calculateFisher(s, t):
    sa = counts1[s]
    ta = counts2[t]
    st = counts_pair[s, t]
    snt = sa - st
    nst = ta - st
    nsnt = n - sa - ta + st
    oddsratio, pvalue = stats.fisher_exact([[st, snt], [nst, nsnt]])
    return pvalue

这对于小型文本文件而言是快速而有效的，但由于我的文件每个都包含700,000行，因此我认为计数器会变得过大，以至于无法快速检索值，从而导致速度变得非常缓慢。 （假设每个句子有10个单词，则counts_pair将具有（10^2）* 700,000 = 70,000,000个条目。）

这需要数十天的时间才能完成文件中所有单词对的计算。您有什么明智的解决方案吗？

非常感谢您的帮助。

- ytrewq

---

每个句子有10个单词，每个句对有100个单词对。在70万个句对中，这样就有7000万个单词对，而不是700000的平方等于490亿。我的理解是否正确？如果是，那我刚刚帮你省了很多工作;-) - Tim Peters

顺便说一下，我认为 list(set(list(... 可以简化为 list(set(...。 - Erik Kaplun

@TimPeters 謝謝，那是我非常愚蠢的錯誤。但問題仍然存在... - ytrewq

find_words() 返回什么？ - martineau

我认为“思考”没有多大意义，因为你可以知道。运行分析器cProfile。检查在Counter.__getitem__中花费了多少时间（如果它们不同，则需要cumtime而不是tottime）。检查随着行数的增加，所花费的时间比例是否增加。如果是这样，那么计数器变慢了。如果不是，那么就没有变慢。 - Steve Jessop

Answer 1

您是如何调用calculateFisher函数的？您的counts_pair不会有7000万个条目：很多单词对会被看到超过一次，因此七千万是它们计数的总和，而不是键的数量。您应该只计算确实共现的成对的精确测试，并且最好的地方就在counts_pair中找到这些内容。但这意味着您可以遍历它；如果这样做，您永远不必在counts_pair中查找任何内容。

for (s, t), count in counts_pair.iteritems():
    sa = counts1[s]
    ta = counts2[t]
    st = count
    # Continue with Fisher's exact calculation

我已经将calculate_fisher函数拆分出来以提高代码清晰度；如果字典查找是导致程序运行缓慢的原因，这样做可以大大减少字典查找次数。但是，如果不是字典查找导致的问题，您需要进行一些性能分析并让我们知道实际情况。

请注意，仅在一个庞大的字典中查找键不应该导致太多的速度下降。然而，如果您的程序必须将大部分数据交换到磁盘上，则“快速检索值”将变得困难。您的计算机是否有足够的内存来同时保存三个计数器？第一个循环是否在合理的时间内完成？因此，找到瓶颈就能更好地了解需要修复的问题。

从您的评论中听起来，您正在文本处理的后续步骤中反复计算Fisher精确度评分。为什么要这样做呢？将程序分为两个步骤：首先按照我描述的方式计算所有单词对的分数。在计算时，将每个单词对和分数写入文件。完成后，使用单独的脚本将它们读回来（现在内存中除了这个包含单词对和Fisher精确度评分的大字典之外没有其他数据），然后进行重写。您应该这样做：如果您需要花费十天时间才能得到分数（而且您仍然没有告诉我们哪里慢，为什么慢），那么开始吧，在十天后，您将永远拥有这些分数，可以随时使用。

我进行了一个快速实验，使用一个包含一百万个((word, word), count)元组的Python进程只需要300MB的内存（在OS X上，但是在Windows上数据结构的大小应该差不多）。如果您有1000万个不同的单词对，那么您可以预计它将占用大约2.5GB的RAM。我怀疑您甚至没有这么多单词对（但是请检查！）。因此，如果您有4GB的RAM，并且没有做任何您没有告诉我们的错误操作，那么您应该没问题。否则，结果可能会有所不同。

- alexis

---

这听起来像是你在反复计算相同的单词对的分数。按照编辑后的答案描述，将其分为两个步骤完成。 （并找出程序花费了多少时间以及是否由于交换而导致） - alexis

非常感谢。我目前正在尝试你的方法，但这很尴尬需要问一下，你提供的for循环代码给了我一个ValueError: 需要多于2个值才能拆包... 这可能是一个非常愚蠢的问题，但我无法找出问题所在。 - ytrewq

哎呀，我不小心压缩了元组解包。请尝试使用上面的新循环。问题在于(s,t)是计数器的键，并且在迭代时以元组的形式出现。 - alexis

非常感谢您的回复。根据您的说法，counts_pair中的条目数显然是73,375,087，大约应该是18GB。我最初尝试将它们存储在Python字典中，但很明显内存不足，然后尝试了SQLite，但随着大小增长，插入速度呈指数级下降。如果我要写入文件并在需要时检索值，最有效的方法是什么？我意识到自己在算法方面的无知。 :( - ytrewq

尝试设置一个真正的数据库（mysql）。但这比预期的词对要多得多：如果你的句子每个大约有10个单词，只有在没有重复的单词对的情况下才能得到这么多的单词对-这怎么可能呢？不知何故，你的代码与你在这里给出的描述不符。 - alexis

Answer 2

我认为你的瓶颈在于除了计数器之外的数据结构如何操作。 words1 = list(set(list(find_words(line1))))会从find_words的结果中创建一个列表，然后再从这个列表中创建一个集合。每个操作都需要分配内存来保存所有对象，并进行复制。更糟糕的是，如果find_words返回的类型不包括__len__方法，则迭代时生成的列表将不断增长并被重新复制。

我假设你只需要一个可迭代的唯一单词集合来更新计数器，对此使用set就足够了。

for line1, line2 in itertools.izip(f1, f2):
    words1 = set(find_words(line1)) # words1 now has list of unique words from line1
    words2 = set(find_words(line2)) # words2 now has list of unique words from line2
    counts1.update(words1)          # counts1 increments words from line1 (once per word)
    counts2.update(words2)          # counts2 increments words from line2 (once per word)
    counts_pair.update(itertools.product(words1, words2)

请注意，您无需更改传递给counts_pair的itertools.product的输出，因为words1或words2中没有重复的元素，因此笛卡尔积不会有任何重复的元素。

- John Spong

---

谢谢回复，但这似乎并没有显著提高速度...还有其他的改进方法吗？ - ytrewq

Answer 3

听起来你需要惰性地生成交叉产品 - 拥有 7000 万个元素的计数器将占用大量 RAM，并在几乎每次访问时遭受缓存未命中的问题。那么，如何保存一个将“文件 1”单词映射到相应“文件 2”单词集合列表的字典呢？

word_to_sets = collections.defaultdict(list)

替换：

   counts_pair.update(list(set(list(itertools.product(words1, words2)))))

使用：

   for w1 in words1:
       word_to_sets[w1].append(words2)

在您的 Fisher 函数中，将其替换为以下内容：

st = counts_pair[s, t]

使用：

    st = sum(t in w2set for w2set in word_to_sets.get(s, []))

这就是我能做到的最懒的方式——根本不需要计算叉积 ;-)

编辑 或者将“列表1”中的一个单词映射到它自己的计数器中：

初始：

word_to_counter = collections.defaultdict(collections.Counter)

替换：

   counts_pair.update(list(set(list(itertools.product(words1, words2)))))

使用：

   for w1 in words1:
       word_to_counter[w1].update(words2)

在费舍尔函数中：

    st = word_to_counter[s][t]

- Tim Peters

---

这似乎快了一点，但并不是非常明显...问题可能在scipy方面吗？ - ytrewq

@CosmicRabbitMediaInc，好吧，我无法从这里进行分析；-) 请查看编辑部分以了解相关方法，该方法在Python端执行的工作较少。 - Tim Peters

@CosmicRabbitMediaInc，费舍尔精确检验统计量的计算成本很低，因此怀疑（但不确定）scipy有问题是不合适的。您有大量数据！无论您做什么，都需要一些时间。 - Tim Peters