Python - минимум списка кортежей с помощью min(list, key=func), как повысить эффективность

Учитывая список templates кортежей (region, calc_3d_harmonics(region)) где calc_3d_harmonics это какая-то функция, которая возвращает подпись для каждого региона, мне нужно найти регион с минимальным баллом (фактический балл не имеет значения).

Оценка региона дается calc_harmonics_distance(calc_3d_harmonics(region),query_harmonics, radius)- функция, которая вычисляет расстояние между двумя гармоническими сигнатурами с учетом некоторого радиуса (query_harmonics и radius рассчитываются заранее).

Мое текущее решение:

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

Член команды предложил использовать вместо этого следующее:

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 очень медленные и тяжелые функции. Также, score можно заменить на _,

Он утверждает, что его предложение может привести к лучшему времени выполнения (хотя оно не будет значительным, поскольку функции гармоник являются основными операциями). Если min(list, key=func) создает список ключей, тогда наши версии эквивалентны (и моя короче), но если он вычисляет ключ каждый раз, когда он думает, что моя будет медленнее.

Какой путь быстрее? Я думаю, что должен быть лучший (с точки зрения времени выполнения) способ сделать это (возможно, используя numpy?) И хотел бы услышать некоторые предложения.

Источник

2 ответа

Решение

min(lst, key=func) звонки func один раз на каждом предмете lst (и это также относится к ключевой функции max, list.sort а также sorted). Так что если lst содержит дублированные элементы, тогда функция клавиш выполняет ненужную работу, если только вы не используете функцию клавиш для запоминания.

Чтобы проиллюстрировать это, вот пара ключевых функций, которые печатают свои аргументы при вызове. 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
Источник

Если сомневаешься, не угадай, профилируй.

Оставляя весь ваш код позади, мы можем обратиться к реализации cPython. Мы это видим min функция использует min_max помощник В этом помощнике мы можем найти, где вычисляется ключевая функция.

Минимальная выдержка будет:

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
}

Исходный код четко утверждает, что ключевая функция вычисляется один раз для каждого элемента в отсортированном итерируемом. С другой стороны, результат ключевой функции отбрасывается после завершения сортировки. Таким образом, дело сводится к тому, если вы планируете повторно использовать значения ключевых функций позже.

Источник
Другие вопросы по тегам