Какой алгоритм для поиска подстрок в списке кортежей будет быстрее comprehension?

Question

[dadaniel]

Дано: Список из примерно 100k кортежей. Каждый кортеж состоит из двух элементов, первый id, а второй - строка. Нужно выбрать все id из тех кортежей, где строки содержат определенную подстроку.

tuples = [(id1, 'cheese trees'), (id2, 'freezy breeze'),...]
vals = ['cheese', 'flees']
ids = {i[0] for i in tuples if any(val in i[1] for val in vals)}

output: {id1}

Сейчас я это делаю через comprehension, но должно же быть более быстрое алгоритмическое решение! вот его-то я и ищу.

Comments

[o5a]

А что, сильно тормозит? Не должно на таких объемах.

Можно еще такой вариант попробовать, если список vals большой. Объединить в один шаблон regexp.

import re

rc = re.compile("|".join(vals))

ids = {i[0] for i in tuples if rc.search(i[1])}

[Andrey Dugin]

Слишком много неясностей. Что в вашем понимании быстро? И сколько раз будет запускаться алгоритм? Если один раз - вашего решения достаточно. Если много раз - нужно преобразовать в более эффективную с точки зрения структуру данных, вплоть до базы данных.

[dadaniel]

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

[o5a]

dadaniel, а сколько занимает предложенное через regexp?

Answer 1

[Wataru]

Алгоритм Ахо-Корасика.

Все ваши ключи складываете в бор, как описано по ссылке. Потом для каждого кортежа выполняйте поиск в строке i[1], если нашли, то добавляйте ваш id в ответ.

Comments

[dadaniel]

Насколько я понимаю, он для того чтобы находить быстро все вхождения строк-образцов (needles) в какую-то произвольной длины строку. То есть в моем случае он может заменить только фрагмент any(val in i[1] for val in vals) который и так исполняется весьма быстро.

[Wataru]

dadaniel, Всмысле, этот отрезок выполняется быстро? Что же у вас тогда тормозит-то?

Сам comprehension это просто синтаксический сахар для прохода по списку и составления нового списка.

При реализации Ахо-Корасика, вам придется ровно один раз просматривать все символы во всех кортежах. Быстрее сложно.

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

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

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

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

[dadaniel]

спасибо! попробую сделать дерево, а пока воспользуюсь Ахо-Корасиком.