Fast/Optimize N-Gramm-Implementierungen in Python

Question

Welche Ngram-Implementierung ist in Python am schnellsten?

Ich habe versucht, nltk die vs Scotts zip (http://locallyoptimal.com/blog/2013/01/20/elegant-n-gram-generation-in-python/) zum Profil:

from nltk.util import ngrams as nltkngram 
import this, time 

def zipngram(text,n=2): 
    return zip(*[text.split()[i:] for i in range(n)]) 

text = this.s 

start = time.time() 
nltkngram(text.split(), n=2) 
print time.time() - start 

start = time.time() 
zipngram(text, n=2) 
print time.time() - start 

[out]

0.000213146209717 
6.50882720947e-05 

Gibt es eine schnellere Implementierung zur Erzeugung ngrams in Python?

Answer 1

Einige Versuche mit etwas Profilierung. Ich dachte, die Verwendung von Generatoren könnte hier die Geschwindigkeit verbessern. Aber die Verbesserung war im Vergleich zu einer leichten Modifikation des Originals nicht bemerkbar. Aber wenn Sie nicht die vollständige Liste gleichzeitig benötigen, sollten die Generatorfunktionen schneller sein.

import timeit 
from itertools import tee, izip, islice 

def isplit(source, sep): 
    sepsize = len(sep) 
    start = 0 
    while True: 
     idx = source.find(sep, start) 
     if idx == -1: 
      yield source[start:] 
      return 
     yield source[start:idx] 
     start = idx + sepsize 

def pairwise(iterable, n=2): 
    return izip(*(islice(it, pos, None) for pos, it in enumerate(tee(iterable, n)))) 

def zipngram(text, n=2): 
    return zip(*[text.split()[i:] for i in range(n)]) 

def zipngram2(text, n=2): 
    words = text.split() 
    return pairwise(words, n) 


def zipngram3(text, n=2): 
    words = text.split() 
    return zip(*[words[i:] for i in range(n)]) 

def zipngram4(text, n=2): 
    words = isplit(text, ' ') 
    return pairwise(words, n) 


s = "Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum." 
s = s * 10 ** 3 

res = [] 
for n in range(15): 

    a = timeit.timeit('zipngram(s, n)', 'from __main__ import zipngram, s, n', number=100) 
    b = timeit.timeit('list(zipngram2(s, n))', 'from __main__ import zipngram2, s, n', number=100) 
    c = timeit.timeit('zipngram3(s, n)', 'from __main__ import zipngram3, s, n', number=100) 
    d = timeit.timeit('list(zipngram4(s, n))', 'from __main__ import zipngram4, s, n', number=100) 

    res.append((a, b, c, d)) 

a, b, c, d = zip(*res) 

import matplotlib.pyplot as plt 

plt.plot(a, label="zipngram") 
plt.plot(b, label="zipngram2") 
plt.plot(c, label="zipngram3") 
plt.plot(d, label="zipngram4") 
plt.legend(loc=0) 
plt.show() 

Für diese Testdaten scheint ziprngram2 und zigngram3 mit Abstand am schnellsten zu sein.

Answer 2

Erweiterung M4rtini's code, machte ich drei weitere Versionen mit einem fest codierten n=2 Parameter:

def bigram1(text): 
    words = iter(text.split()) 
    last = words.next() 
    for piece in words: 
     yield (last, piece) 
     last = piece 

def bigram2(text): 
    words = text.split() 
    return zip(words, islice(words, 1, None)) 

def bigram3(text): 
    words = text.split() 
    return izip(words, islice(words, 1, None)) 

Mit timeit, erhalte ich diese Ergebnisse:

zipngram(s, 2):  3.854871988296509 
list(zipngram2(s, 2)): 2.0733611583709717 
zipngram3(s, 2):  2.6574149131774902 
list(zipngram4(s, 2)): 4.668303966522217 
list(bigram1(s)):  2.2748169898986816 
bigram2(s):   1.979405164718628 
list(bigram3(s)):  1.891601800918579 

bigram3 ist der schnellste für meine Tests. Es scheint einen kleinen Vorteil zu geben, Hardcoding und Iteratoren zu verwenden, wenn sie überall verwendet werden (zumindest für diesen Parameterwert). Wir sehen den Vorteil von Iteratoren überall in dem größeren Unterschied zwischen zipngram2 und zipngram3 für n=2.

Ich versuchte auch, eine Erhöhung von PyPy zu bekommen, aber es schien tatsächlich die Dinge hier langsamer zu machen (dies beinhaltete Versuche, das JIT aufzuwärmen, indem es 10k Mal auf Funktionen vor dem Timing-Test aufgerufen wurde). Trotzdem bin ich PyPy sehr neu, also könnte ich etwas falsch machen. Möglicherweise mit Pyrex oder Cython würde größere Beschleunigungen ermöglichen.