python：什麼是從有序列表中排序鍵的子列表的最快方法

Question

我有一個關於從一長串鍵中排序無序子鍵列表的速度的問題。所以

keys =['a','c','b','f','e','d','p','t','s','y','h'] 
sub_list = ['y','b','a','p'] 

我有兩個想法：

sublist = sorted(sub_list, key=keys) 

，或者

sublist = [key for key in keys if key in sub_list] 

有可能比這兩個對於所有我知道更好的方法。有什麼想法嗎？

Answer 1

我認爲你應該使用sub_list.sort了排序，因爲.sort使得就地排序，其中sorted使子表的複印件排序

所做的列表理解很慢之前，因爲如果語句掃描的最後槽整個SUB_LIST（這樣做的n個操作每個鍵額外）

sublist = [key for key in keys if key in sub_list] 

更快列表理解應該是這樣

sub_set = set(sublist) 
sub_list = [key for key in keys if key in sub_set] 

因爲散列和設置外觀起坐O（1）其中，列表查找是O（N）

排序通常是O（n日誌（n））的 和列表理解爲O（n）的

然而假設是：

sublist = sorted(sub_list, key=keys) 

你的意思是：

sublist = sorted(sub_list, key=keys.index) 

你有清單查詢，而不是哈希外觀（nlog（n））到O（（n ** 2）* log（n））

要將排序返回到nlog（n），您必須將您的密鑰列表哈希如下：

keys = dict(zip(keys, range(len(keys)))) 
sublist = sorted(sub_list, key=keys) 

Answer 2

只是timeit：

In [3]: %timeit sorted(sub_list, lambda a,b: cmp(keys.index(a), keys.index(b))) 
100000 loops, best of 3: 6.22 us per loop 

In [4]: %timeit sublist = [key for key in keys if key in sub_list] 
1000000 loops, best of 3: 1.91 us per loop 

EDIT（更多的方法）：

%timeit sorted(sub_list, key=keys.index) 
100000 loops, best of 3: 2.8 us per loop 

這個例子使用了宏（或不管他們在ipython的稱呼），但你可以通過使用timeit自己：

import timeit 

p = """ 
keys =['a','c','b','f','e','d','p','t','s','y','h'] 
sub_list = ['y','b','a','p']""" 

s = "sorted(sub_list, lambda a,b: cmp(keys.index(a), keys.index(b)))" 

timeit.Timer(stmt=s, setup=p).timeit() 
>>> 8.40028386496742 

s = "[key for key in keys if key in sub_list]" 
timeit.Timer(stmt=s, setup=p).timeit() 
>>> 1.9661344551401498 

所以，你可以嘗試所有你能想到的方法，並選擇最快的

Answer 3

爲什麼不只是sub_list.sort()？這可能不是最快的，但它確實很容易理解。