Эффективный алгоритм шинглинга

Question

Я реализовал следующий алгоритм для извлечения групп из n слов из строки.

def ngrams(text, size):
    tokens = text.split()
    ngrams = []
    for char in range(len(tokens)):
        if (len(tokens)-char) < size:
            break
        list_shingle = tokens[char:char+size]
        str_shingle = ' '.join(list_shingle)
        ngrams.append(str_shingle)
    return ngrams

Строки имеют такую ​​форму:

['Hello my name is Inigo Montoya, you killed my father, prepare to die.']

Вывод должен выглядеть следующим образом:для размера 3 слова:

['Hello my name','my name is','name is Inigo',...,'prepare to die.']

Мне нужно сравнить большое количество документов, как я могу сделать этот код более эффективным?

Answer 1

Это не другой алгоритм, но он использует понимание списка вместо цикла:

def ngrams2(text, size):
    tokens = text.split()
    return [' '.join(tokens[i:i+size])
                     for i in range(len(tokens) - size + 1)]

По крайней мере, на моем компьютере изменение окупается:

$ python3 -m timeit -s 'from shingle import ngrams, ngrams2, text' 'ngrams(text, 3)'
1000 loops, best of 3: 501 usec per loop
$ python3 -m timeit -s 'from shingle import ngrams, ngrams2, text' 'ngrams2(text, 3)'
1000 loops, best of 3: 293 usec per loop

(text - это 10 Кбайт, сгенерированный https://www.lipsum.com/.. Содержит 1347 «слов» в одной строке.)