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

我试图获取一个点的给定半径内的玩家列表，并按照他们到该点的距离排序。获取玩家很简单：将列表元素添加到正确的排序位置

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两次？

来源

2015-02-23 Markus Meskanen

您的目标是找到最接近的球员，还是始终让所有球员以完全排序的顺序？ – 2015-02-23 11:30:07

即使你这样做，你仍然会排序。 – 2015-02-23 11:30:40

@MartijnPieters我试图创建一个函数，返回一个点的半径范围内的所有玩家，按照他们到那个点的距离排序。 – 2015-02-23 11:31:43

作为使用排序数据结构的另一种方法（如Martijn Pieters所建议的），您可以将距离信息与播放器对象组合起来。您可以通过将其作为属性添加到玩家类中，或者通过将每个玩家实例与其距离信息暂时组合来实现。例如，

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]

来源

2015-02-23 11:44:41

这有助于稍后插入其他玩家吗？ – 2015-02-23 11:45:27

@MartijnPieters：我不知道马库斯想做那件事。我感觉距离值是暂时的，每次球员移动时都需要重新计算。所以目前的订单也只是暂时的。 – 2015-02-23 11:49:54

@ PM2Ring你说得对，我不需要这样的行为，如果他们在我调用函数的那一刻进行排序就足够了。 – 2015-02-23 11:53:20

如果距离确实是在欧几里得空间上的距离，你可以使用是某种空间隔离算法，如quadtree为2D，或octree为3D;

如果您有静态设置，则不需要空间分区。但是，如果您有一个具有多个参考点的动态集合，或者参与者正在移动，则这些方法比计算距离（O(kn)距离计算）效率更高，然后计算每个操作的总计至少O(kn)个每个操作的最近距离你计算距离。

参见相关C++ discussion。

来源

2015-02-23 11:45:59

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

回答

相关问题