计数不同的元素

我有这样一个列表（假设它是在summ.txt记忆）：计数不同的元素

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

我需要获得，在第一列的每一个元素（ s_）第二个不同元素的数量（d_）。在这种情况下：

我使用一个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_大约有3千万个元素，所以计算所有元素需要太多时间。你能建议一个更快的算法吗？

来源

2011-12-06 markusian

+1这将是一个很好的代码高尔夫问题。 – Phil

，而不是通过文件去一次为每个s_，做一次全部：

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

应用到您的样本数据，这给：

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

在这个答案中完成的处理与每个完成的处理大致相同在问题的shell脚本中。因此，我预计加速约300万。

来源

2011-12-06 12:35:42

你的方法很简单，我想知道为什么我没有想到它！这正是我所需要的， – markusian

这个答案显示了Unix工具包和管道的强大功能。做好一件事的小程序。祝你们好运。 – shellter

排序步骤是O（Ñ LG Ñ），并且可以有利于线性时间算法来避免。这里的一个Python版本：（排序输出可以在O（ķ LG ķ）额外的时间，其中ķ是不同键数而得到）

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)

来源

2011-12-06 12:25:41

+1在您的答案中列出时间复杂度！ – jedwards

使用DBMS？

或者......

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(); 
}

来源

2011-12-06 12:28:43 symcbean

顺便说一句，有各种调整排序选项 - 请参阅手册页。 – symcbean

计数不同的元素

回答

相关问题