python中Ngram的快速/优化实现

Question

python中哪个ngram实现最快？在

我试着介绍一下nltk和斯科特的zip（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

[退出]

^{pr2}$

在python中有没有更快的实现来生成ngram？在

Answer 1

扩展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，我得到以下结果：

^{pr2}$

bigram3是我测试中最快的。如果在整个过程中使用迭代器，那么硬编码和使用迭代器似乎确实有一点好处（至少对于这个参数值）。我们看到迭代器的好处在于zipngram2和{}之间更大的差异。在

我还尝试使用PyPy来提高效率，但实际上它似乎使事情变得更慢（这包括在进行计时测试之前尝试通过在函数上调用它10k次来预热JIT）。不过，我对PyPy还是个新手，所以我可能做错了什么。可能使用Pyrex或Cython可以实现更大的加速。在

Answer 2

一些尝试和一些分析。我以为使用发电机可以提高这里的速度。但与对原稿稍作修改相比，改进并不明显。但如果你不需要的话，你不需要在相同的时间里运行完整的函数。在

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似乎是最快的。在