2

我有一个关于从一长串键中排序无序键子列表的速度的问题。所以

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]

据我所知,可能有比这两个更好的方法。有什么想法吗?

4

3 回答 3

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

所以你可以尝试所有你能想到的方法并选择最快的

于 2012-12-05T20:51:42.790 回答
0

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

于 2012-12-05T21:03:52.733 回答
0

我认为您应该使用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)
于 2012-12-05T22:14:59.317 回答