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

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是不同的个数 键。)