Python：从列表中删除前缀为oth的元素

Question

获取不包含任何其他元素作为前缀的元素列表的最快方法（python）。在

（元素可以按任何顺序排列，为了解释清楚，元素在这里保持某种顺序，因此如果需要，必须显式地进行排序）

输入是

['AB', 'ABC', 'ABCDEF', 'ABCDEFG', 'BCD', 'DEF', 'DEFGHI', 'EF', 'GKL', 'JKLM']

消除的元素：

^{pr2}$

预期产量

['ABCDEFG', 'BCD', 'DEFGHI', 'EF', 'GKL', 'JKLM']

已编辑：

增加一点复杂性（或清晰度）。列表的平均长度在500到900之间。在

Answer 1

ls.sort()如果您的列表最初是无序的，请先。在

使用startswith：

In [71]: [i for i, j in zip(ls[:-1], ls[1:]) if not j.startswith(i)]+[ls[-1]]
Out[71]: ['ABCDEFG', 'BCD', 'DEFGHI', 'EF', 'GKL', 'JKLM']

{cd3>或^：

^{pr2}$

与@sashkello的方法相比：

In [78]: timeit [v for i, v in enumerate(ls[:-1]) if not ls[i+1].startswith(v)]+[ls[-1]] 
10000 loops, best of 3: 29.6 us per loop

In [79]: timeit [i for i, j in zip(ls[:-1], ls[1:]) if not j.startswith(i)]+[ls[-1]]
10000 loops, best of 3: 28.5 us per loop

In [80]: timeit [x for x in ls if x not in [y[:len(x)] for y in ls if y != x]]
1000 loops, best of 3: 1.77 ms per loop

Answer 2

如果对列表进行排序，则每个元素要么是下一个元素的前缀，要么不是其中任何元素的前缀。因此，您可以写下：

ls.sort()
[ls[i] for i in range(len(ls))[:-1] if ls[i] != ls[i+1][:len(ls[i])]] + [ls[-1]]

这将是n log(n)排序加上一次遍历列表（n）。在

对于您当前的排序列表，它也稍微快一点，因为它是线性的，timeit给出了2.11我们。在

使用zip可以稍微加快实现速度（但不是渐进的），而且更具python风格：

^{pr2}$

时间是1.77美元

Answer 3

列表理解（ls是输入列表的名称）：

[x for x in ls if x not in [y[:len(x)] for y in ls if y != x]]

就性能而言，我怀疑它是最快的，但它的想法是非常直截了当的。您将逐个检查列表元素，并检查它是否是所有其余元素的列表中任何元素的前缀。在

timeit结果：每循环11.9 us（不过，如果要将其用于大列表，则缩放更重要）