計數不同的元素

我有這樣一個列表（假設它是在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

計數不同的元素

回答

相關問題