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

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 us。

稍微更快的實現（但不是漸近），並且更Python以及使用zip：

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

timeit給我們1.77

Answer 2

列表理解（ls是您的輸入列表的名稱）：我懷疑它在性能方面的最快

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

，但這個想法非常簡單。您將逐個查看list元素，並檢查它是否是所有其餘元素列表中任何元素的前綴。

timeit結果：11.9我們每個循環（雖然縮放更重要的，如果你要使用它的大名單）

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