Найти иглу в стоге сена, что лучше?

Ответ 1

Я не думаю, что это можно сделать ниже (t20) с этим (потому что вам нужно прокручивать строку по крайней мере один раз). Вы можете сделать некоторые оптимизации.

Я предполагаю, что вы хотите совместить "целые слова", например, поиск foo должен совпадать следующим образом:

foo and foo, or foobar and not foo.
^^^     ^^^                    ^^^

Так что шинирование только на основе пространства не будет выполнять эту работу, потому что:

>>> 'foo and foo, or foobar and not foo.'.split(' ')
['foo', 'and', 'foo,', 'or', 'foobar', 'and', 'not', 'foo.']
#                  ^                                     ^

Здесь re модуль пригодится, что позволит вам создавать увлекательные условия. Например, \b внутри регулярного выражения означает:

Соответствует пустой строке, но только в начале или конце слова. Слово определяется как последовательность букв алфавитно-цифровых символов или символов подчеркивания Unicode, поэтому конец слова обозначается символом или символом Unicode без символа. Обратите внимание, что формально \b определяется как граница между символами a \w и a \w (или наоборот) или между \w и началом/концом строки. Это означает, что r'\bfoo\b' соответствует 'foo', 'foo.', '(foo)', 'bar foo baz', но не 'foobar' или 'foo3'.

So r'\bfoo\b' будет соответствовать только целому слову foo. Также не забудьте использовать re.escape():

>>> re.escape('foo.bar+')
'foo\\.bar\\+'
>>> r'\b{}\b'.format(re.escape('foo.bar+'))
'\\bfoo\\.bar\\+\\b'

Все, что вам нужно сделать, это использовать re.finditer() для сканирования строки. На основании документации:

Возвращает итератор, дающий объекты соответствия по всем совпадениям совпадений для шаблона RE в строке. Строка сканируется слева направо, а совпадения возвращаются в найденном порядке. Пустые совпадения включаются в результат, если они не касаются начала другого матча.

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

>>> r = re.compile(r'\bfoo\b')
>>> it = r.finditer('foo and foo, or foobar and not foo.')
>>> sum(1 for _ in it)
3

Ответ 2

Это не относится к проблеме сложности, но упрощает код:

def find_needle(n,h):
    return h.split().count(n)

Ответ 3

Вы можете использовать Counter

from collections import Counter

def find_needle(n,h):
    return Counter(h.split())[n]

i.e.:

n = "portugal"
h = 'lobito programmer from portugal hello fromportugal portugal'

print find_needle(n,h)

Вывод:

2

DEMO

Ответ 4

Собственно, когда вы говорите O (n), вы забываете о том, что после сопоставления первой буквы вам также нужно сопоставить оставшиеся (совпадение n от иглы к предложению, затем соответствие e, затем следующий e...) По сути, вы пытаетесь воспроизвести функциональность grep, поэтому вы можете посмотреть алгоритм grep. Вы можете сделать это, построив конечный автомат. Есть много ссылок, которые могут вам помочь, и вы можете начать с Как grep работает так быстро?

Ответ 5

Это все равно будет O (n), но он использует мощность выражений re и python.

import re

def find_needle(n,h):
    g = re.finditer(r'\b%s\b'%n, h)  # use regex word boundaries
    return sum(1 for _ in g)  # return the length of the iterator

Должно использовать гораздо меньше памяти, чем .split для относительно большой "стога сена".

Обратите внимание, что это не совсем то же самое, что и код в OP, потому что он не только найдет "иглу" , но также "иглу" и "иглу" . Он не найдет "иглы".

Ответ 6

Если вы беспокоитесь о времени, которое требуется (в отличие от временной сложности), многопроцессор. В основном сделать n меньше. Вот пример, чтобы запустить его в 2 процессах.

from multiprocessing import Process

def find(word, string):
    return string.count(word)

def search_for_words(word, string):
    full_length = len(string)
    part1 = string[:full_length/2]
    proc1 = Process(target=find, args=(word, part1,))
    proc1.start()
    part2 = string[full_lenght/2:]
    proc2 = Process(target=find, args=(word, part2,))
    proc2.start()
    proc1.join()
    proc2.join()

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

Ответ 7

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

Ответ 8

def find_needle(haystack):
    for item in haystack:
        if item  == 'needle':
            haystack.append(item)
            return 'found the needle at position ' + str(haystack.index(item))

Ответ 9

вот мой.

def find_needle(haystack, needle):
    return haystack.count(needele)

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