c - 如何从两个给定大小为 20GB 的文件中搜索常用密码？

Question

我有两个大小为 20GB 的文件。我必须从一个文件中的任何一个中删除常用密码。

我通过调用 UNIX 的 sort 命令对第二个文件进行了排序。在此之后，我将排序后的文件分成许多文件，以便文件可以使用拆分命令放入 RAM 内存中。拆分为 n 个文件后，我只使用了一个大小为 n 的结构数组来存储每个拆分文件的第一个密码及其对应的文件名。

然后我在该结构数组中应用二进制搜索技术，针对第一个文件的每个键到存储在结构中的第一个密码，以获取相应文件的索引。然后我将 b 搜索应用于该索引的拆分文件。

我假设密码的最大长度为 20 个字符

这个程序还没有效率。

如果可能，请帮助提高效率....

请给我一些建议，以有效地对 20GB 的文件进行排序......

64 位流，8GB RAM 和 i3 四核处理器......

我刚刚用两个大小为 10MB 的文件测试了我的程序。在不使用任何优化选项的情况下花费了大约 2.66 小时。 ....根据我的程序，拆分，排序和二进制搜索后，大约需要7-8个小时来检查每个20GB的密码.....

我可以提高它的时间复杂度吗？我的意思是我可以让它运行得更“快”吗？？？

Answer 1

检查外部排序。参见 http://www.umbrant.com/blog/2011/external_sorting.html在页面末尾确实有代码 (https://github.com/umbrant/extsort)。

外部排序背后的思想是从文件中选择和排序等距样本。然后在采样点对文件进行分区，对分区进行排序并合并结果。

example numbers = [1, 100, 2, 400, 60, 5, 0, 4]
example samples (distance 4) = 1, 60
chunks = {0,1,2,5,4} , {60, 100, 400}

此外，我认为拆分文件不是一个好主意，因为您需要将 20GB 写入磁盘才能拆分它们。您还可以通过在文件中查找来动态创建结构。