@dadaniel
бэкенд разработчик, питон и С++

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

Дано: Список из примерно 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, но должно же быть более быстрое алгоритмическое решение! вот его-то я и ищу.
  • Вопрос задан
  • 156 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Алгоритм Ахо-Корасика.

Все ваши ключи складываете в бор, как описано по ссылке. Потом для каждого кортежа выполняйте поиск в строке i[1], если нашли, то добавляйте ваш id в ответ.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
@bacon
Создать "поисковый" индекс этих строк, можно заморочиться самими, но проще положить это в базу и там создать индекс.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
iChar Санкт-Петербург
от 120 000 до 180 000 ₽
от 80 000 до 120 000 ₽
24 янв. 2021, в 01:39
12000 руб./за проект
24 янв. 2021, в 01:30
1000000 руб./за проект
24 янв. 2021, в 00:56
40000 руб./за проект