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

Question

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

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

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

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

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:

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

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

Затраты на создание второго списка и т. Д. Явно заняли больше времени, чем поиск в более длинном списке. Оглядываясь назад, это был, вероятно, лучший подход, несмотря на то, что подход «сокращающий список» увеличил время первого запуска, что было наихудшим сценарием.

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

Answer 1

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

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'), и в этом случае он, вероятно, тратит большую часть своего времени, собирая большой список допустимых слов, и выигрывает от необходимости делать толькосканирование списка незначительно.Трудно сказать наверняка, но это немного академично, так как бинарный поиск все равно лучше.

Answer 2

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

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

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

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

Answer 3

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

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

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

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

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

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

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

Попытки могут быть полезны в задачах 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, вы бы просто прошли начать ['a'] ['b'], и это будут все слова, которые вы хотите.

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

Answer 4

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

sect () - это функция генератора, которая использует отличную идею Питера для использования 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 () вполне достаточно

Answer 5

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

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

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

Answer 6

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

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

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