Эффективный на Python способ проверить, содержит ли очень большая строка подстроку

Question

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

if small_string in large_string:
    # logic here

Но это кажется очень неэффективным, потому что он проверит каждую возможную последовательность символов в файле. Я знаю, что будет только точное совпадение на новой строке, поэтому было бы лучше прочитать файл в виде списка и выполнить итерацию по этому списку для сопоставления?

РЕДАКТИРОВАТЬ: Чтобы устранить путаницу при «совпадении только на новой строке», вот пример:

small_string = "This is a line"
big_string = "This is a line\nThis is another line\nThis is yet another"

Если я не ошибаюсь, ключевое слово in проверит все последовательности, а не только каждую строку.

Answer 1

Это действительно медленно?Вы говорите о строке 30 МБ;давайте попробуем это с еще большей строкой:

In [12]: string="agu82934u"*50*1024*1024+"string to be found"

In [13]: len(string)
Out[13]: 471859218

In [14]: %timeit "string to be found" in string
1 loops, best of 3: 335 ms per loop

In [15]: %timeit "string not to be found" in string
1 loops, best of 3: 200 ms per loop

Я бы не сказал, что 335 мс - это много времени на поиск подстроки в строке 450 МБ.

Answer 2

Как медленно, слишком медленно?Я только что сделал a in b тест для уникальной строки в конце строки 170 МБ.Это закончилось до того, как мой палец покинул клавишу ввода.

Answer 3

Я не вижу, как сделать это более оптимальным при сравнении, если честно. Но вы можете использовать меньше памяти и тратить меньше времени на ввод-вывод, если читаете файл построчно:

has_small_string = False
for line in large_file:
    if small_string in line:
        has_small_string = True
        break
if has_small_string:
   # ... Your stuff here ...

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

Answer 4

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

• Алгоритм поиска строки Рабина-Карпа

• Алгоритм Кнута-Морриса-Пратта (он же KMP) видит реализацию здесь

Хотя я считаю, что KMP более эффективен, его сложнее реализовать.Первая ссылка включает в себя некоторый псевдокод, который должен очень легко реализовать в python.

Вы можете найти альтернативы здесь: http://en.wikipedia.org/wiki/String_searching_algorithm

Answer 5

Если вы просто хотите проверить, существует ли эта подстрока,

for line in open("file"):
    if substring in line:
         print "exists"
         sys.exit() # or break to do some other stuff

Answer 6

Вы подразумеваете, что будет соответствовать только полная строка?(Ваша РЕДАКТИРОВАТЬ: сопоставление только с примером новой строки, кажется)

Тогда я представляю

for line in open('file').readlines():
  if line==small_string:
    return True
return False

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

будет лучше.

Answer 7

small_string = "This is a line"
big_string = "This is a line This is another line\nThis is yet another"

test= big_string.split("This is a line" ,1)

if len(test)==2:

    print "it`s there"

elif len(test)!=2:

    print "it`s not"

Answer 8

Я бы рассчитывал на быструю реализацию кем-то другим:

import subprocess
from subprocess import STDOUT
import os

...
with open(os.devnull, 'w') as devnull:
    if subprocess.call('grep %s "%s"' % (smallstring, file), shell=True, stdout=devnull, stderr=STDOUT) == 0:
        pass #do stuff

Не работает на Windows.

edit: Я волнуюсь, что grep возвращает 0, найдет он что-нибудь или нет. Но у меня сейчас нет никакой оболочки, поэтому я не могу ее протестировать.