Python - Minimum of list of tuples using min(list, key=func) how to improve efficiency
<p>Given a list <code>templates</code> of tuples <code>(region, calc_3d_harmonics(region))</code> where <code>calc_3d_harmonics</code> is some function that returns a signature for each region, I need to find the region with the minimal score (the actual score doesn't matter).</p>

<p>The score of a region is given by <code>calc_harmonics_distance(calc_3d_harmonics(region),query_harmonics, radius)</code>, a function that calculates the distance between two harmonic signatures given some radius (query_harmonics and radius are computed beforehand). </p>

<p>My current solution is:</p>

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

<p>A team member suggested that I use the following instead:</p>

<pre><code>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])
</code></pre>

<p>Note: Both <code>calc_3d_harmonics</code> and <code>calc_harmonics_distance</code> are very slow and heavy functions. Also, <code>score</code> can be replace by <code>_</code>.</p>

<p>He claims that his suggestion might result in a better runtime (although it would not be significant since the harmonics functions are the major operations). If <code>min(list, key=func)</code> creates a list of the keys, then our versions are equivalent (and mine's shorter), but if it computes the key every time he thinks mine will be slower.</p>

<p>Which way is faster? I think there must be a better (runtime-wise) way to do this (perhaps using numpy?) and would like to hear some suggestions.</p>

<p><code>min(lst, key=func)</code> calls <code>func</code> once on each item of <code>lst</code> (and that also applies to the key function of <code>max</code>, <code>list.sort</code> and <code>sorted</code>). So if <code>lst</code> contains duplicated items then the key function does unnecessary work, unless you use a memoizing key function.</p>

<p>To illustrate, here are a couple of key functions that print their arg when called. <code>kf</code> is a normal key function, <code>kf_cached</code> uses a default mutable dictionary to do memoizing.</p>

<pre><code>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)
</code></pre>

<p><strong>output</strong></p>

<pre><code> Key 1
 Key 4
 Key 1
 Key 4
 Key 2
max 4 

 Key 1
 Key 4
 Cached 1
 Cached 4
 Key 2
max 4
</code></pre>

python list numpy tuples min