schnellste Weg, um einen Korpus Wörterbuch in eine OrderedDict Sortierung - Python

Question

ein Korpus Gegeben/Texte als solche:

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 . 

konnte ich einfach das tun, ein Wörterbuch mit Worthäufigkeiten zu bekommen:

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

Aber wenn das Ziel darin besteht, ein bestelltes Wörterbuch von der höchsten zur niedrigsten Frequenz zu erreichen, muss ich dies tun:

Stellen Sie sich vor, ich hätte 1 Milliarde Schlüssel im Objekt Counter, die Iteration durch die most_common() hätte eine Komplexität, einmal durch ein Korpus (nicht eindeutige Instanzen) und das Vokabular (eindeutiger Schlüssel) zu gehen.

Hinweis: Die Counter.most_common() wäre ein Ad-hoc-sorted() nennen, siehe https://hg.python.org/cpython/file/e38470b49d3c/Lib/collections.py#l472

dies gegeben, habe ich den folgenden Code gesehen, dass numpy.argsort() verwendet:

>>> 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] 
... 

, die schneller ist?

Gibt es eine andere Art und Weise schneller eine solche OrderedDict von einem Counter zu bekommen?

Gibt es außer OrderedDict weitere Python-Objekte, die dasselbe sortierte Schlüssel/Wert-Paar erreichen?

Angenommen, Speicher ist kein Problem. Angesichts 120 GB RAM sollte es nicht viel Problem sein, 1 Milliarde Schlüssel-Wert-Paare richtig zu halten? Nehmen Sie einen Durchschnitt von 20 Zeichen pro Schlüssel für 1 Milliarde Schlüssel und eine einzelne Ganzzahl für jeden Wert an.

Answer 1

Das Objekt Series in Pandas ist ein Array von Schlüssel/Wert-Paaren (die nicht eindeutige Schlüssel haben können), die von Interesse sein können. Es hat eine sort Methode, die nach den Werten sortiert und in Cython implementiert ist. Hier ist ein Beispiel einer Anordnung von Länge einer Million Sortierung:

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 

Bei einem normalen Python dict Sie eine Series durch den Aufruf konstruieren können:

my_series = pd.Series(my_dict) 

Dann sortieren nach Wert von

my_series.sort() 

Answer 2

Ein Schritt zur Verbesserung der Geschwindigkeit ist das optimale Füllen des Zählers.

Zum Beispiel mit Ihrer txt (802 char).

mycounter=Counter(txt.split()) 

produziert das gleiche wie Ihr word_counter, aber in 1/3 der Zeit.

Oder wenn Sie den Text Zeile für Zeile aus einer Datei zu lesen, dann verwenden:

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

Ähnlich das bestellte Wörterbuch kann, ohne die Schleife erstellt werden:

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

Hier bin ich Rufen Sie sorted in der gleichen Weise, wie most_common tut (nach Ihrem Link). Und ich gebe die Liste der sortierten Artikel direkt an den Ersteller OrderedDict weiter.

Wenn ich mycounter in ipython aussehen, erhalte ich die Werte in sortierter Reihenfolge:

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}) 

Das ist, weil seine __repr__ Methode most_common nennt. Auch dies ist von Ihrem Link.

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

Auf weitere Tests sehe ich, dass die Zeit sparen sorted direkt aufrufen nicht:

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 diesem Fall laden das Wörterbuch entweder direkt die Zeit nicht speichern. Ihre Iteration funktioniert genauso gut:

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 

Für diese Probe np.argsort Verwendung hilft nicht (zeitlich). Einfacher Anruf argsort ist langsamer als most_common.

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

meiste Zeit ist die Liste in einem Array in Umwandeln x=np.array(list(mycounter.values())). np.argsort(x) ist viel schneller. Das gilt für viele Funktionen numpy. Beim Betrieb auf Arrays numpy ist schnell. Aber es gibt viel Aufwand beim Konvertieren von Listen in Arrays.

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

oder in Stücken:

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

Ich mache eine strukturierte Anordnung von den items(), dass durch die 2. Sortieranlage

kann ich die OrderedDict über numpy in einer Linie mit erstellen Feld und dann das Wörterbuch erstellen. Keine Zeitersparnis. Ein anderes aktuelles Beispiel, das order zum Sortieren eines strukturierten Arrays verwendet, finden Sie unter https://stackoverflow.com/a/31837513/901925.