在字典中查找最接近的值

我有一本字典，T，其形式为k,i，其关联值为实数（float）。假设我从字典T中选择了一个特定的密钥a,b，对应的值为V1 - 对于具有a+1,i形式的密钥找到最接近V1的值的最有效方法是什么？i是整数，范围从0到n？（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阵列（例如，随着我的增加，时间越来越长）。一本字典被选来允许不均匀的间距。尽管其中一个（次要）问题是根据键来确定事物的排列方式。 – 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

谢谢你的建议。正如我在上面提到的另一个答案中所做的那样，为每个实例创建一个数组我会这样做，因为使用字典的整个观点是因为网格不均匀并且不断更新，所以效率会很低。所以在这里做的数组必须做每一个我做比较的实例（这也可能是数百万），因为字典将被更新，我怀疑这将是非常低效的。尽管我会尝试一下并进行比较。 – 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

在字典中查找最接近的值

回答

相关问题