Проверьте, является ли элемент списка подэлементом элементов в другом списке с Python

Question

Учитывая следующие данные:

a = ["onee", "two", "three"]
b = ["one", "four"]

Я хотел бы для некоторого теста, такого как следующее:

[True if x in a else False for x in b]

Для возврата

[True, False]

Вместо

[False, False]

Итак, для каждого элемента в списке b я хочу посмотреть, является ли это подстрокой любого из элементов в списке a.

Один из способов сделать это можно следующим образом:

test = []
for elb in b:
    included = False
    for ela in a:
        if elb in ela:
            included = True
        break
    test.append(included)

Я не чувствую, что это очень хороший подход, возможно, есть понимание, которое может улучшить его?

Следующее также работает:

[True if any(elb in ela for ela in a) else False for elb in b]

Я просто думаю, что, вероятно, будет более хороший подход.

Answer 1

Прежде всего, этот

True if True else False

является избыточным. Так в твоем первом компе. Вы можете просто иметь: [x in a for x in b], аналогично, [any(elb in ela for ela in a) for elb in b].

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

Эффективность мудрая однако вы можете предварительно сгенерировать все возможные подстроки из всех строк в a, сохранив их в set.

Это будет означать, что сложность будет уменьшена с O(n*m*p), где n - это длина b, m - это длина a, а n - это средняя длина подстроки от a до просто O(n). Это связано с тем, что после создания набора подстрок поиска проверка определенного элемента в b является операцией O(1), поскольку вы проверяете включение в набор, а не O(m*p), где нужно проверять каждый подстрока каждого элемента в a.

Чтобы сгенерировать этот набор поиска подстроки, вы можете использовать следующее понимание набора:

a_substrings = {s[i:j] for s in a for i in range(len(s)) for j in range(i+1, len(s)+1)}

, тогда вы можете просто проверить in this :

[s in a_substrings for s in b]

, который дает ожидаемое [True, False] для ваших входов.

---

Это действительно быстрее?

Для небольших размеров a и b списки, затраты на создание набора поиска перевешивают преимущества возможности проверки каждого элемента в b. Кроме того, для вымогательски длинного списка a, содержащего длинный strings и даже умеренного размера b, он может снова оказаться медленнее, потратив время на просмотр всех подстрок a и создание поиска устанавливается, особенно если большинство элементов в b будут совпадать в первых нескольких строках a.

Однако в случаях, когда оба списка длинные, особенно важно, когда b длинный Ваш метод будет непрерывно генерировать и проверять одни и те же элементы a снова и снова для каждого элемента b. Очевидно, это медленнее, чем предварительный расчет подмножеств. Я предполагаю, что это, по сути, ключевая оптимизация поисковых систем - когда кто-то представляет запрос, он не начинает каждый раз перебирать веб-сайт с чистого листа, вместо этого он постоянно переоценивает все известные веб-сайты, конечно, в порядке популярности, так что они «готовы к go» при поступлении запроса.

Answer 2

Это еще один подход, с которым я столкнулся:

[x in "-".join(y for y in a) for x in b]

Объединение всех строк a в одну строку и проверка наличия элемента там.

Выходы:

[True, False]

Отказ от ответственности: Не уверен, что это именно "лучше", но, опять же, просто еще один подход.

Answer 3

Вы можете сделать:

>>> [ y.startswith(x) for x, y in zip(b,a)]
[True, False]
>>> 

Answer 4

Этого достаточно:

[ any(elb in ela for ela in a) for elb in b ]