Проверьте, если несколько списков содержать элемент из большого внешнего списка


У меня есть список списков (многие tokenised предложений). Для тех, кто не знает, что tokenised предложения, мой список выглядит так:

list1 = [['hello', 'my', 'name'], ['this', 'is', 'stack', 'exchange'], ... ]

У меня есть список ключевых слов, key_words.

За каждым предложением в listЯ хочу проверить, если он находится в key_words. Кроме того, я хочу, чтобы один метод должен применяться в каждом предложении. Ниже-это моя работа (но неэффективно) код:

list1 = [['hello', 'my', 'name'], ['this', 'is', 'stack', 'exchange']]
key_words = ['hello', 'name', 'stack']    

def get_features(sentence, key_words):
    return [word for word in sentence if word in key_words]

f = []
for sent in list1:
    f.append(get_features(sent, key_words))

Это прекрасно, но мои размеры вот так:

len(list1) = 45,000
len(key_words) = 35,000

Это, конечно, неэффективно, и я хотел бы найти более быстрый способ сделать это. Словари могут быть использованы каким-то образом? Я думал изменить key_words из списка в словарь ключ:значение = слово:1. Тогда я мог бы сделать что-то подобное

return [word for word in sentence if key_words[word] does not give error]

но я не знаю, как if does not give error будут реализованы. Делать это позволит за O(1) доступ к словам в key_words если они действительно есть, вместо того, чтобы искать весь список, пока он не найден, с O(N) времени.



1932
5
задан 15 марта 2018 в 03:03 Источник Поделиться
Комментарии
1 ответ

В этом вопросе, и, как полагают Матиас Эттингер, обоснование поиске \$О(1)\$ поиск по времени-сложность в отличии от нынешних \$О(П)\$ сложность-это правильно.

Однако, лучший подход заключается в использовании структуры набора данных, а не структуру списка. Наборы \$О(1)\$ выдаче временной сложности, так как они реализуются с помощью хэш-таблиц (https://wiki.python.org/moin/TimeComplexity) и они похожи на список концептуально, и таким образом принять гораздо больше смысла, чем усложнять с помощью словаря.

Код (с больших габаритов, указанных в вопросе) выполняется за 10 секунд, как так:

list1 = [['hello', 'my', 'name'], ['this', 'is', 'stack', 'exchange']]
key_words = ['hello', 'name', 'stack']

def get_features(sentence, key_words):
return [word for word in sentence if word in key_words]

f = []
key_words = set(key_words)
for sent in list1:
f.append(get_features(sent, key_words))

3
ответ дан 15 марта 2018 в 03:03 Источник Поделиться