2

キーの長いリストからキーの順序付けられていないサブリストをソートする速度について質問があります。そう

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

私には2つのアイデアがあります：

sublist = sorted(sub_list, key=keys)

また、

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

私が知っている限りでは、これら2つよりも良い方法があるかもしれません. 何かご意見は？

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ため、オーバーソートを使用する必要があると思います.sortsorted

最後のifステートメントがsub_list全体をスキャンする必要があるため、作成したリストの理解は非常に遅くなります（したがって、キーごとに余分な操作を行いません）

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 に答える