將列表元素添加到正確的排序位置

我試圖獲取一個點的給定半徑內的玩家列表，並按照他們到該點的距離排序。獲取玩家很簡單：將列表元素添加到正確的排序位置

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

將列表元素添加到正確的排序位置

回答

相關問題