logo标签列表

哪种数据结构适合从文本文件中读取和存储约500万条记录？

c#data-structurestext-files
3

我需要处理两个文本文件，每个文件大约1GB，并比较这些文件中的数据。我应该使用哪种数据结构来存储这些数据？使用字典/哈希表比较如此庞大的记录会导致内存不足异常。或者我应该将数据读取并存储在数据库中吗？

这些文件的格式是什么？逗号分隔值，每行一个记录？您想执行什么类型的比较？记录是否已经排序或者可以进行排序？ - Giorgio
1
你还没有告诉我们你需要用这些数据做什么。这实际上决定了答案... - Jon Skeet
文件中的记录都在一行中，没有任何分隔符。我已经根据正则表达式将记录分开（一个记录是字母数字）。然后我必须检查一个文件中是否存在的记录是否存在于第二个文件中。 - Monica
有没有一种方法可以对记录进行排序？也许你可以按字母顺序逐行进行排序。 - Giorgio
在文件本身中进行排序是不可能的，因为我只有一个连续的数据块（约10^9个字母和数字），必须从中提取记录。要对它们进行排序，我必须将它们提取并复制到主存储器中。 - Monica
不需要将所有数据复制到主内存以对其进行排序，这正是归并排序的一个优点！ - Giorgio
4个回答
2

从根本上说，对于这种类型的行为最好使用数据库，它们旨在处理如此多的数据，并且已经进行了更多的优化工作，以优化该方案中可能遇到的情况。

您也可以使用InProcess SQL（例如SqlLite）或NoSql场景（例如Raven或MongoDB）作为替代方案。

@russ 这有点取决于“比较”操作。 - H H
2
.NET Framework 4提供了内存映射文件功能（呵呵，旧好的Win32 API提供该功能已有多年），您可以将文件的不同部分映射到单独的段中并同时处理它们。
要使用内存映射文件，必须创建整个内存映射文件或其中一部分的视图。您还可以创建多个视图到同一内存映射文件的部分，从而创建并发内存。为了使两个视图保持并发，它们必须从同一内存映射文件创建。
如果文件大于应用程序可用于内存映射的逻辑内存空间的大小（在32位计算机上为2 GB），则可能需要多个视图。
0

这是使用数据库的一个典型示例。根据您的结构，需要编写脚本来定义其布局以将值添加到数据库中。

0

如果您可以按记录中某个属性进行排序，并且该属性也用于比较，那么您可以使用归并排序对文件进行排序，然后并行扫描它们，无需将整个数据存储在主内存中。

如果您使用两个嵌套循环，则检查第一个文件中的记录是否也存在于第二个文件中的复杂度为O(n^2)。但是，如果文件已排序，则可以使用单个循环。此外，归并排序的复杂度为O(n log n)。总体复杂度为O(n log n)，优于O(n^2)。这里是C#中归并排序的实现。

我认为，如果记录被索引，您可以使用数据库来实现相同的结果（以速度为准）。

我面临的问题是由于n太大。在进行O(n log n)次比较时，将所有数据复制到主内存中会导致内存溢出异常。 - Monica
使用归并排序时，您无需复制主存中的所有数据。当数据排序完成后，您无需读取整个文件进行比较，而是可以逐条读取它们。 - Giorgio
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接