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

Question

我在pygame中用python(2.7)编写了一个简单的游戏.在这个游戏中,我必须存储2D坐标.这些项目的数量将从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.0,700.0).

我搜索了这个,但存储的值是字符串或常数.

Answer 1

在列表旁边保留一个集合,或者如果您没有其他用途,则完全替换列表.对于集合,成员资格检查和添加平均为O(1),因此与仅使用列表的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)

Answer 2

如果我理解正确，则说明您正在向中添加元素myList，但永远不要删除它们。然后，您将测试中的每个成员valuesToCheck资格myList。

如果是这样，您可以通过将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)