用python存储和搜索坐标的有效方法

Question

我在pygame中用python（2.7）编写一个简单的游戏。在这个游戏中，我必须存储二维坐标。这些项目的数量将从0开始，每一步增加2个。他们将增加到大约6000人。在每一步中，我都要检查其中是否有9个特定的坐标。我试图将它们简单地存储在（x，y）列表中，但是在这样的列表中搜索是不有效的。

如何存储这些坐标，以便在它们之间进行搜索更有效？

我每一步都要做的是：

# 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.0700.0）。

我已经对此进行了搜索，但存储的值不是字符串就是常量。

Answer 1

如果我理解正确，您将向myList添加元素，但从不删除它们。然后在myList中测试valuesToCheck的每个元素的memebership。

如果是这样，可以通过将myList转换为set而不是list来提高性能。测试列表中的成员身份是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)

Answer 2

在列表旁边维护一个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)