Domanda

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
È stato utile?

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

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top