Подсчет повторяющихся URL, самый быстрый способ

Question

Я все еще работаю с этим огромным списком URL, вся помощь, которую я получил, была отличной.

На данный момент список выглядит примерно так (хотя 17000 URL-адресов):

http://www.domain.com/page?CONTENT_ITEM_ID=1
http://www.domain.com/page?CONTENT_ITEM_ID=3
http://www.domain.com/page?CONTENT_ITEM_ID=2
http://www.domain.com/page?CONTENT_ITEM_ID=1
http://www.domain.com/page?CONTENT_ITEM_ID=2
http://www.domain.com/page?CONTENT_ITEM_ID=3
http://www.domain.com/page?CONTENT_ITEM_ID=3

Я могу отфильтровать дубликаты без проблем с помощью нескольких методов, awk и т. Д. То, что я действительно хочу сделать, это извлечь дубликаты URL, но в то же время принять во внимание, сколько раз URL существует в перечислить и распечатать счетчик рядом с URL с разделителем каналов. После обработки списка это должно выглядеть так:

url | количество
http://www.domain.com/page?CONTENT_ITEM_ID=1 | 2
http://www.domain.com/page?CONTENT_ITEM_ID=2 | 2
http://www.domain.com/page?CONTENT_ITEM_ID=3 | 3

Какой метод был бы самым быстрым способом достижения этого?

Приветствия

Answer 1

Это, вероятно, так быстро, как вы можете без написания кода.

    $ cat foo.txt
    http://www.domain.com/page?CONTENT_ITEM_ID=1
    http://www.domain.com/page?CONTENT_ITEM_ID=3
    http://www.domain.com/page?CONTENT_ITEM_ID=2
    http://www.domain.com/page?CONTENT_ITEM_ID=1
    http://www.domain.com/page?CONTENT_ITEM_ID=2
    http://www.domain.com/page?CONTENT_ITEM_ID=3
    http://www.domain.com/page?CONTENT_ITEM_ID=3
    $ sort foo.txt | uniq -c
          2 http://www.domain.com/page?CONTENT_ITEM_ID=1
          2 http://www.domain.com/page?CONTENT_ITEM_ID=2
          3 http://www.domain.com/page?CONTENT_ITEM_ID=3

Провел небольшое тестирование, и это не особенно быстро, хотя для 17k это займет чуть больше 1 секунды (на загруженном компьютере P4 2,8 ГГц)

$ wc -l foo.txt
174955 foo.txt
vinko@mithril:~/i3media/2008/product/Pending$ time sort foo.txt | uniq -c
  54482 http://www.domain.com/page?CONTENT_ITEM_ID=1
  48212 http://www.domain.com/page?CONTENT_ITEM_ID=2
  72261 http://www.domain.com/page?CONTENT_ITEM_ID=3

real    0m23.534s
user    0m16.817s
sys     0m0.084s

$ wc -l foo.txt
14955 foo.txt
$ time sort foo.txt | uniq -c
   4233 http://www.domain.com/page?CONTENT_ITEM_ID=1
   4290 http://www.domain.com/page?CONTENT_ITEM_ID=2
   6432 http://www.domain.com/page?CONTENT_ITEM_ID=3

real    0m1.349s
user    0m1.216s
sys     0m0.012s

Хотя O (), как обычно, побеждает в игре. Протестировано решение С.Лотта и

$ cat pythoncount.py
from collections import defaultdict
myFile = open( "foo.txt", "ru" )
fq= defaultdict( int )
for n in myFile:
    fq[n] += 1
for n in fq.items():
    print "%s|%s" % (n[0].strip(),n[1])

$ wc -l foo.txt
14955 foo.txt

$ time python pythoncount.py
http://www.domain.com/page?CONTENT_ITEM_ID=2|4290
http://www.domain.com/page?CONTENT_ITEM_ID=1|4233
http://www.domain.com/page?CONTENT_ITEM_ID=3|6432

real    0m0.072s
user    0m0.028s
sys     0m0.012s

$ wc -l foo.txt
1778955 foo.txt

$ time python pythoncount.py
http://www.domain.com/page?CONTENT_ITEM_ID=2|504762
http://www.domain.com/page?CONTENT_ITEM_ID=1|517557
http://www.domain.com/page?CONTENT_ITEM_ID=3|756636

real    0m2.718s
user    0m2.440s
sys     0m0.072s

Answer 2

Собираетесь ли вы делать это снова и снова? Если нет, то «самый быстрый», как и самый быстрый для реализации, вероятно,

sort </file/of/urls | uniq --count | awk '{ print $2, " | ", $1}'

(не проверял, я не рядом с командной строкой UNIX)

Answer 3

В perl

[заявление об отказе: в данный момент не может проверить этот код]

while (<>) {
    chomp;
    $occurences{$_}++;
}
foreach $url (sort keys %occurences) {
    printf "%s|%d\n", $url, $occurences{$url};
}

Answer 4

См. Преобразование списка кортежей в dict в python .

По сути, вы делаете то же самое с int вместо списка.

Это может быть быстрее, чем сортировка системы, потому что это O (n). Тем не менее, это также Python, а не C.

from collections import defaultdict
myFile = open( "urlFile", "ru" )
fq= defaultdict( int )
for n in myFile:
    fq[n] += 1

for url, count in fq.iteritems():
    print url.rstrip(), "|", count

На моем маленьком Dell D830 17000 URL обрабатываются за 0,015 секунды.

Answer 5

Вот еще одна версия на Python:

import fileinput, itertools

urls = sorted(fileinput.input())
for url, sameurls in itertools.groupby(urls):
    print url.rstrip(), "|", sum(1 for _ in sameurls)

Пример:

$ cat foo.txt
http://www.domain.com/page?CONTENT_ITEM_ID=1
http://www.domain.com/page?CONTENT_ITEM_ID=3
http://www.domain.com/page?CONTENT_ITEM_ID=2
http://www.domain.com/page?CONTENT_ITEM_ID=1
http://www.domain.com/page?CONTENT_ITEM_ID=2
http://www.domain.com/page?CONTENT_ITEM_ID=3
http://www.domain.com/page?CONTENT_ITEM_ID=3

$ python countuniq.py foo.txt
http://www.domain.com/page?CONTENT_ITEM_ID=1 | 2
http://www.domain.com/page?CONTENT_ITEM_ID=2 | 2
http://www.domain.com/page?CONTENT_ITEM_ID=3 | 3

Производительность:

C:\> timethis "sort urls17000.txt|uniq -c"
...
TimeThis :  Elapsed Time :  00:00:00.688

C:\> timethis python countuniq.py urls17000.txt
...
TimeThis :  Elapsed Time :  00:00:00.625

C:\> timethis python slott.py urls17000.txt
...
TimeThis :  Elapsed Time :  00:00:00.562

C:\> timethis perl toolkit.pl urls17000.txt
...
TimeThis :  Elapsed Time :  00:00:00.187

Заключение : Все решения менее 1 секунды. Самая медленная труба, Решение S.Lott быстрее, чем у вышеприведенной версии Python, а Perl-решение toolkit самое быстрое.

---

C:\> timethis perl toolkit.pl urls1778955.txt
...
TimeThis :  Elapsed Time :  00:00:17.656

C:\> timethis "sort urls1778955.txt|uniq -c"
...
TimeThis :  Elapsed Time :  00:01:54.234

$ wc urls1778955.txt
1778955  1778955 81831930 urls1778955.txt

Хеширование бита сортирует по большому количеству URL.