我有两个大小为 20GB 的文件。我必须从一个文件中的任何一个中删除常用密码。
我通过调用 UNIX 的 sort 命令对第二个文件进行了排序。在此之后,我将排序后的文件分成许多文件,以便文件可以使用拆分命令放入 RAM 内存中。拆分为 n 个文件后,我只使用了一个大小为 n 的结构数组来存储每个拆分文件的第一个密码及其对应的文件名。
然后我在该结构数组中应用二进制搜索技术,针对第一个文件的每个键到存储在结构中的第一个密码,以获取相应文件的索引。然后我将 b 搜索应用于该索引的拆分文件。
我假设密码的最大长度为 20 个字符
这个程序还没有效率。
如果可能,请帮助提高效率....
请给我一些建议,以有效地对 20GB 的文件进行排序......
64 位流,8GB RAM 和 i3 四核处理器......
我刚刚用两个大小为 10MB 的文件测试了我的程序。在不使用任何优化选项的情况下花费了大约 2.66 小时。 ....根据我的程序,拆分,排序和二进制搜索后,大约需要7-8个小时来检查每个20GB的密码.....
我可以提高它的时间复杂度吗?我的意思是我可以让它运行得更“快”吗???
最佳答案
检查外部排序。参见 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 写入磁盘才能拆分它们。您还可以通过在文件中查找来动态创建结构。
关于c - 如何从两个给定大小为 20GB 的文件中搜索常用密码?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8315485/