Быстрое/Оптимизация реализации N-грамм в python

Question

Какая реализация ngram выполняется быстрее всего на python?

Я пытался АНКЕТА NLTK против молнии Скотта (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 

Есть ли быстрее реализация для генерации ngrams в Python?

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 является самым быстрым для мои тесты. Кажется, что небольшая выгода от hardcoding и от использования итераторов, если они используются повсюду (по крайней мере для этого значения параметра). Мы видим преимущества итераторов в большей разнице между zipngram2 и zipngram3 за n=2.

Я также попытался получить импульс от использования PyPy, но он, похоже, на самом деле замедляет работу здесь (сюда включались попытки разогреть JIT, называя его 10k раз на функции перед выполнением теста времени). Тем не менее, я очень новичок в PyPy, поэтому я могу делать что-то неправильно. Возможно, использование Pyrex или Cython позволит увеличить ускорения.