Слишком медленный подсчет отдельных элементов в большом списке

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

Я использую сценарий оболочки для получения этого:

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) состоит из примерно 19 миллионов элементов, а число различных s_ составляет около 3 миллионов, поэтому для вычисления всех потребуется слишком много времени.Можете ли вы предложить более быстрый алгоритм?

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 количество различных ключей.)

Answer 2

Вместо того, чтобы просматривать файл один раз для каждого s_, выполните их все сразу:

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

Применительно к вашим образцам данных это дает:

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

обработка, выполненная в этом ответе, примерно такая же, как и для каждого s_ в сценарии оболочки в вопросе.Таким образом, я ожидаю ускорение в 3 миллиона раз.

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