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>When in doubt, do not guess, <a href="https://docs.python.org/3/library/profile.html" rel="nofollow">profile it</a>.</p>

<p>Putting all of your code behind, we may refer to cPython implementation. We can see, that <code>min</code> function uses <a href="https://github.com/python/cpython/blob/master/Python/bltinmodule.c#L1482" rel="nofollow"><code>min_max</code> helper</a>. 
In this helper we can locate where <a href="https://github.com/python/cpython/blob/master/Python/bltinmodule.c#L1520" rel="nofollow">key function is computed</a>.</p>

<p>Minimal excerpt would be:</p>

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

<p>Source code states clearly that key function is computed once for each element in sorted iterable. On the other hand, key function result is thrown away after sorting is complete. So case comes down to if you are planning on reusing key function values later.</p>

python list numpy tuples min