У меня есть список со многими словами (100. 000+), и я хотел бы удалить все подстроки каждого слова в списке.
Поэтому для простоты предположим, что у меня есть следующий список:
words = ['Hello', 'Hell', 'Apple', 'Banana', 'Ban', 'Peter', 'P', 'e']
Требуется следующий вывод:
['Hello', 'Apple', 'Banana', 'Peter']
'Hell' был удален, потому что это подстрока 'Hello''Ban' был удален, потому что это подстрока 'Banana''P' был удален, потому что это подстрока 'Peter''e' был удален, потому что это подстрока 'Hello', 'Hell', 'Apple' и т.д.Что я сделал
Это мой код, но мне интересно, есть ли более эффективный способ, чем эти вложенные методы.
to_remove = [x for x in words for y in words if x != y and x in y]
output = [x for x in words if x not in to_remove]
Как я могу улучшить производительность? Должен ли я использовать regex?
@wim является правильным.
Учитывая алфавит фиксированной длины, следующий алгоритм является линейным по всей длине текста. Если алфавит имеет неограниченный размер, тогда он будет O(n log(n)). В любом случае это лучше, чем O(n^2).
Create an empty suffix tree T.
Create an empty list filtered_words
For word in words:
if word not in T:
Build suffix tree S for word (using Ukkonen algorithm)
Merge S into T
append word to filtered_words
Сначала создайте набор всех (уникальных) подстрок, затем отфильтруйте слова с ним:
def substrings(s):
length = len(s)
return {s[i:j + 1] for i in range(length) for j in range(i, length)} - {s}
def remove_substrings(words):
subs = set()
for word in words:
subs |= substrings(word)
return set(w for w in words if w not in subs)
Вы можете сортировать данные по длине, а затем использовать список:
words = ['Hello', 'Hell', 'Apple', 'Banana', 'Ban', 'Peter', 'P', 'e']
new_words = sorted(words, key=len, reverse=True)
final_results = [a for i, a in enumerate(new_words) if not any(a in c for c in new_words[:i])]
Выход:
['Banana', 'Hello', 'Apple', 'Peter']
Обратите внимание, что использование for в пионе вообще медленное (вы можете использовать массивы numpy или пакет NLP), кроме этого, как насчет этого:
words = list(set(words))#elimnate dublicates
str_words = str(words)
r=[]
for x in words:
if str_words.find(x)!=str_words.rfind(x):continue
else:r.append(x)
print(r)
как я отвечаю здесь, я не вижу причины, почему c++ не был бы вариантом