modo più veloce per l'ordinamento di un dizionario corpus in un OrderedDict - pitone

Question

Dato un corpus/testi come ad esempio:

Resumption of the session 
I declare resumed the session of the European Parliament adjourned on Friday 17 December 1999 , and I would like once again to wish you a happy new year in the hope that you enjoyed a pleasant festive period . 
Although , as you will have seen , the dreaded ' millennium bug ' failed to materialise , still the people in a number of countries suffered a series of natural disasters that truly were dreadful . 
You have requested a debate on this subject in the course of the next few days , during this part @-@ session . 
In the meantime , I should like to observe a minute ' s silence , as a number of Members have requested , on behalf of all the victims concerned , particularly those of the terrible storms , in the various countries of the European Union . 

potrebbe semplicemente fare questo per ottenere un dizionario con le frequenze di parole:

>>> word_freq = Counter() 
>>> for line in text.split('\n'): 
...  for word in line.split(): 
...    word_freq[word]+=1 
... 

ma se l'obiettivo è quello di realizzare un dizionario ordinato dal più alto al più basso di frequenza, dovrò fare questo:

>>> from collections import OrderedDict 
>>> sorted_word_freq = OrderedDict() 
>>> for word, freq in word_freq.most_common(): 
...  sorted_word_freq[word] = freq 
... 

Immaginate di avere 1 miliardo di chiavi nell'oggetto Counter, l'iterazione attraverso lo most_common() avrebbe una complessità di passare attraverso un corpus (istanze non univoche) una volta e il vocabolario (chiave univoca).

Nota: La Counter.most_common() chiamerebbero un annuncio-hoc sorted(), vedere https://hg.python.org/cpython/file/e38470b49d3c/Lib/collections.py#l472

Detto questo, ho visto il seguente codice che utilizza numpy.argsort():

>>> import numpy as np 
>>> words = word_freq.keys() 
>>> freqs = word_freq.values() 
>>> sorted_word_index = np.argsort(freqs) # lowest to highest 
>>> sorted_word_freq_with_numpy = OrderedDict() 
>>> for idx in reversed(sorted_word_index): 
...  sorted_word_freq_with_numpy[words[idx]] = freqs[idx] 
... 

che è più veloce?

C'è qualche altro modo più veloce per ottenere tale OrderedDict da un Counter?

diverso da OrderedDict, ci sono altri oggetti Python che ottengono la stessa coppia chiave-valore ordinata?

Supporre che la memoria non sia un problema. Dato 120 GB di RAM, non ci dovrebbe essere molto problema per mantenere 1 miliardo di coppie valore-chiave giusto? Assumi una media di 20 caratteri per chiave per 1 miliardo di chiavi e un singolo intero per ogni valore.

Answer 1

L'oggetto Series in Pandas è un array di coppie chiave-valore (che possono avere chiavi non univoche) che potrebbero essere di interesse. Ha un metodo sort che ordina in base ai valori ed è implementato in Cython. Ecco un esempio di ordinamento di un array di lunghezza un milione:

In [39]: 
import pandas as pd 
import numpy as np 

arr = np.arange(1e6) 
np.random.shuffle(arr) 
s = pd.Series(arr, index=np.arange(1e6)) 
%timeit s.sort() 
%timeit sorted(arr) 

1 loops, best of 3: 85.8 ms per loop 
1 loops, best of 3: 1.15 s per loop 

Dato un normale Python dict è possibile costruire un Series chiamando:

my_series = pd.Series(my_dict) 

Poi ordina per valore

my_series.sort() 

Answer 2

Un passo per migliorare la velocità è riempire il contatore in modo ottimale.

Ad esempio, con il tuo txt (802 caratteri).

mycounter=Counter(txt.split()) 

produce la stessa cosa come word_counter, ma nel terzo tempo.

O se si deve leggere il testo riga per riga da un file, quindi utilizzare:

word_freq=Counter() 
for line in txt.splitlines(): 
    word_freq.update(line.split()) 

Allo stesso modo il dizionario ordinato possono essere creati senza l'anello:

mydict = OrderedDict(sorted(mycounter.items(), key=operator.itemgetter(1), reverse=True)) 

Eccomi chiamando lo sorted allo stesso modo di most_common (come da collegamento). E sto passando l'elenco di elementi ordinati direttamente al creatore OrderedDict.

Quando guardo mycounter in ipython, ottengo i valori in modo ordinato:

In [160]: mycounter 
Out[160]: Counter({'the': 13, ',': 10, 'of': 9, 'a': 7, '.': 4, 'in': 4, 'to': 3, 'have': 3, 'session': 3, ''': 3, 'on': 3, 'you': 3, 'I': 3, 'that': 2, 'requested': 2, 'like': 2, 'European': 2, 'this': 2, 'countries': 2, 'as': 2, 'number': 2, 's': 1, 'various': 1, 'wish': 1, 'will': 1, 'Parliament': 1, 'meantime': 1, 'Resumption': 1, 'natural': 1, 'days': 1, 'debate': 1, 'You': 1, 'Members': 1, 'next': 1, '@-@': 1, 'hope': 1, 'enjoyed': 1, 'December': 1, 'victims': 1, 'particularly': 1, 'millennium': 1, .... 'behalf': 1, 'were': 1, 'failed': 1}) 

Questo perché il suo metodo __repr__ chiama most_common. Di nuovo questo è dal tuo link.

items = ', '.join(map('%r: %r'.__mod__, self.most_common())) 

Su ulteriori test vedo che chiamare direttamente sorted non risparmiare tempo:

In [166]: timeit mycounter.most_common() 
10000 loops, best of 3: 31.1 µs per loop 

In [167]: timeit sorted(mycounter.items(),key=operator.itemgetter(1),reverse=True) 
10000 loops, best of 3: 30.5 µs per loop 

In [168]: timeit OrderedDict(mycounter.most_common()) 
1000 loops, best of 3: 225 µs per loop 

In questo caso, il caricamento del dizionario direttamente non salva tempo sia. Il tuo iterazione fa altrettanto bene:

In [174]: %%timeit 
    .....: sorteddict=OrderedDict() 
    .....: for word,freq in word_freq.most_common(): 
    sorteddict[word]=freq 
    .....: 
1000 loops, best of 3: 224 µs per loop 

Per questo esempio, utilizzando np.argsort non aiuta (timewise). La semplice chiamata argsort è più lenta di most_common.

In [178]: timeit np.argsort(list(mycounter.values())) 
10000 loops, best of 3: 34.2 µs per loop 

maggior parte del tempo è nel convertire l'elenco in un array, x=np.array(list(mycounter.values())). np.argsort(x) è molto più veloce. Questo è vero per molte delle funzionalità di numpy. Quando si opera su array numpy è veloce. Ma c'è un sacco di spese generali quando si convertono gli elenchi in array.

posso creare l'OrderedDict via numpy in una sola riga con:

OrderedDict(np.sort(np.array(list(mycounter.items()), dtype='a12,i'), order='f1')[::-1]) 

o in pezzi:

lla = np.array(list(mycounter.items()),dtype='a12,i') 
lla.sort(order='f1') 
OrderedDict(lla[::-1]) 

Sto facendo una matrice strutturata dal items(), l'ordinamento che dal 2 ° campo, quindi creare il dizionario. Nessun risparmio di tempo però. Vedere https://stackoverflow.com/a/31837513/901925 per un altro esempio recente di utilizzo di order per ordinare un array strutturato.