Python. Является ли словарь медленным, чтобы найти частоту каждого символа?

Я пытаюсь найти частоту каждого символа в любом заданном тексте, используя алгоритм сложности O (n). Мой алгоритм выглядит так:

s = len(text) 
P = 1.0/s 
freqs = {} 
for char in text: 
    try: 
       freqs[char]+=P 
    except: 
       freqs[char]=P

но я сомневаюсь, что этот словарь-метод достаточно быстр, поскольку он зависит от базовой реализации методов словаря. Это самый быстрый способ?

UPDATE: нет увеличения скорости, если используются коллекции и целые числа. Это связано с тем, что алгоритм уже имеет сложность O (n), поэтому существенное ускорение не возможно.

Например, результаты для текста 1MB:

without collections:
real    0m0.695s

with collections:
real    0m0.625s

Ответ 1

Сравнение производительности

Примечание: время в таблице не включает время, необходимое для загрузки файлов.

| approach       | american-english, |      big.txt, | time w.r.t. defaultdict |
|                |     time, seconds | time, seconds |                         |
|----------------+-------------------+---------------+-------------------------|
| Counter        |             0.451 |         3.367 |                     3.6 |
| setdefault     |             0.348 |         2.320 |                     2.5 |
| list           |             0.277 |         1.822 |                       2 |
| try/except     |             0.158 |         1.068 |                     1.2 |
| defaultdict    |             0.141 |         0.925 |                       1 |
| numpy          |             0.012 |         0.076 |                   0.082 |
| S.Mark ext.  |             0.003 |         0.019 |                   0.021 |
| ext. in Cython |             0.001 |         0.008 |                  0.0086 |
#+TBLFM: $4=$3/@7$3;%.2g

Используемые файлы: '/usr/share/dict/american-english' и 'big.txt'.

script, который сравнивает варианты "Counter", "setdefault", "list", "try/except", "defaultdict", "numpy", "cython" и @S.Mark в http://gist.github.com/347000

Самое быстрое решение - расширение Python, написанное в Cython:

import cython

@cython.locals(
    chars=unicode,
    i=cython.Py_ssize_t,
    L=cython.Py_ssize_t[0x10000])
def countchars_cython(chars):
    for i in range(0x10000): # unicode code points > 0xffff are not supported
        L[i] = 0

    for c in chars:
        L[c] += 1

    return {unichr(i): L[i] for i in range(0x10000) if L[i]}

Предыдущее сравнение:

* python (dict) : 0.5  seconds
* python (list) : 0.5  (ascii) (0.2 if read whole file in memory)
* perl          : 0.5
* python (numpy): 0.07 
* c++           : 0.05
* c             : 0.008 (ascii)

Входные данные:

$ tail /usr/share/dict/american-english
éclat's
élan
élan's
émigré
émigrés
épée
épées
étude
étude's
études

$ du -h /usr/share/dict/american-english
912K    /usr/share/dict/american-english

python (Counter): 0,5 секунды

#!/usr/bin/env python3.1
import collections, fileinput, textwrap

chars = (ch for word in fileinput.input() for ch in word.rstrip())
# faster (0.4s) but less flexible: chars = open(filename).read()
print(textwrap.fill(str(collections.Counter(chars)), width=79))

Запустите его:

$ time -p python3.1 count_char.py /usr/share/dict/american-english

Counter({'e': 87823, 's': 86620, 'i': 66548, 'a': 62778, 'n': 56696, 'r':
56286, 't': 51588, 'o': 48425, 'l': 39914, 'c': 30020, 'd': 28068, 'u': 25810,
"'": 24511, 'g': 22262, 'p': 20917, 'm': 20747, 'h': 18453, 'b': 14137, 'y':
12367, 'f': 10049, 'k': 7800, 'v': 7573, 'w': 6924, 'z': 3088, 'x': 2082, 'M':
1686, 'C': 1549, 'S': 1515, 'q': 1447, 'B': 1387, 'j': 1376, 'A': 1345, 'P':
974, 'L': 912, 'H': 860, 'T': 858, 'G': 811, 'D': 809, 'R': 749, 'K': 656, 'E':
618, 'J': 539, 'N': 531, 'W': 507, 'F': 502, 'O': 354, 'I': 344, 'V': 330, 'Z':
150, 'Y': 140, 'é': 128, 'U': 117, 'Q': 63, 'X': 42, 'è': 29, 'ö': 12, 'ü': 12,
'ó': 10, 'á': 10, 'ä': 7, 'ê': 6, 'â': 6, 'ñ': 6, 'ç': 4, 'å': 3, 'û': 3, 'í':
2, 'ô': 2, 'Å': 1})
real 0.44
user 0.43
sys 0.01

perl: 0,5 секунды

time -p perl -MData::Dumper -F'' -lanwe'$c{$_}++ for (@F);
END{ $Data::Dumper::Terse = 1; $Data::Dumper::Indent = 0; print Dumper(\%c) }
' /usr/share/dict/american-english

Вывод:

{'S' => 1515,'K' => 656,'' => 29,'d' => 28068,'Y' => 140,'E' => 618,'y' => 12367,'g' => 22262,'e' => 87823,'' => 2,'J' => 539,'' => 241,'' => 3,'' => 6,'' => 4,'' => 128,'D' => 809,'q' => 1447,'b' => 14137,'z' => 3088,'w' => 6924,'Q' => 63,'' => 10,'M' => 1686,'C' => 1549,'' => 10,'L' => 912,'X' => 42,'P' => 974,'' => 12,'\'' => 24511,'' => 6,'a' => 62778,'T' => 858,'N' => 531,'j' => 1376,'Z' => 150,'u' => 25810,'k' => 7800,'t' => 51588,'' => 6,'W' => 507,'v' => 7573,'s' => 86620,'B' => 1387,'H' => 860,'c' => 30020,'' => 12,'I' => 344,'' => 3,'G' => 811,'U' => 117,'F' => 502,'' => 2,'r' => 56286,'x' => 2082,'V' => 330,'h' => 18453,'f' => 10049,'' => 1,'i' => 66548,'A' => 1345,'O' => 354,'n' => 56696,'m' => 20747,'l' => 39914,'' => 7,'p' => 20917,'R' => 749,'o' => 48425}
real 0.51
user 0.49
sys 0.02

python (numpy): 0,07 секунды

На основе Ants Aasma answer (изменен для поддержки юникода):

#!/usr/bin/env python
import codecs, itertools, operator, sys
import numpy

filename = sys.argv[1] if len(sys.argv)>1 else '/usr/share/dict/american-english'

# ucs2 or ucs4 python?
dtype = {2: numpy.uint16, 4: numpy.uint32}[len(buffer(u"u"))]

# count ordinals
text = codecs.open(filename, encoding='utf-8').read()
a = numpy.frombuffer(text, dtype=dtype)
counts = numpy.bincount(a)

# pretty print
counts = [(unichr(i), v) for i, v in enumerate(counts) if v]
counts.sort(key=operator.itemgetter(1))
print ' '.join('("%s" %d)' % c for c in counts  if c[0] not in ' \t\n')

Вывод:

("Å" 1) ("í" 2) ("ô" 2) ("å" 3) ("û" 3) ("ç" 4) ("â" 6) ("ê" 6) ("ñ" 6) ("ä" 7) ("á" 10) ("ó" 10) ("ö" 12) ("ü" 12) ("è" 29) ("X" 42) ("Q" 63) ("U" 117) ("é" 128) ("Y" 140) ("Z" 150) ("V" 330) ("I" 344) ("O" 354) ("F" 502) ("W" 507) ("N" 531) ("J" 539) ("E" 618) ("K" 656) ("R" 749) ("D" 809) ("G" 811) ("T" 858) ("H" 860) ("L" 912) ("P" 974) ("A" 1345) ("j" 1376) ("B" 1387) ("q" 1447) ("S" 1515) ("C" 1549) ("M" 1686) ("x" 2082) ("z" 3088) ("w" 6924) ("v" 7573) ("k" 7800) ("f" 10049) ("y" 12367) ("b" 14137) ("h" 18453) ("m" 20747) ("p" 20917) ("g" 22262) ("'" 24511) ("u" 25810) ("d" 28068) ("c" 30020) ("l" 39914) ("o" 48425) ("t" 51588) ("r" 56286) ("n" 56696) ("a" 62778) ("i" 66548) ("s" 86620) ("e" 87823)
real 0.07
user 0.06
sys 0.01

С++: 0,05 секунды

// $ g++ *.cc -lboost_program_options 
// $ ./a.out /usr/share/dict/american-english    
#include <iostream>
#include <fstream>
#include <cstdlib> // exit

#include <boost/program_options/detail/utf8_codecvt_facet.hpp>
#include <boost/tr1/unordered_map.hpp>
#include <boost/foreach.hpp>

int main(int argc, char* argv[]) {
  using namespace std;

  // open input file
  if (argc != 2) {
    cerr << "Usage: " << argv[0] << " <filename>\n";
    exit(2);
  }
  wifstream f(argv[argc-1]); 

  // assume the file has utf-8 encoding
  locale utf8_locale(locale(""), 
      new boost::program_options::detail::utf8_codecvt_facet);
  f.imbue(utf8_locale); 

  // count characters frequencies
  typedef std::tr1::unordered_map<wchar_t, size_t> hashtable_t;  
  hashtable_t counts;
  for (wchar_t ch; f >> ch; )
    counts[ch]++;

  // print result
  wofstream of("output.utf8");
  of.imbue(utf8_locale);
  BOOST_FOREACH(hashtable_t::value_type i, counts) 
    of << "(" << i.first << " " << i.second << ") ";
  of << endl;
}

Результат:

$ cat output.utf8

(í 2) (O 354) (P 974) (Q 63) (R 749) (S 1,515) (ñ 6) (T 858) (U 117) (ó 10) (ô 2) (V 330) (W 507) (X 42) (ö 12) (Y 140) (Z 150) (û 3) (ü 12) (a 62,778) (b 14,137) (c 30,020) (d 28,068) (e 87,823) (f 10,049) (g 22,262) (h 18,453) (i 66,548) (j 1,376) (k 7,800) (l 39,914) (m 20,747) (n 56,696) (o 48,425) (p 20,917) (q 1,447) (r 56,286) (s 86,620) (t 51,588) (u 25,810) (Å 1) (' 24,511) (v 7,573) (w 6,924) (x 2,082) (y 12,367) (z 3,088) (A 1,345) (B 1,387) (C 1,549) (á 10) (â 6) (D 809) (E 618) (F 502) (ä 7) (å 3) (G 811) (H 860) (ç 4) (I 344) (J 539) (è 29) (K 656) (é 128) (ê 6) (L 912) (M 1,686) (N 531)

c (ascii): 0,0079 секунды

// $ gcc -O3 cc_ascii.c -o cc_ascii && time -p ./cc_ascii < input.txt
#include <stdio.h>

enum { N = 256 };
size_t counts[N];

int main(void) {
  // count characters
  int ch = -1;
  while((ch = getchar()) != EOF)
    ++counts[ch];

  // print result
  size_t i = 0;
  for (; i < N; ++i) 
    if (counts[i])
      printf("('%c' %zu) ", (int)i, counts[i]);
  return 0;
}

Ответ 2

Как избежать операций с float внутри цикла и делать это после того, как все сделано?

Таким образом, вы могли бы просто делать +1 каждый раз, и это должно быть быстрее.

И лучше использовать collection.defaultdict, как советует S.Lott.

freqs=collections.defaultdict(int)

for char in text: 
   freqs[char]+=1

Или вы можете попробовать, collections.Counter в python 2.7 +

>>> collections.Counter("xyzabcxyz")
Counter({'y': 2, 'x': 2, 'z': 2, 'a': 1, 'c': 1, 'b': 1})

или

Вы можете попробовать psyco, которые точно компилируются для python. У вас есть петли, поэтому я думаю, что вы получите некоторое повышение производительности с помощью psyco

Изменить 1:

Я сделал несколько базовых показателей на big.txt (~ 6.5 МБ), который используется в корректор орфографии peter norvig

Text Length: 6488666

dict.get : 11.9060001373 s
93 chars {u' ': 1036511, u'$': 110, u'(': 1748, u',': 77675, u'0': 3064, u'4': 2417, u'8': 2527, u'<': 2, u'@': 8, ....

if char in dict : 9.71799993515 s
93 chars {u' ': 1036511, u'$': 110, u'(': 1748, u',': 77675, u'0': 3064, u'4': 2417, u'8': 2527, u'<': 2, u'@': 8, ....

dict try/catch : 7.35899996758 s
93 chars {u' ': 1036511, u'$': 110, u'(': 1748, u',': 77675, u'0': 3064, u'4': 2417, u'8': 2527, u'<': 2, u'@': 8, ....

collections.default : 7.29699993134 s
93 chars defaultdict(<type 'int'>, {u' ': 1036511, u'$': 110, u'(': 1748, u',': 77675, u'0': 3064, u'4': 2417, u'8': 2527, u'<': 2, u'@': 8, ....

_{Характеристики процессора: процессор Intel Atom Atom с тактовой частотой 1,6 ГГц}

В соответствии с этим dict.get является ~~самым медленным~~ и collections.defaultdict является самым быстрым, try/except также является быстрым.

Изменить 2:

Добавлены теги collections.Counter, медленнее, чем dict.get, и заняли 15 секунд в моем ноутбуке

collections.Counter : 15.3439998627 s
93 chars Counter({u' ': 1036511, u'e': 628234, u't': 444459, u'a': 395872, u'o': 382683, u'n': 362397, u'i': 348464,

Ответ 3

Я написал Char Расширение счетчика C для Python, выглядит как 300x быстрее, чем collections.Counter и 150x быстрее, чем collections.default(int)

C Char Counter : 0.0469999313354 s
93 chars {u' ': 1036511, u'$': 110, u'(': 1748, u',': 77675, u'0': 3064, u'4': 2417, u'8': 2527, u'<': 2, u'@': 8,

Вот Char коды расширений счетчика C

static PyObject *
CharCounter(PyObject *self, PyObject *args, PyObject *keywds)
{
    wchar_t *t1;unsigned l1=0;

    if (!PyArg_ParseTuple(args,"u#",&t1,&l1)) return NULL;

    PyObject *resultList,*itemTuple;

    for(unsigned i=0;i<=0xffff;i++)char_counter[i]=0;

    unsigned chlen=0;

    for(unsigned i=0;i<l1;i++){
        if(char_counter[t1[i]]==0)char_list[chlen++]=t1[i];
        char_counter[t1[i]]++;
    }

    resultList = PyList_New(0);

    for(unsigned i=0;i<chlen;i++){
        itemTuple = PyTuple_New(2);

        PyTuple_SetItem(itemTuple, 0,PyUnicode_FromWideChar(&char_list[i],1));
        PyTuple_SetItem(itemTuple, 1,PyInt_FromLong(char_counter[char_list[i]]));

        PyList_Append(resultList, itemTuple);
        Py_DECREF(itemTuple);

    };

    return resultList;
}

В тех случаях, когда char_counter и char_list являются malloc-ated на уровне модуля, поэтому не нужно malloc каждый раз при вызове функции.

char_counter=(unsigned*)malloc(sizeof(unsigned)*0x10000);
char_list=(wchar_t*)malloc(sizeof(wchar_t)*0x10000);

Он возвращает список с кортежами

[(u'T', 16282), (u'h', 287323), (u'e', 628234), (u' ', 1036511), (u'P', 8946), (u'r', 303977), (u'o', 382683), ...

Чтобы преобразовать в формат dict, просто dict() сделает.

dict(CharCounter(text))

PS: Benchmark включал преобразование времени в dict

CharCounter принимает только строку Unicode Python u"", если текст является utf8, нужно сделать .decode("utf8") заранее.

Вход Поддерживает Unicode до Basic Multilingual Plane (BMP) - от 0x0000 до 0xFFFF

Ответ 4

Нет, это не самый быстрый, потому что вы знаете, что символы имеют ограниченный диапазон, и вы можете использовать список и прямую индексацию, используя числовое представление символа, для хранения частот.

Ответ 5

Очень тяжело бить dict. Он очень сильно настроен, поскольку почти все в Python основано на dict.

Ответ 6

Я не знаком с python, но для поиска частот, если вы не знаете диапазон частот (в этом случае вы можете использовать массив), словарь - это путь. Если вы знаете свои символы в диапазоне Unicode, ASCII и т.д., Вы можете определить массив с правильным количеством значений.
Тем не менее, это изменит пространственную сложность этого от O (n) до O (возможное n), но вы получите улучшение временной сложности от O (n * (время извлечения/времени словаря)) до O (n).

Ответ 7

Если вы действительно обеспокоены скоростью, вы можете рассмотреть сначала подсчет символов с целыми числами, а затем получить частоты через (float) деление.

Вот цифры:

python -mtimeit -s'x=0' 'x+=1'      
10000000 loops, best of 3: 0.0661 usec per loop

python -mtimeit -s'x=0.' 'x+=1.'
10000000 loops, best of 3: 0.0965 usec per loop

Ответ 8

ну, вы можете сделать это в старомодном стиле... поскольку мы знаем, что не так много разных персонажей, и они смежны, мы можем использовать простой массив (или список здесь) и использовать порядковые номера символов для индексирования:

s = 1.0*len(text)
counts = [0]*256 # change this if working with unicode
for char in text: 
    freqs[ord(char)]+=1

freqs = dict((chr(i), v/s) for i,v in enumerate(counts) if v)

Это, вероятно, будет быстрее, но с постоянным коэффициентом оба метода должны иметь одинаковую сложность.

Ответ 9

Используя этот код на Алисе в Стране Чудес (163793 символов) и "Библия, версия Дуэ-Реймса" (5649295 символов) из проекта Гутенберг:

from collections import defaultdict
import timeit

def countchars():
    f = open('8300-8.txt', 'rb')
    #f = open('11.txt')
    s = f.read()
    f.close()
    charDict = defaultdict(int)
    for aChar in s:
        charDict[aChar] += 1


if __name__ == '__main__':
    tm = timeit.Timer('countchars()', 'from countchars import countchars')  
    print tm.timeit(10)

Я получаю:

2.27324003315 #Alice in Wonderland
74.8686217403 #Bible

Соотношение между количеством символов для обеих книг 0.029, а отношение между временами 0.030, поэтому алгоритм O (n) с очень малым постоянным множителем. Я думаю, что достаточно быстро для большинства (всех?) Целей.

Ответ 10

Если данные находятся в однобайтовой кодировке, вы можете использовать numpy для ускорения процесса подсчета:

import numpy as np

def char_freq(data):
    counts = np.bincount(np.frombuffer(data, dtype=np.byte))
    freqs = counts.astype(np.double) / len(data)
    return dict((chr(idx), freq) for idx, freq in enumerate(freqs) if freq > 0)

Некоторые быстрые бенчмаркинга показывают, что это примерно в 10 раз быстрее, чем агрегирование по умолчаниюdict (int).

Ответ 11

Чтобы избежать попытки, кроме накладных расходов, вы можете использовать defaultdict.

Ответ 12

Малая скорость будет использовать метод dict.setdefault, таким образом вы не будете платить довольно большую цену за каждый новый встреченный персонаж:

for char in text:
    freq[char] = freq.setdefault(char, 0.0) + P

В качестве побочного элемента: с обнаженным except: считается очень плохой практикой.