Подтвердить что ты не робот

Самый быстрый способ в Python найти подстроку "startswith" в длинном отсортированном списке строк

Я сделал много Googling, но ничего не нашел, поэтому мне очень жаль, если я просто искал неправильные вещи.

Я пишу реализацию Ghost для MIT Введение в программирование, назначение 5.

Как часть этого, мне нужно определить, является ли строка символов началом любого действительного слова. У меня есть список допустимых слов ( "список слов" ).

Обновление: я мог бы использовать что-то, что повторялось в списке каждый раз, например, простое предложение Peter:

def word_exists(wordlist, word_fragment):
return any(w.startswith(word_fragment) for w in wordlist)

Я ранее имел:

wordlist = [w for w in wordlist if w.startswith(word_fragment)]

(из здесь), чтобы сузить список до списка допустимых слов, начинающихся с этого фрагмента, и считать потерю, если список слов пуст. Причина, по которой я использовал этот подход, заключалась в том, что я (неправильно, см. Ниже) думал, что это сэкономит время, так как последующие поиски должны были бы искать меньший список.

Мне пришло в голову, что это происходит через каждый элемент в исходном списке слов (38 000 с лишним слов), проверяющих начало каждого из них. Это кажется глупым, когда список слов упорядочен, и понимание может прекратиться, как только оно ударит то, что после фрагмента слова. Я пробовал это:

newlist = []
for w in wordlist:
    if w[:len(word_fragment)] > word_fragment:
        # Take advantage of the fact that the list is sorted
        break
    if w.startswith(word_fragment):
        newlist.append(w)
return newlist

но это примерно такая же скорость, которая, как я думал, может быть потому, что в списках понимаются как скомпилированный код?

Затем я подумал, что более эффективным будет некоторая форма бинарного поиска в списке, чтобы найти блок совпадающих слов. Это путь, или я пропущу что-то действительно очевидное?

Ясно, что в этом случае это не очень важно, но я только начинаю программировать и хочу делать что-то правильно.

UPDATE:

С тех пор я проверил приведенные ниже предложения с помощью простого теста script. Хотя бинарный поиск Peter/bisect, очевидно, был бы лучше для одного прогона, меня интересовал, победит ли список сужений над несколькими фрагментами. На самом деле это не так:

The totals for all strings "p", "py", "pyt", "pyth", "pytho" are as follows:
In total, Peter simple test took 0.175472736359
In total, Peter bisect left test took 9.36985015869e-05
In total, the list comprehension took 0.0499348640442
In total, Neil G bisect took 0.000373601913452

Накладные расходы на создание второго списка и т.д. явно занимали больше времени, чем поиск более длинного списка. Оглядываясь назад, это, вероятно, лучший подход, независимо от того, как подход "сокращенного списка" увеличил время для первого запуска, что было наихудшим сценарием.

Спасибо всем за отличные предложения, и хорошо сделал Питер за лучший ответ!!!

4b9b3361

ОТВЕТЫ

Ответ 1

Выражения генератора оцениваются лениво, поэтому, если вам нужно только определить, действительно ли ваше слово действительно, я ожидаю, что следующее будет более эффективным, поскольку оно не обязательно заставляет его создавать полный список, как только он найдет матч:

def word_exists(wordlist, word_fragment):
    return any(w.startswith(word_fragment) for w in wordlist)

Обратите внимание, что для этого важно, чтобы отсутствовали квадратные скобки.

Однако это, очевидно, все еще линейно в худшем случае. Вы правы, что бинарный поиск будет более эффективным; вы можете использовать для этого встроенный модуль bisect. Это может выглядеть примерно так:

from bisect import bisect_left
def word_exists(wordlist, word_fragment):
    try:
        return wordlist[bisect_left(wordlist, word_fragment)].startswith(word_fragment)
    except IndexError:
        return False # word_fragment is greater than all entries in wordlist

bisect_left работает в O (log (n)), поэтому будет значительно быстрее для большого списка слов.

Изменить: я бы предположил, что приведенный вами пример проиграет, если ваш word_fragment является чем-то действительно распространенным (например, 't'), и в этом случае он, вероятно, большую часть времени проводит сбор большого списка допустимых слов, а коэффициент усиления из всего лишь частичного сканирования списка пренебрежимо мало. Трудно сказать наверняка, но это немного академический, так как бинарный поиск в любом случае лучше.

Ответ 2

Вы правы, что можете сделать это более эффективно, учитывая, что список отсортирован.

Я строю ответ @Peter, который возвращает один элемент. Я вижу, что вы хотите, чтобы все слова начинались с заданного префикса. Вот как вы это делаете:

from bisect import bisect_left
wordlist[bisect_left(wordlist, word_fragment):
         bisect_left(wordlist, word_fragment[:-1] + chr(ord(word_fragment[-1])+1))]

Это возвращает срез из исходного отсортированного списка.

Ответ 3

Как сказал Питер, я бы использовал модуль Bisect. Особенно, если вы читаете из большого файла слов.

Если вам действительно нужна скорость, вы можете сделать демона (Как создать демон в Python?), который имеет предварительно обработанную структуру данных, подходящую для задачи

Я предлагаю вам использовать "попытки"

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=usingTries

Существует множество алгоритмов и структур данных для индексации и поиска строки внутри текста, некоторые из них включены в стандарт библиотеки, но не все из них; структура данных trie является хорошей пример того, что нет.

Пусть слово является одной строкой и пусть словарь представляет собой большой набор слова. Если у нас есть словарь, и нам нужно знать, если одно слово внутри словаря попытки представляют собой структуру данных, которая может Помоги нам. Но вы можете спросить себя: "Зачем использовать попытки, если они установлены  и хэш-таблицы могут делать то же самое?" Есть две основные причины:

  • Попытки могут вставлять и находить строки в O (L) времени (где L представляет длина одного слова). Это намного быстрее, чем установлено, но это бит быстрее, чем хеш-таблица.
  • Набор и хэш-таблицы может найти только словаря, которые точно соответствуют одному слово, которое мы находим; trie позволяет нам находить слова, которые имеют отдельный символ, общий префикс, отсутствующий символ, и т.д.

Попытки могут быть полезны в проблемах TopCoder, но также имеют большое количество приложений в разработке программного обеспечения. Например, рассмотрите веб-браузер. Вы знаете, как веб-браузер может автоматически заполнить текст или показать вам много возможностей текста, который вы может написать? Да, с trie вы можете сделать это очень быстро. Вы знать, как орфографический корректор может проверить, что каждое слово, которое вы Тип находится в словаре? Опять трю. Вы также можете использовать trie для предлагаемые исправления слов, которые присутствуют в тексте, но не в словаре.

пример:

start={'a':nodea,'b':nodeb,'c':nodec...}
nodea={'a':nodeaa,'b':nodeab,'c':nodeac...}
nodeb={'a':nodeba,'b':nodebb,'c':nodebc...}
etc..

тогда, если вы хотите, чтобы все слова, начинающиеся с ab, вы просто проходили start ['a'] ['b'], и это все, что вы хотите.

чтобы создать его, вы можете выполнять итерацию через свой список слов и для каждого слова, итерации по символам, добавляя новый по умолчанию dict, где требуется.

Ответ 4

В случае двоичного поиска (при условии, что список слов отсортирован), я думаю о чем-то вроде этого:

wordlist = "ab", "abc", "bc", "bcf", "bct", "cft", "k", "l", "m"
fragment = "bc"
a, m, b = 0, 0, len(wordlist)-1
iterations = 0

while True:
    if (a + b) / 2 == m: break # endless loop = nothing found
    m = (a + b) / 2
    iterations += 1
    if wordlist[m].startswith(fragment): break # found word
    if wordlist[m] > fragment >= wordlist[a]: a, b = a, m
    elif wordlist[b] >= fragment >= wordlist[m]: a, b = m, b

if wordlist[m].startswith(fragment):
    print wordlist[m], iterations
else:
    print "Not found", iterations

Он найдет одно совпадающее слово или нет. Затем вам нужно будет взглянуть влево и вправо, чтобы найти другие совпадающие слова. Мой алгоритм может быть неправильным, его просто грубая версия моих мыслей.

Ответ 5

Вот мой самый быстрый способ сузить список wordlist до списка допустимых слов, начинающихся с данного фрагмента:

sect() - это функция генератора, которая использует отличную идею Peter для использования bisect и функции islice():

from bisect import bisect_left
from itertools import islice

from time import clock

A,B = [],[]


iterations = 5
repetition = 10

with open('words.txt') as f:
    wordlist = f.read().split()

wordlist.sort()
print 'wordlist[0:10]==',wordlist[0:10]


def sect(wordlist,word_fragment):
    lgth = len(word_fragment)
    for w in islice(wordlist,bisect_left(wordlist, word_fragment),None):
        if w[0:lgth]==word_fragment:
            yield w
        else:
            break


def hooloo(wordlist,word_fragment):
    usque = len(word_fragment)
    for w in wordlist:
        if w[:usque] > word_fragment:
            break
        if w.startswith(word_fragment):
            yield w


for rep in xrange(repetition):
    te = clock()
    for i in xrange(iterations):
        newlistA = list(sect(wordlist,'VEST'))
    A.append(clock()-te)

    te = clock()
    for i in xrange(iterations):
        newlistB = list(hooloo(wordlist,'VEST'))
    B.append(clock() - te)


print '\niterations =',iterations,'   number of tries:',repetition,'\n'
print newlistA,'\n',min(A),'\n'
print newlistB,'\n',min(B),'\n'

результат

wordlist[0:10]== ['AA', 'AAH', 'AAHED', 'AAHING', 'AAHS', 'AAL', 'AALII', 'AALIIS', 'AALS', 'AARDVARK']

iterations = 5    number of tries: 30 

['VEST', 'VESTA', 'VESTAL', 'VESTALLY', 'VESTALS', 'VESTAS', 'VESTED', 'VESTEE', 'VESTEES', 'VESTIARY', 'VESTIGE', 'VESTIGES', 'VESTIGIA', 'VESTING', 'VESTINGS', 'VESTLESS', 'VESTLIKE', 'VESTMENT', 'VESTRAL', 'VESTRIES', 'VESTRY', 'VESTS', 'VESTURAL', 'VESTURE', 'VESTURED', 'VESTURES'] 
0.0286089433154 

['VEST', 'VESTA', 'VESTAL', 'VESTALLY', 'VESTALS', 'VESTAS', 'VESTED', 'VESTEE', 'VESTEES', 'VESTIARY', 'VESTIGE', 'VESTIGES', 'VESTIGIA', 'VESTING', 'VESTINGS', 'VESTLESS', 'VESTLIKE', 'VESTMENT', 'VESTRAL', 'VESTRIES', 'VESTRY', 'VESTS', 'VESTURAL', 'VESTURE', 'VESTURED', 'VESTURES'] 
0.415578236899

sect() в 14,5 раз быстрее holloo()

PS:

Я знаю существование timeit, но здесь для такого результата достаточно clock()

Ответ 6

Выполнение двоичного поиска в списке не гарантирует вам ничего. Я не уверен, как это будет работать.

У вас есть список, который заказан, это хорошая новость. Алгоритмическая сложность производительности обоих ваших случаев - это O (n), что неплохо, что вам просто нужно перебирать весь список слов один раз.

Но во втором случае производительность (инженерная производительность) должна быть лучше, потому что вы ломаетесь, как только обнаружите, что случаи отдыха не будут применяться. Попытайтесь иметь список, где 1-й элемент соответствует и остаётся 38000 - 1 элемент не соответствует, второй будет бить первый.