Что самый эффективный путь состоит в том, чтобы найти одной из нескольких подстрок в Python?
Вот полностью аннотированный пример в виде выражения функции:
const sum: ({
arg1,
arg2,
arg3
}: {
arg1: number;
arg2: number;
arg3: number;
}) => number = ({ arg1, arg2, arg3 }) => arg1 + arg2 + arg3;
Вот еще одна и лучшая альтернатива для функций со стрелками. Аннотируются только аргументы, и компилятор может правильно определить тип возвращаемого значения. Функция имеет меньше помех и работает так же, как и раньше.
const sum = ({
arg1,
arg2,
arg3
}: {
arg1: number;
arg2: number;
arg3: number;
}) => arg1 + arg2 + arg3;
Если вы собираетесь аннотировать свою функцию в отдельном файле:
interface Args {
arg1: number;
arg2: number;
arg3: number;
}
type Sum = (input: Args) => number;
const sum: Sum = ({ arg1, arg2, arg3 }) => arg1 + arg2 + arg3;
Вы можете использовать any в качестве типа аргумента, если типы аргументов неизвестны. Тип возвращаемого значения будет выводиться как любой:
const sum = ({
arg1,
arg2,
arg3
}: any) => arg1 + arg2 + arg3;
Так что этот эквивалент эквивалентен предыдущему примеру:
const sum: ({ arg1, arg2, arg3 }: any) => any
Это может не иметь особого смысла для функций стрелок, но вы можете устанавливать типы для известных аргументов и использования пар ключ-значение для аннотирования дополнительных аргументов:
const sum = ({
arg1,
arg2,
arg3
}: {
arg1: number;
arg2: number;
arg3: number;
[key: string]: number;
}) => arg1 + arg2 + arg3;
Вы также можете использовать обобщения:
interface Args {
arg1: number;
arg2: number;
arg3: number;
}
const sum = <T extends Args>({
arg1,
arg2,
arg3
}: T) => arg1 + arg2 + arg3;
Вот те же примеры, сумма как оператор функции. [1117 ]
function sum({
arg1,
arg2,
arg3
}: {
arg1: number;
arg2: number;
arg3: number;
}): number {
return arg1 + arg2 + arg3;
}
Если у вас есть сложные детали реализации в теле вашей функции, оператор функции может быть лучшим выбором для ее эргономики. Плюс дженерики выглядят менее неуклюже в выражениях функций.
6 ответов
I would assume a regex is better than checking for each substring individually because conceptually the regular expression is modeled as a DFA, and so as the input is consumed all matches are being tested for at the same time (resulting in one scan of the input string).
So, here is an example:
import re
def work():
to_find = re.compile("cat|fish|dog")
search_str = "blah fish cat dog haha"
match_obj = to_find.search(search_str)
the_index = match_obj.start() # produces 5, the index of fish
which_word_matched = match_obj.group() # "fish"
# Note, if no match, match_obj is None
UPDATE: Some care should be taken when combining words in to a single pattern of alternative words. The following code builds a regex, but escapes any regex special characters and sorts the words so that longer words get a chance to match before any shorter prefixes of the same word:
def wordlist_to_regex(words):
escaped = map(re.escape, words)
combined = '|'.join(sorted(escaped, key=len, reverse=True))
return re.compile(combined)
>>> r.search('smash atomic particles').span()
(6, 10)
>>> r.search('visit usenet:comp.lang.python today').span()
(13, 29)
>>> r.search('a north\south division').span()
(2, 13)
>>> r.search('012cat').span()
(3, 6)
>>> r.search('0123dog789cat').span()
(4, 7)
END UPDATE
It should be noted that you will want to form the regex (ie - call to re.compile()) as little as possible. The best case would be you know ahead of time what your searches are (or you compute them once/infrequently) and then save the result of re.compile somewhere. My example is just a simple nonsense function so you can see the usage of the regex. There are some more regex docs here:
http://docs.python.org/library/re.html
Hope this helps.
UPDATE: I am unsure about how python implements regular expressions, but to answer Rax's question about whether or not there are limitations of re.compile() (for example, how many words you can try to "|" together to match at once), and the amount of time to run compile: neither of these seem to be an issue. I tried out this code, which is good enough to convince me. (I could have made this better by adding timing and reporting results, as well as throwing the list of words into a set to ensure there are no duplicates... but both of these improvements seem like overkill). This code ran basically instantaneously, and convinced me that I am able to search for 2000 words (of size 10), and that and of them will match appropriately. Here is the code:
import random
import re
import string
import sys
def main(args):
words = []
letters_and_digits = "%s%s" % (string.letters, string.digits)
for i in range(2000):
chars = []
for j in range(10):
chars.append(random.choice(letters_and_digits))
words.append(("%s"*10) % tuple(chars))
search_for = re.compile("|".join(words))
first, middle, last = words[0], words[len(words) / 2], words[-1]
search_string = "%s, %s, %s" % (last, middle, first)
match_obj = search_for.search(search_string)
if match_obj is None:
print "Ahhhg"
return
index = match_obj.start()
which = match_obj.group()
if index != 0:
print "ahhhg"
return
if words[-1] != which:
print "ahhg"
return
print "success!!! Generated 2000 random words, compiled re, and was able to perform matches."
if __name__ == "__main__":
main(sys.argv)
UPDATE: It should be noted that the order of of things ORed together in the regex matters. Have a look at the following test inspired by TZOTZIOY:
>>> search_str = "01catdog"
>>> test1 = re.compile("cat|catdog")
>>> match1 = test1.search(search_str)
>>> match1.group()
'cat'
>>> match1.start()
2
>>> test2 = re.compile("catdog|cat") # reverse order
>>> match2 = test2.search(search_str)
>>> match2.group()
'catdog'
>>> match2.start()
2
This suggests the order matters :-/. I am not sure what this means for Rax's application, but at least the behavior is known.
UPDATE: I posted this questions about the implementation of regular expressions in Python which will hopefully give us some insight into the issues found with this question.
subs = ['cat', 'fish', 'dog']
sentences = ['0123dog789cat']
import re
subs = re.compile("|".join(subs))
def search():
for sentence in sentences:
result = subs.search(sentence)
if result != None:
return (result.group(), result.span()[0])
# ('dog', 4)
Это расплывчатый теоретический ответ без кода, но я надеюсь, что он укажет вам правильное направление.
Во-первых, вам понадобится более эффективный поиск по списку подстрок. , Я бы порекомендовал какую-то древовидную структуру. Начните с корня, затем добавьте узел 'a' , если какие-либо подстроки начинаются с 'a' , добавьте узел 'b' , если какие-либо подстроки начинаются с 'b' и так далее. Для каждого из этих узлов продолжайте добавлять подузлы.
Например, если у вас есть подстрока со словом «муравей», у вас должен быть корневой узел, дочерний узел 'a' , внучатый узел 'n' и узел правнука 't' .
Узлы должны быть достаточно простыми в создании.
class Node(object):
children = []
def __init__(self, name):
self.name = name
где имя - это символ.
Перебирайте строки по буквам. Следите за тем, на какой букве вы находитесь. В каждой букве попробуйте использовать следующие несколько букв, чтобы пройти по дереву. Если вы добьетесь успеха, ваш буквенный номер будет позицией подстроки, а ваш порядок обхода будет указывать на найденную подстроку.
Уточняющее редактирование: DFA должны быть намного быстрее, чем этот метод, поэтому я должен одобрить Ответ Тома . Я держу этот ответ только на тот случай, если ваш список подстрок часто меняется, и в этом случае использование дерева может быть быстрее.
В случае успеха ваш буквенный номер будет позицией подстроки, а ваш порядок обхода будет указывать на найденную подстроку.Уточняющее редактирование: DFA должны быть намного быстрее, чем этот метод, и поэтому я должен одобрить Tom's ответ . Я держу этот ответ только на тот случай, если ваш список подстрок часто меняется, и в этом случае использование дерева может быть быстрее.
В случае успеха ваш буквенный номер будет позицией подстроки, а ваш порядок обхода будет указывать на найденную подстроку.Уточняющее редактирование: DFA должны быть намного быстрее, чем этот метод, поэтому я должен одобрить Tom's ответ . Я держу этот ответ только на тот случай, если ваш список подстрок часто меняется, и в этом случае использование дерева может быть быстрее.
First of all, I would suggest you to sort the initial list in ascending order. Because scanning for a shorter substring is faster that scanning for a longer substring.
Как насчет этого.
>>> substrings = ['cat', 'fish', 'dog']
>>> _string = '0123dog789cat'
>>> found = map(lambda x: (_string.index(x), x), filter(lambda x: x in _string, substrings))
[(10, 'cat'), (4, 'dog')]
>>> if found:
>>> min(found, key=lambda x: x[0])
(4, 'dog')
Очевидно, вы могли бы вернуть что-то, кроме кортежа.
Это работает следующим образом:
- Фильтрация списка подстрок до тех, которые находятся в строка
- Создание списка кортежей, содержащих индекс подстроки, и подстроки
- Если подстрока была найдена, найдите минимальное значение на основе индекса
Я просто хочу указать на разницу во времени между ответом DisplacedAussie и ответом Тома. Оба были быстрыми при однократном использовании, поэтому у вас не должно быть заметного ожидания ни того, ни другого, но когда вы рассчитываете их:
import random
import re
import string
words = []
letters_and_digits = "%s%s" % (string.letters, string.digits)
for i in range(2000):
chars = []
for j in range(10):
chars.append(random.choice(letters_and_digits))
words.append(("%s"*10) % tuple(chars))
search_for = re.compile("|".join(words))
first, middle, last = words[0], words[len(words) / 2], words[-1]
search_string = "%s, %s, %s" % (last, middle, first)
def _search():
match_obj = search_for.search(search_string)
# Note, if no match, match_obj is None
if match_obj is not None:
return (match_obj.start(), match_obj.group())
def _map():
search_for = search_for.pattern.split("|")
found = map(lambda x: (search_string.index(x), x), filter(lambda x: x in search_string, search_for))
if found:
return min(found, key=lambda x: x[0])
if __name__ == '__main__':
from timeit import Timer
t = Timer("_search(search_for, search_string)", "from __main__ import _search, search_for, search_string")
print _search(search_for, search_string)
print t.timeit()
t = Timer("_map(search_for, search_string)", "from __main__ import _map, search_for, search_string")
print _map(search_for, search_string)
print t.timeit()
Выходы:
(0, '841EzpjttV')
14.3660159111
(0, '841EzpjttV')
# I couldn't wait this long
Я бы согласился с ответом Тома, как по удобочитаемости, так и по скорости.