Python - min（list、key = func）を使用するタプルの最小リスト効率を改善する方法

Question

タプルのリストtemplates(region, calc_3d_harmonics(region))ここで、calc_3d_harmonicsは各地域の署名を返す関数です。最小スコア（実際のスコアは関係ありません）。

領域のスコアは、calc_harmonics_distance(calc_3d_harmonics(region),query_harmonics, radius)で与えられます。これは、いくつかの半径（query_harmonicsとradiusは事前に計算されています）を指定した2つの高調波シグネチャ間の距離を計算する関数です。

私の現在のソリューションは、次のとおりです。

query_harmonics = calc_3d_harmonics(query_region) 
ref_region, score = min([(t[0], calc_harmonics_distance(t[1], query_harmonics, radius)) for t in templates], key=lambda x: x[1]) 

注：calc_3d_harmonicsとcalc_harmonics_distanceの両方が非常に遅く、重い機能です

query_harmonics = calc_3d_harmonics(query_region) 
ref_region, score = min(templates, key=lambda t: calc_3d_harmonics_distance(t[1], query_harmonics, radius)) 

チームのメンバーは、私が代わりに以下を使用することを示唆しました。またscoreは_で置き換えることができます。

彼の提案は、高調波機能が主要な操作であるため重要ではないが、より良い実行時間をもたらすと主張する。 min(list, key=func)が鍵のリストを作成した場合、私たちのバージョンは同等であり、私のバージョンはより短いですが、私が思うたびに鍵を計算すると、私のバージョンは遅くなります。

どちらが速いのですか？私はこれを行うには（実行時に）より良い方法が必要であると思います（おそらくnumpyを使用していますか？）、いくつかの提案を聞いてみたいと思います。

Answer 1

min(lst, key=func)はlstの各項目に一度funcを呼び出し（それはまたmax、list.sortとsortedのキー機能に適用されます）。したがって、lstに重複した項目が含まれている場合、メモ機能を使用しない限り、キー機能は不要な作業を行います。

ここでは、呼び出されたときにargを表示する2つの重要な関数を示します。 kfは通常のキー機能です。kf_cachedは、デフォルトの変更可能な辞書を使用してメモをとります。

def kf(n): 
    print(' Key', n) 
    return int(n) 

def kf_cached(n, cache={}): 
    if n in cache: 
     print(' Cached', n) 
     return cache[n] 
    print(' Key', n) 
    cache[n] = k = int(n) 
    return k 

a = '14142' 

u = max(a, key=kf) 
print('max', u, '\n') 

u = max(a, key=kf_cached) 
print('max', u) 

出力

Key 1 
Key 4 
Key 1 
Key 4 
Key 2 
max 4 

Key 1 
Key 4 
Cached 1 
Cached 4 
Key 2 
max 4 

Answer 2

疑わしいときは、profile itを推測しないでください。

すべてのコードを隠しておくと、cPythonの実装を参照することがあります。我々は、min関数がmin_max helperを使用していることがわかります。 このヘルパーでは、key function is computedの場所を見つけることができます。

最小限の抜粋は次のようになります。

while ((item = PyIter_Next(it))) { 
    /* get the value from the key function */ 
    if (keyfunc != NULL) { 
     val = PyObject_CallFunctionObjArgs(keyfunc, item, NULL); 
     if (val == NULL) 
      goto Fail_it_item; 
    } 
    /* no key function; the value is the item */ 
    else { 
     val = item; 
     Py_INCREF(val); 
    } 
    // comparision logic for min/max 
} 

ソースコードの状態が明確にそのキーの機能は、ソートされた反復可能な内の各要素に対して一度計算されます。一方、ソートが完了すると、キー関数の結果が破棄されます。したがって、後で主要な関数値を再利用することを計画している場合は、ケースが発生します。