6

我正在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)。

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

4

2 回答 2

7

在您的列表旁边保留一组，或者如果您没有其他用途，则完全替换该列表。集合的成员资格检查和添加平均为 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)
于 2013-04-01T20:02:19.907 回答
5

如果我理解正确，您正在向 中添加元素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)
于 2013-04-01T20:03:06.933 回答