Python - è un dizionario lento per trovare la frequenza di ogni personaggio?
https://stackoverflow.com/questions/2522152
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Sto cercando di trovare una frequenza di ogni simbolo in un dato testo utilizzando un algoritmo di O (n) la complessità. Il mio algoritmo appare come:
s = len(text)
P = 1.0/s
freqs = {}
for char in text:
try:
freqs[char]+=P
except:
freqs[char]=P
ma dubito che questo dizionario-metodo è abbastanza veloce, perché dipende l'implementazione sottostante dei metodi del dizionario. È questo il metodo più veloce?
UPDATE: non v'è alcun aumento della velocità in caso di utilizzo collezioni e interi. È perché l'algoritmo è già di O (n) la complessità, in modo che nessun aumento di velocità essenziale è possibile.
Per esempio, i risultati per il testo 1MB:
without collections:
real 0m0.695s
with collections:
real 0m0.625s
Soluzione
Confronto delle prestazioni
. Nota: il tempo nella tabella non comprende il tempo necessario per caricare i file
| 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's ext. | 0.003 | 0.019 | 0.021 |
| ext. in Cython | 0.001 | 0.008 | 0.0086 |
#+TBLFM: $4=$3/@7$3;%.2g
I file utilizzati:. '/usr/share/dict/american-english' e 'big.txt'
Lo script che mette a confronto 'contatore', 'setDefault', 'lista', 'try / tranne', 'defaultdict', 'NumPy', 'Cython' -based, e @ soluzioni di S.Marco è a http://gist.github.com/347000
La soluzione più veloce è un'estensione Python scritta in 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]}
confronto precedente:
* 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)
dati di ingresso:
$ 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 secondi
#!/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))
eseguirlo:
$ 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 secondi
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
Output:
{'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 secondi
In base a di Aasma risposta (modificato a supporto unicode):
#!/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')
Output:
("Å" 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
C ++: 0,05 secondi
// $ 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;
}
Risultato:
$ 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 secondi
// $ 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;
}
Altri suggerimenti
Come su come evitare operazioni galleggiante all'interno del ciclo e farlo dopo tutto è fatto?
Con questo modo, si può solo fare uno ogni volta, e il suo dovrebbe essere più veloce.
E un uso migliore collections.defaultdict come S. Lott consigliato.
freqs=collections.defaultdict(int)
for char in text:
freqs[char]+=1
Oppure può provare, collections.Counter in Python 2.7 +
>>> collections.Counter("xyzabcxyz")
Counter({'y': 2, 'x': 2, 'z': 2, 'a': 1, 'c': 1, 'b': 1})
o
Si può provare a psyco , che fanno just-in-time compilazione per Python. Hai loop, quindi penso che si potrebbe ottenere un po 'di guadagno di prestazioni con psyco
Modifica 1:
Ho fatto qualche base di parametri di riferimento su big.txt (~ 6.5 MB), che viene utilizzato in < a href = "http://norvig.com/spell-correct.html" rel = "nofollow noreferrer"> ortografia correttore di 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, ....
Specifiche CPU: 1.6GHz Intel Mobile Atom CPU
Secondo tale, dict.get è più lento e collections.defaultdict è più veloce, try/except è anche quella veloce.
Modifica 2:
Aggiunto benchmark collections.Counter, i suoi più lento di dict.get e ha preso 15s nel mio computer portatile
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,
Ho scritto Estensione Char contatore C a Python, si presenta come 300x più veloce di collections.Counter e 150x più veloce di 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,
Ecco Codici Char contatore C estensione
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;
}
Dove char_counter, e char_list sono malloc-ato a livello di modulo, quindi nessun bisogno di malloc ogni volta quando le chiamate di funzione.
char_counter=(unsigned*)malloc(sizeof(unsigned)*0x10000);
char_list=(wchar_t*)malloc(sizeof(wchar_t)*0x10000);
Si restituisce un elenco di tuple
[(u'T', 16282), (u'h', 287323), (u'e', 628234), (u' ', 1036511), (u'P', 8946), (u'r', 303977), (u'o', 382683), ...
Per convertire in formato dict, basta dict() farà.
dict(CharCounter(text))
PS: Benchmark incluso il tempo di conversione a dict
CharCounter accettano solo Python Unicode String u"", se il testo è utf8, bisogno di fare .decode("utf8") in anticipo.
Input supporta Unicode fino Basic Multilingual Plane (BMP) - 0x0000 a 0xFFFF
No, non è il più veloce, perché si sa che i personaggi hanno una portata limitata e si potrebbe utilizzare una lista e l'indicizzazione diretta, utilizzando la rappresentazione numerica del carattere, per memorizzare le frequenze.
E 'molto, molto difficile da battere dict. E 'molto altamente sintonizzato dal momento che quasi tutto in Python è dict-based.
Non ho familiarità con Python, ma per la ricerca di frequenze, se non si conosce la gamma di frequenze (nel qual caso è possibile utilizzare un array), dizionario è la strada da percorrere.
Se conoscete i vostri personaggi in un'unicode, ASCII, ecc gamma, è possibile definire una matrice con il numero corretto di valori.
Tuttavia, questo cambierà la complessità spazio di questo da O (n) a O (possibile n), ma si guadagnerà un miglioramento del tempo di complessità da O (n * (estrazione dizionario / ora di inserimento)) a O (n).
Se siete davvero preoccupati per la velocità, si potrebbe considerare personaggi primi di conteggio con interi e quindi l'ottenimento di frequenze attraverso la divisione (float).
Ecco i numeri:
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
bene, lo si può fare in stile antico ... come sappiamo che non ci sono troppi personaggi diversi e sono contigui, siamo in grado di utilizzare un array semplice (o una lista qui) e utilizzare i caratteri ordinali numerazione per l'indicizzazione:
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)
Questa sarà probabilmente più veloce, ma solo per un fattore costante, entrambi i metodi dovrebbe avere la stessa complessità.
L'utilizzo di questo codice su Alice in Wonderland (163793 caratteri) e "La Bibbia, Douay-Rheims Version" (5649295 caratteri) da Project Gutenberg:
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)
ottengo:
2.27324003315 #Alice in Wonderland
74.8686217403 #Bible
Il rapporto tra il numero di caratteri per entrambi i libri è 0.029 ed il rapporto tra i tempi è 0.030, così, l'algoritmo è O (n) con un piccolo fattore costante. Abbastanza veloce per la maggior parte (tutti?) scopi, direi.
Se i dati sono in un singolo byte di codifica è possibile utilizzare numpy per accelerare il processo di conteggio:
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)
Un rapido analisi comparativa mostra che questo è circa 10 volte più veloce di aggregare ad un defaultdict (int).
Per evitare il tentativo, tranne spese generali è possibile utilizzare un defaultdict.
Piccola velocità di up sarà l'utilizzo di dict.setdefault metodo, che modo non pagherete piuttosto grande prezzo per ogni nuovo personaggio incontrato:
for char in text:
freq[char] = freq.setdefault(char, 0.0) + P
Come sidenote:. Dover except: nudo è considerato molto cattiva pratica
