这是一个创建于 1005 天前的主题，其中的信息可能已经有所发展或是发生改变。
需要实现如下功能，现在有两个文件，每个文件每行都包含文件名和 md5 ，现在需要对比 a 文件每行 md5 码和文件名是否存在 b 文件中，为了防止文件过大，现在是采用双重循环逐行对比的方式。发现单次遍历 10000 次需要 1.4 秒左右（性能比较好的台式机），两个 10000 行的文件时间不可估量，试过了多线程和多进程遍历，效果不明显，对 python 不是很了解，在这求教大佬解答，有没有好的思路，谢谢！
 |
1
BrettD 2022-03-13 00:18:40 +08:00 via iPhone
把双层嵌套循环改成两个单独的循环
|
 |
2
qaweqa 2022-03-13 00:19:50 +08:00
hash set
|
 |
3
liprais 2022-03-13 00:20:07 +08:00
B 文件弄成字典 name -> md5 遍历 a 完事
|
 |
4
Building 2022-03-13 00:20:23 +08:00
先排序，再对比
|
 |
5
jeffxjh OP |
 |
6
duke807 2022-03-13 01:17:42 +08:00 via Android  1
@jeffxjh 比較理想的做法是 rb tree 實現的 dict ，rb tree 本身是自帶排序的，查找的速度很快。
然而 python 默認的 dict 不是基於 rb tree 或類似的 tree ，而是用 hash 和數組的方式，數據量大的時候，hash 重複比較多，要循環查子數組，查找效率相對低一些。 |
 |
7
xupefei 2022-03-13 02:41:39 +08:00
分别排序后用两个指针从前到后对比，复线性杂度。
|
 |
8
loading 2022-03-13 09:10:34 +08:00 1
我选择导入到数据库用 SQL 跑,join 一下就好了。
|
 |
9
whusnoopy 2022-03-13 09:11:21 +08:00 1
这个不是 Python 的问题，是算法时间复杂度的问题，虽然有一部分和语言或系统相关的性能开销（如磁盘 IO 啥的）
你原始的做法是把两个文件打开，然后双重循环按行比较，这是 O(n^2) 的时间复杂度，O(1) 的空间复杂度（不算读取文件本身的空间开销） 如果按楼上说的用 dict （其实就是 hash ），先读文件 A ，这是 O(n) 的时间复杂度，为了构建这个 dict 需要额外的 O(n) 的空间复杂度，然后拿着这个 dict 去遍历文件 B 来做比较，又是 O(n)*O(1) 的时间复杂度（按行读取和每次比较），总的时间复杂度是 O(n)，空间复杂度是 O(n) 如果用排序后比较，先对文件 A 和文件 B 读取后排序，这需要 O(nlogn) 的时间复杂度（排序的开销），存储两个排序后的文件需要 O(n) 的空间复杂度（没有额外开销，只是需要存着），然后用归并的思路对两个排序后的列表双指针遍历，这是 O(n) 的时间复杂度，总的时间复杂度是 O(nlogn)，空间复杂度是 O(n) 综上，排序后比较有更高的时间复杂度和算法开销（能很快完整写对双指针遍历且处理好边界情况的三脚猫程序员并不多），不如直接用 dict ，就是第二个文件顺序读一遍，把每行内容作为 key 放进一个 dict ，然后遍历第一个文件，如果第一个文件行内容的 key 不在 dict 里，那就是 a 文件这行内容不存在 b 文件里 |
 |
10
ASpiral 2022-03-13 11:06:42 +08:00 via Android 1
先排序后对比，排序将占用这个功能的绝大部分时间；应该参考 3 楼说的方法，先把小的文件转成字典，再遍历大的文件，这样比较好
|
 |
11
d5 2022-03-13 16:14:24 +08:00
排序比较消耗时间。可以直接利用哈希表的特性。可以参考 Linux diff 命令:
https://segmentfault.com/q/1010000005699153 |
 |
12
paopjian 2022-03-13 20:31:22 +08:00
不能直接用 pandas 读取后 join 看结果吗?
|
Select Language