从词典列表中获取最接近的元素

Question

我的程序生成以下列表(摘录):

my_list = [{'x': 1764, 'y': 18320, 'class': 'note', 'id': 'd1e2443'},
           {'x': 1764, 'y': 20030, 'class': 'note', 'id': 'd1e2591'},
           {'x': 1807, 'y': 12650, 'class': 'note', 'id': 'd1e1362'},
           {'x': 2243, 'y': 20120, 'class': 'note', 'id': 'd1e2609'},
           {'x': 2243, 'y': 22685, 'class': 'note', 'id': 'd1e2769'},
           {'x': 2257, 'y': 12560, 'class': 'note', 'id': 'd1e1380'},
           {'x': 2688, 'y': 20210, 'class': 'note', 'id': 'd1e2625'},
           {'x': 2707, 'y': 10040, 'class': 'note', 'id': 'd1e1194'},
           {'x': 2707, 'y': 12650, 'class': 'note', 'id': 'd1e1398'},
           {'x': 2707, 'y': 14720, 'class': 'note', 'id': 'd1e1571'},
           {'x': 2901, 'y': 18140, 'class': 'note', 'id': 'd1e2475'}]

它已经按'x'键的值排序.我正在尝试编写一个方法,该方法返回给定坐标的此列表的两个元素的元组(xPos, yPos):

• 左边最近的元素(x <= xPos)
• 最右边的元素(x > xPos)

距离只是欧几里德距离("毕达哥拉斯").该函数的第二个参数是允许的最大距离:

def getNearest(noteList, posX, posY, maxDistance):
    [...]
    return leftElement, rightElement

我试图使用bisect函数分别得到最接近元素的插入点xPos以及xPos - maxDistance(case'left')和xPos + maxDistance(case'right),以缩小搜索范围.然后我计算了这个切片列表中每个剩余元素的距离

不知何故,这感觉非常不优雅.有没有更好的方法呢？

编辑: 也许我的意图并不是很清楚:我需要列表中的两个元素."2D窗格"中最近的元素位于左侧,一个位于右侧.因此我也需要考虑y坐标.

可能会发生(实际上几乎每次)关于其x坐标的最接近的元素比具有近y坐标的元素更远.

Answer 1

我尝试将我最初的想法与答案中的一些建议合并起来。这就是我想出的：

class translatedDictList(object):
    def __init__(self, dictList, key):
        self.dictList = dictList
        self.key = key

    def __getitem__(self, item):
        return self.dictList[item][self.key]

    def __len__(self):
        return self.dictList.__len__()

def getNearest(self, symbolList, pos, maxDistance):
    translatedList = translatedDictList(symbolList, 'x')

    splitIndex = bisect.bisect(translatedList, pos[0])
    minIndex = bisect.bisect(translatedList, pos[0] - maxDistance)
    maxIndex = bisect.bisect(translatedList, pos[0] + maxDistance)

    # Euclidean distance acutally not needed anymore!
    leftElement = min(symbolList[minIndex:splitIndex],
                      key=lambda n: abs(n['x'] - pos[0]) +
                                    abs(n['y'] - pos[1]))
    rightElement = min(symbolList[splitIndex:maxIndex],
                       key=lambda n: abs(n['x'] - pos[0]) +
                                     abs(n['y'] - pos[1]))

    return leftElement, rightElement

print(getNearest(self.symbolsSorted, (1200, 1500), 1000))

也许有一种更聪明的方法来翻译 insymbolList以便使用bisect()？

应该是o(log*n)，据我所知，我什至不再需要计算欧几里德距离，因为我只是比较，对实际距离不感兴趣。