计算大列表中的不同元素太慢

Question

我有一个这样的列表（假设它存储在 summ.txt 中）：

s1   d2
s1   d4
s3   d2
s4   d1
s1   d3 
s4   d1
s5   d6
s3   d5
s1   d2

对于第一列 (s_) 中的每个元素，我需要获取第二列中不同元素的数量 ( d_）。在本例中：

s1  3
s3  2
s4  1   
s5  1

我使用 shell 脚本来获取以下内容：

sor=`cat s.txt`

for d in $sor
do

n=$( grep $d ./summ.txt | cut -f2 | sort -u | wc -l)
echo $d, $n

done

其中 s.txt 是包含所有不同 s_ 的文件。在这种情况下，它将是：

s1
s2
s3
s4
s5

我知道这种方法有效，因为我已经尝试过。主要问题是主列表（summ.txt）由大约 1900 万个元素组成，不同 s_ 的数量约为 300 万个，因此计算所有元素会花费太多时间。你能建议一个更快的算法吗？

Answer 1

排序步骤为 O(n lg n)，可以避免，而采用线性时间算法。这是一个 Python 版本：（

distinct_values = defaultdict(set)  # hashmap of keys to hashsets of values
for line in sys.stdin:
    key, val = line.split()
    distinct_values[key].add(val)

for key, values in distinct_values.iteritems():
    print key, len(values)

排序输出可以在 O(k lg k) 额外时间内获得，其中 k 是 k 的数量>不同的键。）

Answer 2

不要为每个 s_ 遍历一次文件，而是一次全部完成：

sort -u | cut -f 1 | uniq -c | awk '{ print $2","$1 }'

应用于您的示例数据，这给出：

s1,3
s3,2
s4,1
s5,1

此答案中完成的处理与每个 完成的处理大致相同>s_ 在问题中的 shell 脚本中。因此，我预计速度会提高约 300 万倍。

Answer 3

使用数据库管理系统？

或者...

sort <input_file | awk -f counter.awk

#!/usr/bin/awk

// {
    if ($1!=prevfirstkey) {
       dump();
       prevfirstkey=$1;
       prevnextkey=$2;
       count=1;
    } else if ($2 != prevnextkey) {
       prevnextkey=$2;
       count++;
    }
}
dump() {
    print prevfirstkey " has " count " values";
    count=0;
}
END {
    dump();
}