与其他几个大文件相比,计算文件唯一性(%)的最有效方法

Question

我有大约30个500MB文件,每行一个字.我有一个脚本,用伪bash做到这一点:

for i in *; do
    echo "" > everythingButI
    for j in *-except-$i; do
        cat $j >> everythingButI
        sort everythingButI | uniq > tmp
        mv tmp everythingButI
    done
    comm $i everythingButI -2 -3 > uniqueInI

    percentUnique=$(wc -l uniqueInI) / $(wc -l $i) * 100
    echo "$i is $percentUnique% Unique"
done

它计算每个文件的"唯一性"(文件已经在每个文件中排序和唯一).

所以,如果我有文件:

file1    file2   file3
a        b       1
c        c       c
d        e       e
f        g
         h

file1将是75%唯一(因为其中1/4的行在另一个文件中找到),file2将是60%唯一,file3将是33.33%唯一.但是要把它变成30个文件,500MB一个弹出,需要一点点才能运行.

我想编写一个python脚本,它可以做得更快,更快,但我想知道实际上最快的算法是什么.(我在PC上也只有2GB的RAM.)

任何人都有关于算法的意见,或者知道更快的方法吗？

Answer 1

编辑：由于每个输入都已经在内部排序和重复数据删除，因此您实际上需要为此进行n路合并，并且本文前一版本中的哈希构建练习相当毫无意义。

如果你不小心的话， n路合并会有点复杂。基本上，它的工作原理是这样的：

• 读入每个文件的第一行，并将其唯一行计数器和总行计数器初始化为 0。
• 执行这个循环体：
  • 找出读取的行中的最小值。
  • 如果该值与任何其他文件中的值不同，则增加该文件的唯一行计数器。
  • 对于每个文件，如果最小值等于最后读取的值，则读取下一行并增加该文件的总行计数器。如果您到达文件末尾，则该文件已完成：将其从进一步考虑中删除。
• 循环直到没有任何文件可供考虑。此时，您应该为每个文件拥有准确的唯一行计数器和总行计数器。那么百分比就是一个简单的乘法和除法问题。

我省略了合并算法完整形式的优先级队列的使用；只有当您有足够多的输入文件时，这一点才变得重要。