3

我有两个文本文件，都包含大约 700,000 行。

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

我需要计算匹配行上出现的每个单词对的 Fisher 精确分数。

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

how are you

和

fine thanx

然后我需要计算 (how,fine), (how,thanx), (are,fine), (are,thanx), (you,fine), (you,thanx) 的 Fisher 分数。

为了计算 Fisher 的精确分数，我使用集合模块的计数器来计算每个单词的出现次数，以及它们在两个文件中的共同出现次数，如

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 个条目。）

完成文件中所有单词对的计算需要数十天的时间。

什么是聪明的解决方法？

非常感谢您的帮助。

4

3 回答 3

4

你究竟是如何调用该calculateFisher函数的？你counts_pair不会有7000 万个条目：很多单词对会出现不止一次，所以 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函数；我希望你能明白。因此，如果字典查找是让您放慢速度的原因，这将为您节省很多。如果没有，……做一些分析，让我们知道到底发生了什么。

但请注意，简单地在一个巨大的字典中查找键不应该太慢。但是，如果您的程序必须将其大部分数据交换到磁盘，“快速检索值”将很困难。您的计算机中是否有足够的内存来同时容纳三个计数器？第一个循环是否在合理的时间内完成？因此，找到瓶颈，您将更多地了解需要解决的问题。

编辑：从您的评论看来，您在文本处理的后续步骤中一遍又一遍地计算费舍尔的准确分数。为什么要这样做？分两步分解你的程序：首先，按照我的描述计算所有单词对分数。在计算时将每一对写入并计分到一个文件中。完成后，使用单独的脚本将它们读回（现在内存中只包含这本大字典和费舍尔的精确分数），然后重写。无论如何你都应该这样做：如果你只需要十天才能获得分数（而且你*仍然没有向我们提供任何关于什么是缓慢的细节，以及为什么），开始吧，在十天内你将永远拥有它们，随时使用。

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

于 2013-10-28T00:35:02.437 回答
3

听起来您需要懒惰地生成交叉产品 -Counter具有 7000 万个元素的 a 将占用大量 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”字映射到它自己的Counter：

最初的：

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)

在 Fisher 函数中：

    st = word_to_counter[s][t]
于 2013-10-23T21:34:13.427 回答
3

我认为您的瓶颈在于您如何操作计数器以外的数据结构。

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)

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

于 2013-10-23T21:09:04.217 回答