在python中快速/優化N-gram實現

Question

哪個ngram實現在python中最快？

我試着來分析NLTK的VS斯科特的拉鍊（http://locallyoptimal.com/blog/2013/01/20/elegant-n-gram-generation-in-python/）：

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 

[出]

0.000213146209717 
6.50882720947e-05 

是否有在python產生的n-gram任何更快的實現？

Answer 1

一些分析的嘗試。我認爲使用發電機可以提高這裏的速度。但與原始版本的輕微修改相比，改進並不明顯。但是如果你不需要同時完整的列表，那麼生成器函數應該更快。

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

對於此測試數據，zipngram2和zipngram3似乎是最快的一個良好的邊緣。

Answer 2

擴展M4rtini's code，我做了另外三個版本，一個硬編碼n=2參數：

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

使用timeit，我得到這些結果：

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是最快的我的測試。對於硬編碼以及使用迭代器（如果它們在整個過程中一直使用）（至少對於此參數值）似乎有一點好處。我們在zipngram2和zipngram3之間看到n=2的迭代器的好處。

我也嘗試過使用PyPy，但它似乎實際上讓事情變慢了（這包括嘗試通過在進行定時測試之前調用10k次函數來預熱JIT）。儘管如此，我對PyPy很陌生，所以我可能做錯了什麼。可能使用Pyrex或Cython可以實現更高的速度。