Python: 删除列表中其他元素的前缀元素

Question

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

（元素可以以任何顺序出现，为了清晰起见，在这里元素被保持有点连续，所以如果需要排序，必须显式地执行）

输入是

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

消除的元素：

'AB' prefix of 'ABC'
'ABC' prefix of 'ABCDEF'
'ABCDEF' prefix OF 'ABCDEFG'
'DEF' prefix of 'DEFGHI'

预期输出

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

编辑:

稍微增加一些复杂性（或清晰度）。列表的平均长度在500-900之间变化。

- NEB

---

输出结果的顺序重要吗？ - thefourtheye

是的，结果必须排序。 - NEB

你的输出是否应该包含 'ABCDEFG' 和 'DEFGHI'？你的意思是你应该删除那些是其他元素前缀的元素吗？ - Matthew Trevor

由于它不是任何其他元素的前缀，所以是的。 - NEB

Answer 1

如果您的列表已经排序，每个元素都要么是下一个元素的前缀，要么不是它们中任何一个的前缀。因此，您可以这样写：

```

如果您的列表已经排序，每个元素都要么是下一个元素的前缀，要么不是它们中任何一个的前缀。因此，您可以这样写：

```

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 风格。

[x for x, y in zip(ls[:-1], ls[1:]) if x != y[:len(x)]] + [ls[-1]]

timeit 给出了 1.77 微秒

- sashkello

---

对于我在这里尝试的示例数据，第一个答案看起来相当快。 - NEB

你是对的。我在平均列表长度为900的情况下再次进行了采样。zip逻辑执行1000次循环所需的平均时间（700微秒）比第一个逻辑（740微秒）要好得多。感谢您提供的解决方案 :) - NEB

是 n + log(n) 吗？不是 nlog(n)。 - Misha Slyusarev

@MishaSlyusarev 他们使用的是Timsort算法，其时间复杂度为n log(n)。总时间复杂度为 n log(n) + n。 - sashkello

Answer 2

列表推导式（ls 是你的输入列表名称）：

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

我觉得这个算法在性能上可能不是最快的，但是思路非常直接。你逐个遍历列表元素，并检查它是否为其余所有元素列表中任何元素的前缀。

timeit 结果：每次循环11.9微秒（如果您要用于大型列表，则比例更重要）。

- sashkello

---

除非你对列表理解非常熟悉，否则它并不是一个“简单易读”的想法。它可能需要一些解释。 - Emmet

@Emmet：这是我一直在使用的解决方案，但对于我的情况，每个循环所需的平均时间约为240毫秒。1000个循环700微秒比1个循环240毫秒要好得多（在代码的关键路径中实现了非常好的性能提升）。但我仍然同意您的观点，即易于理解和可读性。 - NEB

Answer 3

如果您的列表最初是无序的，请首先使用 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']

或者使用enumerate：

[v for i, v in enumerate(ls[:-1]) if not ls[i+1].startswith(v)]+[ls[-1]]

与@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

- zhangxaochen

---

你只是比较相邻的元素。发布者指定输入可能未经排序。 - roippi

@roippi，我想只需要ls.sort就可以了 ;) - zhangxaochen

是的，但你让时间方面的问题存在了。即使你更新了它们，在预排序的列表上进行排序显然并不能代表真实的性能。你的算法复杂度确实是O(nlogn)，而不是sashkello的O(n**2)，但在这个示例数据上的任何时间都不会接近现实。 - roippi

我又对平均列表长度为900进行了样本测试，大多数解决方案的1000次循环所需的平均时间约为790微秒至825微秒。它们不错，但对于我的情况，被接受的答案运行时间为700微秒。 - NEB

@NEB 我的时间片段是在他编辑之前发布的，sashkello的答案现在很好 ;) - zhangxaochen