类似项目的检查表

Question

给出以下列表

simple_list = ['abcX1', 'def', 'abc', 'abcX2', 'abcY', 'defX1', 'efg', 'fgh']

如何删除起始相同但没有后缀的项目

例如：

• 当然{}我只想保留{}
• 当然{}我想保留{}
• 当然{}我想保留这两个，因为它们没有带后缀的对应项

我的想法：

for i in simple_list:
   for j in simple_list:
      Here I am stuck

此外，我的尝试似乎不太像Python。因此，我们将非常感谢您的建议

Answer 1

对于短列表，您可以使用嵌套的列表理解和any，检查当前元素是否是任何其他元素（除了它本身）的前缀

lst = ['abcX1', 'def', 'abc', 'abcX2', 'abcY', 'defX1', 'efg', 'fgh']

res = [x for x in lst if not any(x != y and y.startswith(x) for y in lst)]

如果列表包含重复元素，则保留所有重复项；在这种情况下，您应该比较索引而不是元素本身，或者首先从元素创建一个集合。）

但是，请注意，这将具有二次复杂性，即O（n²），这对于较长的列表可能是禁止的。更好（但也有点复杂）的方法是从所有单词中创建一个Trie或前缀树，然后只使用该树的叶子

tree = {}
for w in lst:
    t = tree
    for c in w:
        t = t.setdefault(c, {})

def leafs(t, p=""):
    return [x for k in t for x in leafs(t[k], p+k)] if t else [p]

res = list(leafs(tree))

创建树和获取叶子的复杂度应该是O（n*k），其中n是单词数，k是每个单词的平均字母数。¹

另一种更简单的方法是：请注意，如果x是y的前缀，那么x将在y之前排序，因此您可以对列表排序，然后仅比较连续值。排序的复杂度为O（n logn），然后过滤的复杂度为O（n）

srt = sorted(lst)
res = [x for i, x in enumerate(srt)
         if i == len(srt) - 1 or not srt[i+1].startswith(x)]

树和排序方法都可能扰乱结果中元素的顺序。如果希望元素按其原始顺序排列，可以从筛选的元素创建一个set，然后在原始列表上进行另一次传递，保留集合中的元素。这将添加另一个O（n）：

res_set = set(res)
res = [x for x in lst if x in res_set]

每种方式的结果res都是['abcX1', 'abcX2', 'abcY', 'defX1', 'efg', 'fgh']。此外，它们都将创建一个新的过滤列表，但不会修改原始列表

---

我做了更多的时间分析。对于您的列表，正如预期的那样，没有太大的差异。有趣的是，前缀树最慢，可能是因为创建所有这些字典的开销超过了短列表中的O（n²）。分拣速度最快

>>> %timeit test.simple(lst)
10000 loops, best of 5: 44.3 µs per loop
>>> %timeit test.prefixtree(lst)
10000 loops, best of 5: 51.6 µs per loop
>>> %timeit test.sorting(lst)
100000 loops, best of 5: 11.2 µs per loop

更重要的是，在1000个单词的列表中，前缀树现在比嵌套循环快得多，但仍然比排序慢得多，尽管其复杂性较低。我对此的解释是，内置sorted的O（n logn）是用快速C实现的，而树的O（n）仍然是慢速Python

>>> %timeit test.simple(words)
1 loop, best of 5: 562 ms per loop
>>> %timeit test.prefixtree(words)
100 loops, best of 5: 8.42 ms per loop
>>> %timeit test.sorting(words)
1000 loops, best of 5: 1.23 ms per loop

---

¹我在这里添加了k因子，因为它在这个算法中更为明显，但是当然使用startswith也不是O（1），而是O（[实际前缀的长度]）

Answer 2

试试这个：

filtered_list = [x for x in simple_list if not any([y.startswith(x) and y != x for y in simple_list])]