将列表元素附加到正确的排序位置

Question

我试图得到一个给定半径范围内的玩家列表，并按他们到该点的距离排序。 获得玩家很简单：

players = [
    player for player in Player.instances
    if player.distance(my_point) <= max_radius
]

分类也很好：

return sorted(players, key=lambda player: player.get_distance(my_point))

但是，如果服务器上满是玩家，那么为每个人调用player.distance(my_point)可能会变得很繁重，因此在之后对玩家进行排序总是需要一些额外的时间。 有没有一种方法可以在添加玩家时自动对列表进行排序，这样我就不必在每个人中循环两次并调用getdistance两次？你知道吗

Answer 1

作为使用排序数据结构的替代方法（如martijnpieters所建议的），您可以将距离信息与player对象相结合。您可以通过将其作为属性添加到player类中，或者通过临时将每个player实例与其距离信息相结合来实现这一点。例如

players = []
for player in Player.instances:
    dist = player.distance(my_point)
    if dist <= max_radius:
        players.append((dist, player))

#Sort in order of distance. If two distances match, sort by player.
players.sort()

#Strip out dist info
players = [v for u,v in players]

#or
players = zip(*players)[1]

Answer 2

如果这个距离确实是欧几里德空间中的距离，那么你可以使用某种空间划分算法，比如quadtree表示2D，或者octree表示3D

如果您有一个静态集，那么就不需要进行空间分区。但是如果你有一个有许多参考点的动态集合，或者玩家正在移动，那么这些方法比每次计算距离时，计算距离（O(kn)距离计算）然后为每个操作计算最近的距离要有效得多。你知道吗

另请参见相关的C++ discussion。你知道吗