获取包含字符串元素的列表，不包括以初始列表中的任何其他元素为前缀的元素
Obtain a list containing string elements excluding elements prefixed with any other element from initial list
我在筛选字符串列表时遇到了一些问题。我发现了一个类似的问题 here 但不是我需要的。
输入列表为：
l = ['ab', 'xc', 'abb', 'abed', 'sdfdg', 'abfdsdg', 'xccc']
预期结果是
['ab', 'xc', 'sdfdg']
结果中项目的顺序并不重要
过滤功能必须很快，因为列表的大小
我目前的解决方案是
l = ['ab', 'xc', 'abb', 'abed', 'sdfdg', 'abfdsdg', 'xccc']
for i in range(0, len(l) - 1):
for j in range(i + 1, len(l)):
if l[j].startswith(l[i]):
l[j] = l[i]
else:
if l[i].startswith(l[j]):
l[i] = l[j]
print list(set(l))
编辑
经过大量输入数据的多次测试，列出 1500000 个字符串，我最好的解决方案是：
def filter(l):
if l==[]:
return []
l2=[]
l2.append(l[0])
llen = len(l)
k=0
itter = 0
while k<llen:
addkelem = ''
j=0
l2len = len(l2)
while j<l2len:
if (l2[j].startswith(l[k]) and l[k]!= l2[j]):
l2[j]=l[k]
l.remove(l[k])
llen-=1
j-=1
addkelem = ''
continue
if (l[k].startswith(l2[j])):
addkelem = ''
break
elif(l[k] not in l2):
addkelem = l[k]
j+=1
if addkelem != '':
l2.append(addkelem)
addkelem = ''
k+=1
return l2
执行时间约为 213 秒
Sample imput data - 每行是列表中的一个字符串
使用reduce函数的解决方案：
def r(a, b):
if type(a) is list:
if len([z for z in a if b.startswith(z)]) == 0:
a.append(b)
return a
if a.startswith(b):
return b
if b.startswith(a):
return a
return [a, b]
print reduce(r, l)
估计[z for z in a if b.startswith(z)]部分可以进一步优化
编辑3
经过一番冥想，我写了这个算法。它比基于 Padraic Cunningham 提供的大随机数据集的基于 reduce 的方法快 1k 倍（感谢提供数据集）。该算法具有 ~ O(nlogn) 的复杂性，尽管还有一些 space 用于较小的优化。它的内存效率也很高。大约需要额外 n space。
def my_filter(l):
q = sorted(l, reverse=True)
first = q.pop()
addfirst = True
while q:
candidate = q.pop()
if candidate == first:
addfirst = False
continue
if not candidate.startswith(first):
if addfirst:
yield first
first, addfirst = candidate, True
if addfirst:
yield first
Edit2 这个东西在我的测试中和基于reduce的算法一样快，但是这个比较取决于使用的数据集。我只是将教科书页面解析为单词。该算法基于以下观察。令 A、B 和 C 为字符串，len(A) < min(len(B), len(C))。请注意，如果 A 是 B 的前缀，则检查 A 是否是 C 的前缀就足以说明存在 C 的前缀。
def my_filter(l):
q = sorted(l, key=len)
prefixed = []
while q:
candidate = q.pop()
if any(candidate.startswith(prefix) for prefix in prefixed):
continue
if any(candidate.startswith(string) for string in q):
prefixed.append(candidate)
else:
yield candidate
原版post
这是我提出的原始算法。事实上，它是您算法的简明版本。
l = ['ab', 'xc', 'abb', 'abed', 'sdfdg', 'abfdsdg', 'xccc']
res = [string for string in l if sum(not string.startswith(prefix) for prefix in l) == len(l)-1]
演示>>>
print res
# ['ab', 'xc', 'sdfdg']
lst = ['ab', 'xc', 'abb', 'abed', 'sdfdg', 'abfdsdg', 'xccc']
result = []
for element in lst:
is_prefixed = False
for possible_prefix in lst:
if element is not possible_prefix and element.startswith(possible_prefix):
is_prefixed = True
break
if not is_prefixed:
result.append(element)
这是一些实验性的多线程版本：
好好测试一下！
import thread
import math
import multiprocessing
list = ['ab', 'xc', 'abb', 'abed', 'sdfdg', 'abfdsdg', 'xccc']
def get_results(list, thread_num, num_of_threads):
result = []
part_size = int(math.ceil(len(list) * 1.0 / num_of_threads))
for element in list[part_size * thread_num: part_size * (thread_num + 1)]:
is_prefixed = False
for possible_prefix in list:
if element is not possible_prefix and element.startswith(possible_prefix):
is_prefixed = True
if not is_prefixed:
result.append(element)
return result
num_of_threads = multiprocessing.cpu_count()
results = []
for t in xrange(num_of_threads):
thread.start_new_thread(lambda list: results.extend(get_results(list, t, num_of_threads)), (list,))
from collections import Counter
def filter_list(mylist):
longest_string = len(max(mylist, key=len))
set_list = [set(filter(lambda x: len(x) == i, mylist))
for i in range(1, longest_string)]
def unique_starts_with_filter(string):
for i in range(1, len(string)):
if string[:i] in set_list[i-1]: return False
return True
cn = Counter(mylist)
mylist = filter(lambda x: cn[x] == 1, mylist)
return filter(unique_starts_with_filter, mylist)
（再次）针对样式和极小的优化进行了编辑
您可以按首字母对项目进行分组，然后只搜索子列表，任何字符串都不能以子字符串开头，除非它至少具有相同的首字母:
from collections import defaultdict
def find(l):
d = defaultdict(list)
# group by first letter
for ele in l:
d[ele[0]].append(ele)
for val in d.values():
for v in val:
# check each substring in the sublist
if not any(v.startswith(s) and v != s for s in val):
yield v
print(list(find(l)))
['sdfdg', 'xc', 'ab']
这正确地过滤了单词，正如您从下面的代码中看到的那样，reduce 函数没有，'tool' 不应该在输出中：
In [56]: l = ["tool",'ab',"too", 'xc', 'abb',"toot", 'abed',"abel", 'sdfdg', 'abfdsdg', 'xccc',"xcew","xrew"]
In [57]: reduce(r,l)
Out[57]: ['tool', 'ab', 'too', 'xc', 'sdfdg', 'xrew']
In [58]: list(find(l))
Out[58]: ['sdfdg', 'too', 'xc', 'xrew', 'ab']
它也很高效：
In [59]: l = ["".join(sample(ascii_lowercase, randint(2,25))) for _ in range(5000)]
In [60]: timeit reduce(r,l)
1 loops, best of 3: 2.12 s per loop
In [61]: timeit list(find(l))
1 loops, best of 3: 203 ms per loop
In [66]: %%timeit
..... result = []
....: for element in lst:
....: is_prefixed = False
....: for possible_prefix in lst:
....: if element is not possible_prefix and element.startswith(possible_prefix):
....: is_prefixed = True
....: break
....: if not is_prefixed:
....: result.append(element)
....:
1 loops, best of 3: 4.39 s per loop
In [92]: timeit list(my_filter(l))
1 loops, best of 3: 2.94 s per loop
如果您知道最小字符串长度始终 > 1，您可以进一步优化，同样，如果最小长度字符串为 2，则一个单词必须至少具有前两个字母的共同点：
def find(l):
d = defaultdict(list)
# find shortest length string to use as key length
mn = len(min(l, key=len))
for ele in l:
d[ele[:mn]].append(ele)
for val in d.values():
for v in val:
if not any(v.startswith(s) and v != s for s in val):
yield v
In [84]: timeit list(find(l))
100 loops, best of 3: 14.6 ms per loop
最后，如果你有重复的单词，你可能想从你的列表中过滤掉重复的单词，但你需要保留它们以进行比较：
from collections import defaultdict,Counter
def find(l):
d = defaultdict(list)
mn = len(min(l, key=len))
cn = Counter(l)
for ele in l:
d[ele[:mn]].append(ele)
for val in d.values():
for v in val:
if not any(v.startswith(s) and v != s for s in val):
# make sure v is not a dupe
if cn[v] == 1:
yield v
因此，如果速度很重要，那么使用上述代码的一些变体的实现将比您的幼稚方法快得多。内存中存储的数据也更多，因此您也应该考虑到。
为了节省内存，我们可以为每个 val/sublist 创建一个计数器，这样我们一次只存储一个单词的计数器字典：
def find(l):
d = defaultdict(list)
mn = len(min(l, key=len))
for ele in l:
d[ele[:mn]].append(ele)
for val in d.values():
# we only need check each grouping of words for dupes
cn = Counter(val)
for v in val:
if not any(v.startswith(s) and v != s for s in val):
if cn[v] == 1:
yield v
每个循环创建一个字典会增加 5 毫秒，因此对于 5k 个单词仍然 < 20 毫秒。
如果数据已排序，reduce 方法应该有效：
reduce(r,sorted(l)) # -> ['ab', 'sdfdg', 'too', 'xc', 'xrew']
要明确行为之间的区别：
In [202]: l = ["tool",'ab',"too", 'xc', 'abb',"toot", 'abed',
"abel", 'sdfdg', 'abfdsdg', 'xccc',"xcew","xrew","ab"]
In [203]: list(filter_list(l))
Out[203]: ['ab', 'too', 'xc', 'sdfdg', 'xrew', 'ab']
In [204]: list(find(l))
Out[204]: ['sdfdg', 'too', 'xc', 'xrew', 'ab', 'ab']
In [205]: reduce(r,sorted(l))
Out[205]: ['ab', 'sdfdg', 'too', 'xc', 'xrew']
In [206]: list(find_dupe(l))
Out[206]: ['too', 'xrew', 'xc', 'sdfdg']
In [207]: list(my_filter(l))
Out[207]: ['sdfdg', 'xrew', 'too', 'xc']
In [208]: "ab".startswith("ab")
Out[208]: True
所以 ab 重复了两次所以使用一个集合或一个字典而不跟踪 ab 出现的次数意味着我们认为没有其他元素满足条件 ab "ab".startswith(other ) == True，可以看出是不正确的
您还可以使用 itertools.groupby 根据最小索引大小进行分组：
def find_dupe(l):
l.sort()
mn = len(min(l, key=len))
for k, val in groupby(l, key=lambda x: x[:mn]):
val = list(val)
for v in val:
cn = Counter(val)
if not any(v.startswith(s) and v != s for s in val) and cn[v] == 1:
yield v
根据您的评论，如果您认为 "dd".startswith("dd") 对重复元素不应该为 True，我们可以调整我的第一个代码：
l = ['abbb', 'xc', 'abb', 'abed', 'sdfdg', 'xc','abfdsdg', 'xccc', 'd','dd','sdfdg', 'xc','abfdsdg', 'xccc', 'd','dd']
def find_with_dupe(l):
d = defaultdict(list)
# group by first letter
srt = sorted(set(l))
ind = len(srt[0])
for ele in srt:
d[ele[:ind]].append(ele)
for val in d.values():
for v in val:
# check each substring in the sublist
if not any(v.startswith(s) and v != s for s in val):
yield v
print(list(find_with_dupe(l)))
['abfdsdg', 'abed', 'abb', 'd', 'sdfdg', 'xc']
运行 在随机文本样本 运行 上，您自己的代码所用时间的一小部分：
In [15]: l = open("/home/padraic/Downloads/sample.txt").read().split()
In [16]: timeit list(find(l))
100 loops, best of 3: 19 ms per loop
In [17]: %%timeit
....: l = open("/home/padraic/Downloads/sample.txt").read().split()
....: for i in range(0, len(l) - 1):
....: for j in range(i + 1, len(l)):
....: if l[j].startswith(l[i]):
....: l[j] = l[i]
....: else:
....: if l[i].startswith(l[j]):
....: l[i] = l[j]
....:
1 loops, best of 3: 4.92 s per loop
两者都返回相同的输出：
In [41]: l = open("/home/padraic/Downloads/sample.txt").read().split()
In [42]:
for i in range(0, len(l) - 1):
for j in range(i + 1, len(l)):
if l[j].startswith(l[i]):
l[j] = l[i]
else:
if l[i].startswith(l[j]):
l[i] = l[j]
....:
In [43]:
In [43]: l2 = open("/home/padraic/Downloads/sample.txt").read().split()
In [44]: sorted(set(l)) == sorted(find(l2))
Out[44]: True
这个算法在我的电脑上用了 0.97 秒完成任务，the input file submitted by the author (154MB):
l.sort()
last_str = l[0]
filtered = [last_str]
app = filtered.append
for str in l:
if not str.startswith(last_str):
last_str = str
app(str)
# Commented because of the massive amount of data to print.
# print filtered
算法很简单：首先按字典顺序对列表进行排序，然后搜索第一个没有列表第一个前缀的字符串，然后搜索下一个没有最后一个没有前缀的字符串一个等等
如果列表已经排序（您的示例文件似乎已经排序），您可以删除 l.sort() 行，这将导致时间和内存的 O(n) 复杂度。
您可以试试这个简短的解决方案。
import re
l = ['ab', 'xc', 'abb', 'abed', 'sdfdg', 'abfdsdg', 'xccc']
newl=[]
newl.append(l[0])
con=re.escape(l[0])
for i in l[1:]:
pattern=r"^(?!(?:"+con+r")).*$"
if re.match(pattern,i):
newl.append(i)
con=con+"|"+re.escape(i)
print newl
编辑：长列表使用
import re
l = ['ab', 'xc', 'abb', 'abed', 'sdfdg', 'abfdsdg', 'xccc']
newl=[]
newl.append(l[0])
con=re.escape(l[0])
for i in l[1:]:
for x in re.split("\|",con):
pattern=r"^(?="+x+r").*$"
if re.match(pattern,i):
break
else:
newl.append(i)
con=con+"|"+re.escape(i)
print newl
解决方案 1（使用 LinkedList）
这是一个非常简单的解决方案，使用排序 (O(n * log(n))) 和 LinkedList - 迭代 (O(n)) 和删除元素 (O(1))。如果您对初始数据进行排序，则元素将以这样的方式排序，即另一个元素的最长前缀元素将与后者相邻。因此可以删除该元素。
下面是一段代码，过滤掉排序好的LinkedList:
def filter_out(the_list):
for element in the_list:
if element.prev_node and element.get_data().startswith(element.prev_node.get_data()):
the_list.remove(element)
return the_list
并像这样使用它：
linked_list = LinkedList(sorted(l))
filter_out(linked_list)
那么您的 linked_list 将包含过滤后的数据。
此解决方案需要 O(n * log(n))
这里是LinkedList的实现：
class Node(object):
def __init__(self, data=None, next_node=None, prev_node=None):
self.data = data
self._next_node = next_node
self._prev_node = prev_node
def get_data(self):
return self.data
@property
def next_node(self):
return self._next_node
@next_node.setter
def next_node(self, node):
self._next_node = node
@property
def prev_node(self):
return self._prev_node
@prev_node.setter
def prev_node(self, node):
self._prev_node = node
def __repr__(self):
return repr(self.get_data())
class LinkedList(object):
def __init__(self, iterable=None):
super(LinkedList, self).__init__()
self.head = None
self.tail = None
self.size = 0
if iterable:
for element in iterable:
self.insert(Node(element))
def insert(self, node):
if self.head:
self.tail.next_node = node
node.prev_node = self.tail
self.tail = node
else:
self.head = node
self.tail = node
self.size += 1
def remove(self, node):
if self.size > 1:
prev_node = node.prev_node
next_node = node.next_node
if prev_node:
prev_node.next_node = next_node
if next_node:
next_node.prev_node = prev_node
else:
self.head = None
self.tail = None
def __iter__(self):
return LinkedListIter(self.head)
def __repr__(self):
result = ''
for node in self:
result += str(node.get_data()) + ', '
if result:
result = result[:-2]
return "[{}]".format(result)
class LinkedListIter(object):
def __init__(self, start):
super(LinkedListIter, self).__init__()
self.node = start
def __iter__(self):
return self
def next(self):
this_node = self.node
if not this_node:
raise StopIteration
self.node = self.node.next_node
return this_node
解决方案 2（使用集合）
如果算法不需要稳定，即结果列表不需要保持元素的原始顺序，这里是使用set的解决方案。
那么让我们做一些定义：
n - the size of your list, i.e. number of elements
m - the maximum possible length of a string element of your list
首先，从原来的 list l:
中初始化一个新的 set inter
inter = set(l)
这样我们将删除所有重复的元素，这将简化我们的进一步工作。此外，此操作的平均复杂度为 O(n)，最坏情况为 O(n^2)。
然后再空一个set，我们将在其中保存我们的结果：
result = set()
所以现在让我们检查每个元素，在我们的 inter 集合中是否有后缀：
for elem in inter: # This will take at most O(n)
no_prefix = True
for i in range(1, len(elem)): # This will take at most O(m)
if elem[:i] in inter: # This will take avg: O(1), worst: O(n)
no_prefix = False
continue
if no_prefix:
result.add(elem) # This will take avg: O(1), worst: O(n)
所以现在您已经在 result.
中得到了您想要的东西
这个最后的核心步骤平均需要 O(n * (1 * m + 1)) = O(n * m)，最坏情况下需要 O(n * (m * n + n)) = O(n^2 * (m + 1))，因此如果 m 与 n 相比微不足道，那么你有 [平均 =18=]，最坏情况下 O(n ^ 2)。
复杂度是根据Python provides for the set data structure计算出来的。要进一步优化算法，您可以实现自己的 tree-based set 并获得 O(n * log(n)) 复杂度。
我相信以下很可能是最有效的。
from sortedcontainers import SortedSet
def prefixes(l) :
rtn = SortedSet()
for s in l:
rtn.add(s)
i = rtn.index(s)
if (i > 0 and s.startswith(rtn[i-1])):
rtn.remove(s)
else :
j = i+1
while (j < len(rtn) and rtn[j].startswith(s)):
j+=1
remove = rtn[i+1:j]
for r in remove:
rtn.remove(r)
return list(rtn)
我认为最重要的情况可能是输入文件非常长，而输出文件要小得多。此解决方案避免将整个输入文件保存在内存中。如果输入文件已排序，则它持有的 rtn 参数永远不会比最终返回的文件长。此外，它演示了 "maintain a solution that is valid for data seen so far, and extend this solution to be valid to each new piece of data" 的模式。这是一个让您自己熟悉的好模式。
我在筛选字符串列表时遇到了一些问题。我发现了一个类似的问题 here 但不是我需要的。
输入列表为：
l = ['ab', 'xc', 'abb', 'abed', 'sdfdg', 'abfdsdg', 'xccc']
预期结果是
['ab', 'xc', 'sdfdg']
结果中项目的顺序并不重要
过滤功能必须很快，因为列表的大小
我目前的解决方案是
l = ['ab', 'xc', 'abb', 'abed', 'sdfdg', 'abfdsdg', 'xccc']
for i in range(0, len(l) - 1):
for j in range(i + 1, len(l)):
if l[j].startswith(l[i]):
l[j] = l[i]
else:
if l[i].startswith(l[j]):
l[i] = l[j]
print list(set(l))
编辑
经过大量输入数据的多次测试，列出 1500000 个字符串，我最好的解决方案是：
def filter(l):
if l==[]:
return []
l2=[]
l2.append(l[0])
llen = len(l)
k=0
itter = 0
while k<llen:
addkelem = ''
j=0
l2len = len(l2)
while j<l2len:
if (l2[j].startswith(l[k]) and l[k]!= l2[j]):
l2[j]=l[k]
l.remove(l[k])
llen-=1
j-=1
addkelem = ''
continue
if (l[k].startswith(l2[j])):
addkelem = ''
break
elif(l[k] not in l2):
addkelem = l[k]
j+=1
if addkelem != '':
l2.append(addkelem)
addkelem = ''
k+=1
return l2
执行时间约为 213 秒
Sample imput data - 每行是列表中的一个字符串
使用reduce函数的解决方案：
def r(a, b):
if type(a) is list:
if len([z for z in a if b.startswith(z)]) == 0:
a.append(b)
return a
if a.startswith(b):
return b
if b.startswith(a):
return a
return [a, b]
print reduce(r, l)
估计[z for z in a if b.startswith(z)]部分可以进一步优化
编辑3
经过一番冥想，我写了这个算法。它比基于 Padraic Cunningham 提供的大随机数据集的基于 reduce 的方法快 1k 倍（感谢提供数据集）。该算法具有 ~ O(nlogn) 的复杂性，尽管还有一些 space 用于较小的优化。它的内存效率也很高。大约需要额外 n space。
def my_filter(l):
q = sorted(l, reverse=True)
first = q.pop()
addfirst = True
while q:
candidate = q.pop()
if candidate == first:
addfirst = False
continue
if not candidate.startswith(first):
if addfirst:
yield first
first, addfirst = candidate, True
if addfirst:
yield first
Edit2 这个东西在我的测试中和基于reduce的算法一样快，但是这个比较取决于使用的数据集。我只是将教科书页面解析为单词。该算法基于以下观察。令 A、B 和 C 为字符串，len(A) < min(len(B), len(C))。请注意，如果 A 是 B 的前缀，则检查 A 是否是 C 的前缀就足以说明存在 C 的前缀。
def my_filter(l):
q = sorted(l, key=len)
prefixed = []
while q:
candidate = q.pop()
if any(candidate.startswith(prefix) for prefix in prefixed):
continue
if any(candidate.startswith(string) for string in q):
prefixed.append(candidate)
else:
yield candidate
原版post 这是我提出的原始算法。事实上，它是您算法的简明版本。
l = ['ab', 'xc', 'abb', 'abed', 'sdfdg', 'abfdsdg', 'xccc']
res = [string for string in l if sum(not string.startswith(prefix) for prefix in l) == len(l)-1]
演示>>>
print res
# ['ab', 'xc', 'sdfdg']
lst = ['ab', 'xc', 'abb', 'abed', 'sdfdg', 'abfdsdg', 'xccc']
result = []
for element in lst:
is_prefixed = False
for possible_prefix in lst:
if element is not possible_prefix and element.startswith(possible_prefix):
is_prefixed = True
break
if not is_prefixed:
result.append(element)
这是一些实验性的多线程版本：
好好测试一下！
import thread
import math
import multiprocessing
list = ['ab', 'xc', 'abb', 'abed', 'sdfdg', 'abfdsdg', 'xccc']
def get_results(list, thread_num, num_of_threads):
result = []
part_size = int(math.ceil(len(list) * 1.0 / num_of_threads))
for element in list[part_size * thread_num: part_size * (thread_num + 1)]:
is_prefixed = False
for possible_prefix in list:
if element is not possible_prefix and element.startswith(possible_prefix):
is_prefixed = True
if not is_prefixed:
result.append(element)
return result
num_of_threads = multiprocessing.cpu_count()
results = []
for t in xrange(num_of_threads):
thread.start_new_thread(lambda list: results.extend(get_results(list, t, num_of_threads)), (list,))
from collections import Counter
def filter_list(mylist):
longest_string = len(max(mylist, key=len))
set_list = [set(filter(lambda x: len(x) == i, mylist))
for i in range(1, longest_string)]
def unique_starts_with_filter(string):
for i in range(1, len(string)):
if string[:i] in set_list[i-1]: return False
return True
cn = Counter(mylist)
mylist = filter(lambda x: cn[x] == 1, mylist)
return filter(unique_starts_with_filter, mylist)
（再次）针对样式和极小的优化进行了编辑
您可以按首字母对项目进行分组，然后只搜索子列表，任何字符串都不能以子字符串开头，除非它至少具有相同的首字母:
from collections import defaultdict
def find(l):
d = defaultdict(list)
# group by first letter
for ele in l:
d[ele[0]].append(ele)
for val in d.values():
for v in val:
# check each substring in the sublist
if not any(v.startswith(s) and v != s for s in val):
yield v
print(list(find(l)))
['sdfdg', 'xc', 'ab']
这正确地过滤了单词，正如您从下面的代码中看到的那样，reduce 函数没有，'tool' 不应该在输出中：
In [56]: l = ["tool",'ab',"too", 'xc', 'abb',"toot", 'abed',"abel", 'sdfdg', 'abfdsdg', 'xccc',"xcew","xrew"]
In [57]: reduce(r,l)
Out[57]: ['tool', 'ab', 'too', 'xc', 'sdfdg', 'xrew']
In [58]: list(find(l))
Out[58]: ['sdfdg', 'too', 'xc', 'xrew', 'ab']
它也很高效：
In [59]: l = ["".join(sample(ascii_lowercase, randint(2,25))) for _ in range(5000)]
In [60]: timeit reduce(r,l)
1 loops, best of 3: 2.12 s per loop
In [61]: timeit list(find(l))
1 loops, best of 3: 203 ms per loop
In [66]: %%timeit
..... result = []
....: for element in lst:
....: is_prefixed = False
....: for possible_prefix in lst:
....: if element is not possible_prefix and element.startswith(possible_prefix):
....: is_prefixed = True
....: break
....: if not is_prefixed:
....: result.append(element)
....:
1 loops, best of 3: 4.39 s per loop
In [92]: timeit list(my_filter(l))
1 loops, best of 3: 2.94 s per loop
如果您知道最小字符串长度始终 > 1，您可以进一步优化，同样，如果最小长度字符串为 2，则一个单词必须至少具有前两个字母的共同点：
def find(l):
d = defaultdict(list)
# find shortest length string to use as key length
mn = len(min(l, key=len))
for ele in l:
d[ele[:mn]].append(ele)
for val in d.values():
for v in val:
if not any(v.startswith(s) and v != s for s in val):
yield v
In [84]: timeit list(find(l))
100 loops, best of 3: 14.6 ms per loop
最后，如果你有重复的单词，你可能想从你的列表中过滤掉重复的单词，但你需要保留它们以进行比较：
from collections import defaultdict,Counter
def find(l):
d = defaultdict(list)
mn = len(min(l, key=len))
cn = Counter(l)
for ele in l:
d[ele[:mn]].append(ele)
for val in d.values():
for v in val:
if not any(v.startswith(s) and v != s for s in val):
# make sure v is not a dupe
if cn[v] == 1:
yield v
因此，如果速度很重要，那么使用上述代码的一些变体的实现将比您的幼稚方法快得多。内存中存储的数据也更多，因此您也应该考虑到。
为了节省内存，我们可以为每个 val/sublist 创建一个计数器，这样我们一次只存储一个单词的计数器字典：
def find(l):
d = defaultdict(list)
mn = len(min(l, key=len))
for ele in l:
d[ele[:mn]].append(ele)
for val in d.values():
# we only need check each grouping of words for dupes
cn = Counter(val)
for v in val:
if not any(v.startswith(s) and v != s for s in val):
if cn[v] == 1:
yield v
每个循环创建一个字典会增加 5 毫秒，因此对于 5k 个单词仍然 < 20 毫秒。
如果数据已排序，reduce 方法应该有效：
reduce(r,sorted(l)) # -> ['ab', 'sdfdg', 'too', 'xc', 'xrew']
要明确行为之间的区别：
In [202]: l = ["tool",'ab',"too", 'xc', 'abb',"toot", 'abed',
"abel", 'sdfdg', 'abfdsdg', 'xccc',"xcew","xrew","ab"]
In [203]: list(filter_list(l))
Out[203]: ['ab', 'too', 'xc', 'sdfdg', 'xrew', 'ab']
In [204]: list(find(l))
Out[204]: ['sdfdg', 'too', 'xc', 'xrew', 'ab', 'ab']
In [205]: reduce(r,sorted(l))
Out[205]: ['ab', 'sdfdg', 'too', 'xc', 'xrew']
In [206]: list(find_dupe(l))
Out[206]: ['too', 'xrew', 'xc', 'sdfdg']
In [207]: list(my_filter(l))
Out[207]: ['sdfdg', 'xrew', 'too', 'xc']
In [208]: "ab".startswith("ab")
Out[208]: True
所以 ab 重复了两次所以使用一个集合或一个字典而不跟踪 ab 出现的次数意味着我们认为没有其他元素满足条件 ab "ab".startswith(other ) == True，可以看出是不正确的
您还可以使用 itertools.groupby 根据最小索引大小进行分组：
def find_dupe(l):
l.sort()
mn = len(min(l, key=len))
for k, val in groupby(l, key=lambda x: x[:mn]):
val = list(val)
for v in val:
cn = Counter(val)
if not any(v.startswith(s) and v != s for s in val) and cn[v] == 1:
yield v
根据您的评论，如果您认为 "dd".startswith("dd") 对重复元素不应该为 True，我们可以调整我的第一个代码：
l = ['abbb', 'xc', 'abb', 'abed', 'sdfdg', 'xc','abfdsdg', 'xccc', 'd','dd','sdfdg', 'xc','abfdsdg', 'xccc', 'd','dd']
def find_with_dupe(l):
d = defaultdict(list)
# group by first letter
srt = sorted(set(l))
ind = len(srt[0])
for ele in srt:
d[ele[:ind]].append(ele)
for val in d.values():
for v in val:
# check each substring in the sublist
if not any(v.startswith(s) and v != s for s in val):
yield v
print(list(find_with_dupe(l)))
['abfdsdg', 'abed', 'abb', 'd', 'sdfdg', 'xc']
运行 在随机文本样本 运行 上，您自己的代码所用时间的一小部分：
In [15]: l = open("/home/padraic/Downloads/sample.txt").read().split()
In [16]: timeit list(find(l))
100 loops, best of 3: 19 ms per loop
In [17]: %%timeit
....: l = open("/home/padraic/Downloads/sample.txt").read().split()
....: for i in range(0, len(l) - 1):
....: for j in range(i + 1, len(l)):
....: if l[j].startswith(l[i]):
....: l[j] = l[i]
....: else:
....: if l[i].startswith(l[j]):
....: l[i] = l[j]
....:
1 loops, best of 3: 4.92 s per loop
两者都返回相同的输出：
In [41]: l = open("/home/padraic/Downloads/sample.txt").read().split()
In [42]:
for i in range(0, len(l) - 1):
for j in range(i + 1, len(l)):
if l[j].startswith(l[i]):
l[j] = l[i]
else:
if l[i].startswith(l[j]):
l[i] = l[j]
....:
In [43]:
In [43]: l2 = open("/home/padraic/Downloads/sample.txt").read().split()
In [44]: sorted(set(l)) == sorted(find(l2))
Out[44]: True
这个算法在我的电脑上用了 0.97 秒完成任务，the input file submitted by the author (154MB):
l.sort()
last_str = l[0]
filtered = [last_str]
app = filtered.append
for str in l:
if not str.startswith(last_str):
last_str = str
app(str)
# Commented because of the massive amount of data to print.
# print filtered
算法很简单：首先按字典顺序对列表进行排序，然后搜索第一个没有列表第一个前缀的字符串，然后搜索下一个没有最后一个没有前缀的字符串一个等等
如果列表已经排序（您的示例文件似乎已经排序），您可以删除 l.sort() 行，这将导致时间和内存的 O(n) 复杂度。
您可以试试这个简短的解决方案。
import re
l = ['ab', 'xc', 'abb', 'abed', 'sdfdg', 'abfdsdg', 'xccc']
newl=[]
newl.append(l[0])
con=re.escape(l[0])
for i in l[1:]:
pattern=r"^(?!(?:"+con+r")).*$"
if re.match(pattern,i):
newl.append(i)
con=con+"|"+re.escape(i)
print newl
编辑：长列表使用
import re
l = ['ab', 'xc', 'abb', 'abed', 'sdfdg', 'abfdsdg', 'xccc']
newl=[]
newl.append(l[0])
con=re.escape(l[0])
for i in l[1:]:
for x in re.split("\|",con):
pattern=r"^(?="+x+r").*$"
if re.match(pattern,i):
break
else:
newl.append(i)
con=con+"|"+re.escape(i)
print newl
解决方案 1（使用 LinkedList）
这是一个非常简单的解决方案，使用排序 (O(n * log(n))) 和 LinkedList - 迭代 (O(n)) 和删除元素 (O(1))。如果您对初始数据进行排序，则元素将以这样的方式排序，即另一个元素的最长前缀元素将与后者相邻。因此可以删除该元素。
下面是一段代码，过滤掉排序好的LinkedList:
def filter_out(the_list):
for element in the_list:
if element.prev_node and element.get_data().startswith(element.prev_node.get_data()):
the_list.remove(element)
return the_list
并像这样使用它：
linked_list = LinkedList(sorted(l))
filter_out(linked_list)
那么您的 linked_list 将包含过滤后的数据。
此解决方案需要 O(n * log(n))
这里是LinkedList的实现：
class Node(object):
def __init__(self, data=None, next_node=None, prev_node=None):
self.data = data
self._next_node = next_node
self._prev_node = prev_node
def get_data(self):
return self.data
@property
def next_node(self):
return self._next_node
@next_node.setter
def next_node(self, node):
self._next_node = node
@property
def prev_node(self):
return self._prev_node
@prev_node.setter
def prev_node(self, node):
self._prev_node = node
def __repr__(self):
return repr(self.get_data())
class LinkedList(object):
def __init__(self, iterable=None):
super(LinkedList, self).__init__()
self.head = None
self.tail = None
self.size = 0
if iterable:
for element in iterable:
self.insert(Node(element))
def insert(self, node):
if self.head:
self.tail.next_node = node
node.prev_node = self.tail
self.tail = node
else:
self.head = node
self.tail = node
self.size += 1
def remove(self, node):
if self.size > 1:
prev_node = node.prev_node
next_node = node.next_node
if prev_node:
prev_node.next_node = next_node
if next_node:
next_node.prev_node = prev_node
else:
self.head = None
self.tail = None
def __iter__(self):
return LinkedListIter(self.head)
def __repr__(self):
result = ''
for node in self:
result += str(node.get_data()) + ', '
if result:
result = result[:-2]
return "[{}]".format(result)
class LinkedListIter(object):
def __init__(self, start):
super(LinkedListIter, self).__init__()
self.node = start
def __iter__(self):
return self
def next(self):
this_node = self.node
if not this_node:
raise StopIteration
self.node = self.node.next_node
return this_node
解决方案 2（使用集合）
如果算法不需要稳定，即结果列表不需要保持元素的原始顺序，这里是使用set的解决方案。
那么让我们做一些定义：
n- the size of your list, i.e. number of elements
m- the maximum possible length of a string element of your list
首先，从原来的 list l:
set inter
inter = set(l)
这样我们将删除所有重复的元素，这将简化我们的进一步工作。此外，此操作的平均复杂度为 O(n)，最坏情况为 O(n^2)。
然后再空一个set，我们将在其中保存我们的结果：
result = set()
所以现在让我们检查每个元素，在我们的 inter 集合中是否有后缀：
for elem in inter: # This will take at most O(n)
no_prefix = True
for i in range(1, len(elem)): # This will take at most O(m)
if elem[:i] in inter: # This will take avg: O(1), worst: O(n)
no_prefix = False
continue
if no_prefix:
result.add(elem) # This will take avg: O(1), worst: O(n)
所以现在您已经在 result.
这个最后的核心步骤平均需要 O(n * (1 * m + 1)) = O(n * m)，最坏情况下需要 O(n * (m * n + n)) = O(n^2 * (m + 1))，因此如果 m 与 n 相比微不足道，那么你有 [平均 =18=]，最坏情况下 O(n ^ 2)。
复杂度是根据Python provides for the set data structure计算出来的。要进一步优化算法，您可以实现自己的 tree-based set 并获得 O(n * log(n)) 复杂度。
我相信以下很可能是最有效的。
from sortedcontainers import SortedSet
def prefixes(l) :
rtn = SortedSet()
for s in l:
rtn.add(s)
i = rtn.index(s)
if (i > 0 and s.startswith(rtn[i-1])):
rtn.remove(s)
else :
j = i+1
while (j < len(rtn) and rtn[j].startswith(s)):
j+=1
remove = rtn[i+1:j]
for r in remove:
rtn.remove(r)
return list(rtn)
我认为最重要的情况可能是输入文件非常长，而输出文件要小得多。此解决方案避免将整个输入文件保存在内存中。如果输入文件已排序，则它持有的 rtn 参数永远不会比最终返回的文件长。此外，它演示了 "maintain a solution that is valid for data seen so far, and extend this solution to be valid to each new piece of data" 的模式。这是一个让您自己熟悉的好模式。