快速数据提取算法

我必须使用2个utf-8文本文件。在文件的每一行都有字符串，可以包含特定的语言字符，如Ü，Ö，±，ę。字符串是随机的顺序和长度，可以重复。在第一个文件中至少有3百万行（它可以很容易超过1行的行）。第二个文件比较小，通常可以得到大约40万行（但可以更大）。快速数据提取算法

我需要创建一个新文件，其中包含来自文件1的条目，其中包含出现在文件2和所有重复条目中的已删除条目。

目前我正在对这两个文件进行排序并删除重复条目。接下来，我将它们写入新文件，同时检查它们是否出现在第二个文件中。

有没有更快的方法来做到这一点？

编辑

内存是一个问题。我不会将这些字符串复制到内存中，购买文件操作。我的朋友建议不要复制到内存中，而是处理文件流。这个执行时间显着下降之后。

计算机管理员不想在其上安装数据库。

后排序我的代码神符像这样的循环：

if stringFromFile1 < stringFromFile2 then writeToFile3 and get next stringFromFile1 
else if stringFromFile1 == stringFromFile2 then dropStringFromFile1 and get next stringFromFile1 
else if stringFromFile1 > stringFromFile2 then get next stringFromFile2 and go to line 1

来源

2012-08-03 firescreamer

1亿？数据是否适合内存？ – 2012-08-03 07:37:20

如果你有一个数据结构，如哈希设置，你可以只是遍历文件，并添加每一行。集合不允许重复，散列集应为提供一种检查元素是否已存在的恒定方法（至少在Java中，add方法检查元素是否存在，如果不存在，则将元素添加到定时设定）。

一旦你浏览了这两个文件，你就可以迭代散列集并将其内容存储到文件中。这应该为您提供一个线性时间的算法。

忘了提及：我假设你没有限制内存消耗。如果这样做，则可能需要尝试将每行的散列保存为数据库，并将每行的散列作为主键。使用两个主键插入元素应该失败，从而确保数据库中有唯一的字符串。一旦完成了插入操作，就可以检索数据库中的值并将其存储到文件中。

来源

2012-08-03 07:34:18 npinti

我的建议是预处理文件二并从中构建树结构。例如，假设你有这种文件两种：

bad 
bass 
absent

那么你的树结构会是这样的：

BEGIN -> b -> a -> d -> END 
|    | 
|    + -> s -> s -> END 
| 
+-> a -> b -> s -> e -> n -> t -> END

END指定单词分隔符（可能是空格或新行或别的东西）

然后你打开文件一进入文件流并在字节后读出它的字节。一旦你遇到文件的开始或者在分隔符后选择下一个字符，你就开始走树。如果使用流式传输的字节，您可以将其转到END，这意味着您找到了匹配的字词，您应该放弃它。如果没有，这个词是独一无二的，不需要丢弃。如果发现唯一，则必须将该单词添加到树结构中以丢弃其进一步的重复。

树结构将采取大量的存储器，但它是无论如何比在某种阵列的保持唯一字

来源

2012-08-03 08:26:49

有许多可能的优化的更小。

正如Roman Saveljev建议的那样，您可以在内存中保留一个trie结构。根据数据的熵，它可以很容易地适应内存。

由于第二个文件已排序，您可以运行二分查找来检查记录是否存在（如果您还没有这样做）。

您还可以在内存中保留一个Bloom Filter，以便轻松检查那些不重复的记录，以避免每次都进入磁盘。

来源

2012-08-03 18:54:46

快速数据提取算法

回答

相关问题