2

假设我们有一个包含员工姓名和年龄列的 csv 文件（>5GB）。该文件按年龄排序。现在，我希望用户使用 Age 搜索这个文件。有人可以指导我哪种数据结构最适合此要求吗？

示例：

我的文件.csv

25 ABC    
25 MNP
14 XYZ
14 PQR

输入：

14

输出：

XYZ
PQR
4

2 回答 2

4

假设文件太大而无法放入 RAM，您可以创建一个索引，这样您就可以最大限度地减少磁盘读取次数（这比 RAM 读取慢得多）。

一些常用的磁盘索引是B+ 树（顶层存储在 RAM 中）和哈希表。

或者，您可以将其存储为SQL表并让库自行处理。

另一种选择，由于范围相当小（我无法想象年龄大于 200），您可以使用 200 个（或可能更少）不同的文件：names_1,names_2,...,names_200wherenames_i包含所有年龄的名称列表i。
（此外，由于在许多条目中都省略了年龄这种方式，您也许可以将它实际放入 RAM 作为 a dictionary:age->list<names>）

如果数据适合 RAM - 您可以使用排序数组（如果不经常/不期望数据更改）并使用二进制搜索。
如果您需要对数据进行更改，您可以使用其他一些结构，例如 RAM 上的哈希表，或自平衡 BST

于 2012-10-13T17:43:56.437 回答
1

您还没有说明您的基础设施是否允许使用内存解决方案。如果是这样，看到你已经用 python 标记了你的问题，我会考虑将文件的内容读入 defaultdict。如果性能可以接受，您有一个基于标准库的快速解决方案

>>> from collections import defaultdict
>>> z = defaultdict(list)
>>> z[25].append("ABC")
>>> z[25].append("MNP")
>>> print z[25]
['ABC', 'MNP']
于 2012-10-13T18:07:30.890 回答