Найдите k элементов dict, значения которых ближе всего к определенному значению

Question

Допустим, мы хотим найти 2 элемента, стоимость которых ближе всего к 10:

A = {'abc': 12.3, 'def': 17.3, 'dsfsf': 18, 'ppp': 3.2, "jlkljkjlk": 9.23}

Работает с:

def nearest(D, centre, k=10):
    return sorted([[d, D[d], abs(D[d] - centre)] for d in D], key=lambda e: e[2])[:k]

print(nearest(A, centre=10, k=2))

[['jlkljkjlk', 9.23, 0.7699999999999996], [' abc ', 12.3, 2.3000000000000007]]

Но есть ли встроенный в Python способ сделать это и / или более оптимизированная версия, когдаdict имеет гораздо больший размер (сотни тысяч предметов)?

Answer 1

Вы можете использовать heapq.nsmallest():

from heapq import nsmallest
A = {'abc': 12.3, 'def': 17.3, 'dsfsf': 18, 'ppp': 3.2, 'jlkljkjlk': 9.23}
def nearest(D, centre, k=10):
    return [[x, D[x], abs(D[x] - centre)] for x in nsmallest(k, D, key=lambda x: abs(D[x] - centre))]

print(nearest(A, centre=10, k=2))
# [['jlkljkjlk', 9.23, 0.7699999999999996], ['abc', 12.3, 2.3000000000000007]]

Что касается сложности времени, это выполняется за O(n log(k)) время вместо O(n log(n)) решения, основанного на сортировкесловарь.

Answer 2

Учитывая, что вам нужно выполнять поиск довольно часто, мы можем сделать это алгоритмом O (log n) , сначала сохранив данные в отсортированном списке:

from operator import itemgetter

ks = sorted(A.items(), key=itemgetter(1))
vs = list(map(itemgetter(1), ks))

Тогда для каждого элемента мы можем использовать точку bisect.bisect_left, чтобы определить точку вставки.Затем мы можем проверить два окружающих значения, проверить наименьшее и вернуть соответствующий ключ.Также возможно, что

from bisect import bisect_left
from operator import itemgetter

def closests(v):
    idx = bisect_left(vs, v)
    i, j = max(0, idx-1), min(idx+2, len(ks))
    part = ks[i:j]
    return sorted([[*pi, abs(pi[-1]-v)] for pi in part], key=itemgetter(-1))[:2]

Вышеприведенное может не выглядеть улучшением, но здесь мы всегда будем оценивать самое большее три элемента в sorted(..), и bisect_left будетоцените логарифмическое количество элементов.

Например:

>>> closests(1)
[['ppp', 3.2, 2.2], ['jlkljkjlk', 9.23, 8.23]]
>>> closests(3.2)
[['ppp', 3.2, 0.0], ['jlkljkjlk', 9.23, 6.03]]
>>> closests(5)
[['ppp', 3.2, 1.7999999999999998], ['jlkljkjlk', 9.23, 4.23]]
>>> closests(9.22)
[['jlkljkjlk', 9.23, 0.009999999999999787], ['abc', 12.3, 3.08]]
>>> closests(9.24)
[['jlkljkjlk', 9.23, 0.009999999999999787], ['abc', 12.3, 3.0600000000000005]]

Фаза "загрузки", таким образом, занимает O (n log n) (с n количеством элементов).Затем, если мы обобщим описанный выше метод для извлечения k элементов (путем увеличения среза), потребуется O (log n + k log k) , чтобы выполнить поиск.

Answer 3

Если вы не возражаете против использования панд:

import pandas as pd
closest = (pd.Series(A) - 10).abs().sort_values()[:2]
#jlkljkjlk    0.77
#abc          2.30
closest.to_dict()
#{'jlkljkjlk': 0.7699999999999996, 'abc': 2.3000000000000007}