Найти ближайшую ценность в словаре

У меня есть словарь, T, с ключами в форме k,i со связанным значением, которое является реальным числом (поплавок). Давайте предположим, что я выбрал конкретный ключ a,b из словаря T с соответствующим значением V1 -что это наиболее эффективный способ найти наиболее близкое значение к V1 для ключа, который имеет форму a+1,i, где i представляет собой целое число, которое находится в диапазоне от 0 до п? (k, a и b также целые числа.) Чтобы добавить одно условие от значений элементов в T, так как i увеличивается в ключе, значение, связанное с T[a+1,i] строго возрастает (то есть T[a+1,i+1] > T[a+1,i]).Найти ближайшую ценность в словаре

Я планировал просто запустить цикл while, который начинается с i = 0 и сравнивает значение T[a+1,i] с V1. Чтобы быть более понятным, цикл просто остановится в точке, где np.abs(T[a+1,i] - V1) < np.abs(T[a+1,i+1] - V1), так как я знаю, что элемент, связанный с T[a+1,i], находится ближе всего к T[a,b] = V1. Но учитывая строго возрастающее условие, которое я наложил, существует ли более эффективный метод, чем запуск цикла while, который выполняет итерации над элементами словаря? i будет идти от 0 до n, где n может быть целым числом в миллионах. Кроме того, этот процесс будет повторяться часто, поэтому эффективность является ключевой.

источник

2016-09-15 Mathews24

* ключи в форме k, i *, означает ли это, что словарь является своего рода двухмерным массивом? – Jeon

@Jeon Да, это похоже на 2D-массив (например, увеличение времени с увеличением i). Словарь был выбран для обеспечения неравномерного расстояния. Хотя одна из (второстепенных) проблем - это выяснить, как вещи устроены просто на основе ключей. – Mathews24

@MoinuddinQuadri Это не задание ... Это персональный проект с неравномерной сеткой. Я хотел бы найти хороший метод для вычисления пространственных производных. Я пытаюсь найти самое близкое значение для моей текущей точки (например, 'V1'), чтобы вычислить численный дифференциал. Я еще не реализовал конкретный метод, так как он должен быть добавлен в другой код для решения набора PDE. Хотя до изменения моего кода (только для того, чтобы снова изменить его в конце, если я узнаю о лучших методах), я подумал, что заранее спрошу, существуют ли более эффективные методы, о которых я просто не подозреваю. – Mathews24

Поскольку значения для заданного a строго возрастают с последующими значениями i, вы можете выполнить двоичный поиск для значения, которое ближе всего к вашей цели.

Хотя, конечно, вы можете написать свой собственный двоичный код поиска в своем словаре, я подозреваю, что вам будет проще с другой структурой данных. Если вы использовали вложенные списки (с a в качестве индекса во внешний список и i как индекс для внутреннего списка), вы можете использовать модуль bisect для эффективного поиска внутреннего списка.

источник

2016-09-15 17:40:03 Blckknght

Использование словаря - это ограничение для других целей в коде, поэтому, к сожалению, другая структура данных не является вариантом. Я рассмотрю существующие двоичные коды поиска. Спасибо за предложения. Я нашел код, такой как 'idx1 = np.array (T.keys())' ' vals1 = np.array (T.values ())' ' dims1 = idx1.max (0) + 1' 'out1 = np.zeros (dims1, dtype = vals1.dtype) ' ' out1 [idx1 [:, 0], idx1 [:, 1]] = vals1' , который мог бы помочь, но преобразование dict в массив за каждый раз может быть еще более неэффективным, так как один раз опять же дикт неравномерен и обновляется. – Mathews24

import numpy as np 

target_value = 0.9 
dict = {(1, 2): 0, (4, 3): 1} 

k = list(dict.keys()) 
v = np.array(list(dict.values())) 
dist = abs(v - target_value) 
arg = np.argmin(dist) 
answer = k[arg] 

print(answer)

источник

2016-09-15 17:52:47 Jeon

Благодарим вас за предложение. Как я уже говорил выше на другом ответе, создание массива для каждого экземпляра, который я хочу сделать, будет неэффективным, поскольку весь смысл использования dict заключается в том, что сетка неоднородна и постоянно обновляется. Таким образом, массив, сделанный здесь, должен был бы выполняться каждый отдельный экземпляр, который я делаю для сравнения (который также может быть в миллионах), поскольку dict будет обновлен, и я подозреваю, что это будет довольно неэффективно. Хотя я попробую и сравню. – Mathews24

Включая numpy - полный перебор – Andrey

Предлагаю использовать модуль bisect.

import bisect 
import numpy as np 


t = np.array([[1.1, 2.0, 3.7], 
       [3.5, 5.6, 7.8], 
       [2.5, 3.4, 10.0]]) 


def find_closest(t, a, i): 
    """ 
    >>> find_closest(t, 0, 2) 
    (1, 0) 
    """ 
    v = t[a, i] 
    b_index = bisect.bisect_right(t[a + 1], v) 
    try: 
     if t[a + 1][b_index] - v > t[a + 1][b_index - 1] - v: 
      b_index -= 1 
    except IndexError: 
     pass 
    return a + 1, b_index

источник

2016-09-15 20:06:51 gavriel

Найти ближайшую ценность в словаре

ответ

Смежные вопросы