2

非常に頻繁に呼び出されるコードから関数を高速化したいと考えています。この関数は、文字列の入力リスト (通常は長さ 4) を受け取り、入力文字列の英数字の順序に対応する順序で、対応するエントリが大文字に置き換えられた文字列のリストを生成します。次に、このリストが 1 つの文字列に結合されます。例: 入力リスト['wwTv', 'NzkT', 'wwTv', 'JhXc']、出力文字列'C,B,C,A'。実際の例では、各リストに多くの重複があります。

この特定の問題のより効果的な解決策を提案できますか? または、私の単純なアルゴリズムは十分に優れており、大幅に改善することはできませんか?

以下は私のコードのサンプルです（Python 3.2）。ここでは、入力データのサンプルがランダムに作成され、関数に渡されますf。

import timeit
import string, random

dumb_label_set = ['A', 'B', 'C', 'D', 'E']

def a(labels):
    uniq_labels = sorted(set(labels))
    dumb_labels = [dumb_label_set[uniq_labels.index(a)] for a in labels]
    s_name = ','.join(dumb_labels)
    return(s_name)

def b(labels):
    uniq_labels = {l: i for i, l in enumerate(sorted(set(labels)))}
    dumb_labels = [dumb_label_set[uniq_labels[a]] for a in labels]
    s_name = ','.join(dumb_labels)
    return(s_name)

labels = []
for i1 in range(100000):
    labels.append([''.join(random.choice(string.ascii_letters) for ii in range(random.randint(1,4))) for i2 in range(4)])

start = timeit.default_timer()
res_a = [a(l) for l in labels]
print(timeit.default_timer() - start)

start = timeit.default_timer()
res_b = [b(l) for l in labels]
print(timeit.default_timer() - start)

print(res_a == res_b)

結果：

0.41835449560994675
0.4420497451417873
True

私の関数aは少し速く、bMartijn Pieters によって提案されました

4

2 に答える 2

3

辞書を使用して、ラベルをインデックスにマップします。

uniq_labels = {l: i for i, l in enumerate(sorted(set(labels)))}
dumb_labels = [dumb_label_set[uniq_labels[a]] for a in labels]

より小さいlabelsセットを使用して、より管理しやすい時間で複数のパスを容易にすると、次のようになります。

>>> import timeit
>>> import string, random
>>> dumb_label_set = ['A', 'B', 'C', 'D', 'E']
>>> def f(labels):
...     uniq_labels = sorted(set(labels))
...     dumb_labels = [dumb_label_set[uniq_labels.index(a)] for a in labels]
...     s_name = ','.join(dumb_labels)
...     return(s_name)
... 
>>> def f_dict(labels):
...     uniq_labels = {l: i for i, l in enumerate(sorted(set(labels)))}
...     dumb_labels = [dumb_label_set[uniq_labels[a]] for a in labels]
...     s_name = ','.join(dumb_labels)
...     return s_name
... 
>>> labels = []
>>> for i1 in range(100):
...     labels.append([''.join(random.choice(string.ascii_letters) for ii in range(random.randint(1,4))) for i2 in range(4)])
... 
>>> timeit.timeit('[f(l) for l in labels]', 'from __main__ import f, labels', number=10000)
6.586822032928467
>>> timeit.timeit('[f(l) for l in labels]', 'from __main__ import f_dict as f, labels', number=10000)
7.633307933807373

しかし、ご覧のとおり、入力セットが小さい場合は、メソッドの方が高速です。.index()マッピングの設定には、最大 4 回のルックアップよりも時間がかかるようです。

ラベル シーケンスが (はるかに) より多くの要素で構成されている場合、私の方法が勝ちます。

>>> dumb_label_set = string.ascii_uppercase
>>> labels = []
>>> for i1 in range(100):
...     labels.append([''.join(random.choice(string.ascii_letters) for ii in range(random.randint(1,4))) for i2 in range(26)])
... 
>>> timeit.timeit('[f(l) for l in labels]', 'from __main__ import f, labels', number=1000)
3.069930076599121
>>> timeit.timeit('[f(l) for l in labels]', 'from __main__ import f_dict as f, labels', number=1000)
2.404794931411743

ここでの最も重要な教訓は、timeitモジュールを使用してさまざまな方法を比較することです。このtimeitモジュールは、プラットフォームに最適なタイマーを使用し、テスト対象のコードの多くの実行を比較して、外部のスケジューリングの影響 (ディスク I/O、他のプロセスなど) を排除します。

1回だけ実行する場合でも、 を使用するよりも を使用するtimeit.default_timer方が望ましいtime.timeです。タイマーは同じかもしれませんが、プラットフォームにとって最も正確な時計になります。

于 2012-12-30T10:03:40.070 に答える
1

これを本当に素早く動かしたい場合は、cython も見てください。もちろん、ここで他の提案されたアルゴリズムを見てください。ただし、最速のアルゴリズムを選択すると、cython はそれを十分に後押しすることができます。

現在、元のメソッドaとを使用していますbが、変更せずに別のモジュールに移動し、cython と gcc (-O3) でコンパイルしました。型情報がなければ、次の時間を取得しました。

a:          0.4449379859997862
b:          0.48829928699888114
a (cython): 0.29741462399942975
b (cython): 0.2461447869991389

変数のタイプをマークすることで、さらに後押しできると確信しています。

于 2013-05-11T19:57:19.297 に答える