python - 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

只是时间：

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

编辑（更多方法）：

%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 2

为什么不只是sub_list.sort()？它可能不是最快的，但它肯定很容易理解。

Answer 3

我认为您应该使用sub_list.sort过度排序，因为.sort进行就地排序，其中sorted在排序之前复制子列表

您所做的列表理解非常慢，因为最后一个 if 语句必须扫描整个 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(nlog(n)) 并且列表理解是 O(n)

但是假设：

sublist = sorted(sub_list, key=keys)

你的意思是：

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

你有列表查找而不是哈希查找，因此你的排序从 O(nlog(n)) 到 O((n**2)*log(n))

要将排序返回到 nlog(n)，您必须将密钥列表转换为哈希，如下所示：

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