0

无法有效地反转（交换键的值和值的键）存储在文件中的大型（2.8GB）字典。效率是问题，我目前的解决方案是：

  • 逐行读取字典文件（格式：,,,...）

    对于每一行：

    • 运行上一次传递的正在进行的输出文件，将其逐行复制到临时文件中
    • 在适当的地方（按字母顺序）将字典值 (val1,val2,...) 插入到临时文件中，每个新值都是一个新键
    • 用临时文件覆盖之前的 pass 输出文件
    • 重复直到处理完所有字典行（以格式结束：:,,,.. :,,.. :,,,..）

该算法非常笨拙，至少输出文件必须被写入 n^2 次（我认为...），其中 n 约为 30,000,000。缺乏可用内存会阻止整个读取它并在内存中处理它。

可能没有比让它继续下去更好的解决方案了，但如果有人有任何想法，我们将不胜感激。

编辑：应该明确最终输出的每一行都可以包含多个键作为值。

4

2 回答 2

4

我建议以下 3 次通过解决方案：

  1. 迭代您的原始字典文件一次，为每个 val 的输出文件添加一个 val 键行。

  2. 使用 unix sort 命令或其他一些快速排序程序对步骤 1 中的输出文件进行排序。

  3. 如果有可能第 1 步产生了需要删除的重复项，请从第 2 步迭代输出文件并在编写最终输出文件时删除重复项。由于 2 的输出文件已排序，因此您只需要一次传递和最少的内存即可执行此操作。

于 2013-06-24T22:30:29.997 回答
1

我不确定我是否理解您的问题，所以让我通过示例描述我认为您想要的内容，然后展示如何去做。

您的输入是一个文本 CSV 文件，如下所示：

a,1,2,3
b,4,5,6
c,7,8,9

每行是一个键，后面是一组值。它表示一个字典，其中每个值都是一个元组——例如，d['a'] = (1,2,3).

输出应该是这样的 CSV 文件：

1,a
2,a
3,a
4,b
5,b
6,b
7,c
8,c
9,c

......但在一些任意的行顺序。原始文件中的每个值都映射到其所在行中第 0 列的键。（如果值重复，则任意选择一个键。）

所以，如果你在内存中做这一切，它看起来像这样：

in_dict = {'a': (1, 2, 3), 'b': (4, 5, 6), 'c': (7, 8, 9)}
out_dict = {value: key for key, value_set in in_dict.items() for value in value_set}

唯一的问题是，这可能需要大约 5.2GB 的 RAM 来处理 2.6GB 的字典，因此您已经将 in_dict 以您的特殊形式存储在磁盘上，并希望以类似的形式将 out_dict 写入磁盘，而无需将所有内容都读入内存。

最简单的方法是使用 DBM 进行中间存储。将 CSV 读取到 DBM 中，然后其结构与上述完全相同out_dict；只是写起来有点复杂。

显然，您将希望使用该csv模块来读取（和写入）CSV，以及用于 DBM的dbm（或者，对于 Python 2.x， ）模块。anydbm

with contextlib.closing(dbm.open('kv.dbm', 'n')) as db:
    with open('kv.csv') as f:
        for row in csv.reader(f):
            for col in row[1:]:
                db[col] = row[0]

然后将该 DBM 写入您的首选格式。如果dbm对象有一个items方法，那就是：

    with open('kvt.csv', 'w') as f:
        csv.writer(f).writerows(dbm.items())

由于它们没有，您可以添加一个，或编写一个 genexp：

        csv.writer(f).writerows((key, db[key]) for key in db.keys())

或显式迭代：

        w = csv.writer(f)
        for key in db.keys():
            w.writerow((key, db[key])

您可能还想使用tempfile使 DBM 成为一个临时文件，在您完成后自动清理它。由于 Windows 和 *nix 以及 Python 版本之间的细节略有不同，我将把这部分作为练习留给读者。

于 2013-06-24T22:56:11.167 回答