在Python中存儲和搜索座標的有效方法

我正在pygame中編寫一個簡單的Python（2.7）遊戲。在這個遊戲中，我必須存儲2D座標。這些項目的數量將從0開始並在每一步中增加2。他們會增加到6000。在每一步中，我都要檢查其中是否有9個特定的座標。我嘗試將它們簡單地存儲在列表中（x，y），但在這樣的列表中搜索效率不高。在Python中存儲和搜索座標的有效方法

如何存儲這些座標，以便在它們之間搜索效率更高？

我試圖在每一個步驟做：

# Assuming: 
myList = [] 
co1 = (12.3,20.2) # and so on.. 
valuesToCheck = [co1,co2,co3,co4,co5,co6,co7,co8,co9] 

# In each step: 
# Adding 2 coordinates 
myList.append((x1,y1)) 
myList.append((x2,y2)) 
# Searching 9 specific coordinates among all 
for coordinate in valuesToCheck: 
    if coordinate in myList: 
     print "Hit!" 
     break 
# Note that the valuesToCheck will change in each step. 
del valuesToCheck[0] 
valuesToCheck.append(co10)

座標是浮點數，他們的最高價值是有限的。他們從（0.0,0.0）到（1200.0,700.0）。

我搜索了這個，但存儲的值是字符串或常數。

來源

2013-04-01 Sweeney Todd

是你需要的座標集做的唯一的搜索是9個特殊座標是否在那裏？這9個特殊的座標是否會改變（如果沒有，爲什麼不扔掉不匹配的2D點）？你需要在你的觀點上進行任何其他搜索？ – angelatlarge

正如我在代碼部分中所添加的，這9個特殊座標也在每一步中改變。雖然沒有其他搜索要做。 –

在這種情況下，我會保持簡單並使用字典。 http://stackoverflow.com/questions/1938614/in-what-case-would-i-use-a-tuple-as-a-dictionary-key – YXD

在列表旁邊保留set，或者在沒有其他用途的情況下完全替換列表。成員檢查和添加的集合爲O(1) on average，所以與僅使用列表的O（N^2）相比，您的總體算法將爲O（N）。

myList = [] 
mySet = set() 
co1 = (12,20) # and so on.. 
valuesToCheck = [co1,co2,co3,co4,co5,co6,co7,co8,co9] 

# In each step: 
# Adding 2 coordinates 
myList.append((x1,y1)) 
myList.append((x2,y2)) 
mySet.add((x1, y1)) 
mySet.add((x2, y2)) 
# Searching 9 specific coordinates among all 
for coordinate in valuesToCheck: 
    if coordinate in mySet: 
     print "Hit!" 
     break 
# Note that the valuesToCheck will change in each step. 

del valuesToCheck[0] 
valuesToCheck.append(co10)

來源

2013-04-01 20:02:19 Kevin

使用一套比使用字典更有效嗎？還有更復雜但有效的方法嗎？（我正在尋找[** Kd樹**]（http://en.wikipedia.org/wiki/K-d_tree）@angelatlarge建議） –

據我瞭解，集實現爲由後端，所以效率將是一樣的。我不知道更有效的方法，儘管我不能貶低它們的存在。 – Kevin

如果我理解正確，您將向myList添加元素，但不會刪除它們。然後，您在myList中測試valuesToCheck中的所有元素。

如果是這種情況，可以通過將myList轉換爲一個集合而不是一個列表來提高性能。測試列表中的成員資格是O（n），而測試集合中的成員資格通常是O（1）。

你的語法將保持不變，主要是：

mySet = set() 

# your code 

# Adding 2 coordinates 
mySet.add((x1,y1)) 
mySet.add((x2,y2)) 
# Searching 9 specific coordinates among all 
for coordinate in valuesToCheck: 
    if coordinate in mySet: 
     print "Hit!" 
     break 
# Note that the valuesToCheck will change in each step. 
del valuesToCheck[0] 
valuesToCheck.append(co10)

來源

2013-04-01 20:03:06 dckrooney

使用set會比使用dict更高效嗎？還有更復雜但有效的方法嗎？（我正在尋找[鏈接]（http://en.wikipedia.org/wiki/K-d_tree）** Kd樹**。@angelatlarge建議） –

@ SweeneyTodd-如果你所做的只是檢查會員資格，「dict」和「set」將執行基本相同的操作。關於更復雜的方法：我會首先考慮制定一些指標，以確定這部分代碼在「足夠好」之前需要多快。不成熟的優化是所有邪惡的根源和所有:) – dckrooney

在Python中存儲和搜索座標的有效方法

回答

相關問題