2

由这个问题的评论提出（我可以看到这无关紧要），我现在意识到使用字典来获取需要定期查询/访问的数据并不好，速度很快。

我有这样的情况：

someDict = {}
someDict[(-2, -2)] = something
somedict[(3, -10)] = something else

我将坐标键存储到在游戏中充当图块数组的对象。这些在某些时候会是负面的，所以我不能使用列表或某种稀疏数组（我认为这是术语？）。

我可以：

  • 加快字典查找速度，所以这不是问题
  • 找到某种支持稀疏负索引的容器？

我会使用一个列表，但随后查询将从 O(log n) 到 O(n) 以找到 (x, y) 处的区域。（我想我的时间也在这里）。

4

5 回答 5

2

开始

加快字典查找速度，所以这不是问题

字典查找非常快 O(1)，但是（根据您的另一个问题）您不依赖于字典的哈希表查找，而是依赖于字典键的线性搜索。

找到某种支持稀疏负索引的容器？

这不是对字典的索引。元组是一个不可变对象，您将整个元组散列。字典真的不知道键的内容，只是它们的哈希。

和其他人一样，我将建议您重组数据。

例如，您可以创建封装所需数据的对象，并将它们排列在二叉树中以进行 O(n lg n) 搜索。您甚至可以将整个内容包装在一个类中，该类将为您提供所需的良好if foo in Bar:语法。

你可能需要几个协调的结构来完成你想要的。这是一个使用 dicts 和 sets 的简化示例（稍微调整用户 6502 的建议）。

# this will be your dict that holds all the data
matrix = {}
# and each of these will be a dict of sets, pointing to coordinates
cols = {}
rows = {}

def add_data(coord, data)
    matrix[coord] = data
    try:
        cols[coord[0]].add(coord)
    except KeyError:
        # wrap coords in a list to prevent set() from iterating over it
        cols[coord[0]] = set([coord])
    try:
        rows[coord[1]].add(coord)
    except KeyError:
        rows[coord[1]] = set([coord])

# now you can find all coordinates from a row or column quickly
>>> add_data((2, 7), "foo4")
>>> add_data((2, 5), "foo3")
>>> 2 in cols
True
>>> 5 in rows
True
>>> [matrix[coord] for coord in cols[2]]
['foo4', 'foo3']

现在只需将其包装在一个类或一个模块中，您就会离开，并且一如既往，如果它不够快，请在您猜测之前进行配置和测试。

于 2011-03-11T20:16:06.070 回答
2

Python 字典非常非常快，使用整数元组不会成为问题。但是，您的用例似乎有时您需要进行单坐标检查，并且遍历所有字典当然很慢。

但是，您可以使用三个字典来加快数据结构的访问速度，而不是进行线性搜索：

class Grid(object):
    def __init__(self):
        self.data = {}  # (i, j) -> data
        self.cols = {}  # i -> set of j
        self.rows = {}  # j -> set of i

    def __getitem__(self, ij):
        return self.data[ij]

    def __setitem__(self, ij, value):
        i, j = ij
        self.data[ij] = value
        try:
            self.cols[i].add(j)
        except KeyError:
            self.cols[i] = set([j])
        try:
            self.rows[j].add(i)
        except KeyError:
            self.rows[j] = add([i])

    def getRow(self, i):
        return [(i, j, data[(i, j)])
                for j in self.cols.get(i, [])]

    def getCol(self, j):
        return [(i, j, data[(i, j)])
                for i in self.rows.get(j, [])]

请注意，还有许多其他可能的数据结构，具体取决于您要执行的操作、阅读频率、更新频率、是否按矩形查询、是否查找最近的非空单元格等等。

于 2011-03-11T20:33:36.400 回答
1

一种选择是简单地移动索引，使其为正。

例如，如果您的索引是这样连续的：

...
-2 -> a
-1 -> c
0 -> d
1 -> e
2 -> f
...

只需执行 LookupArray[Index + MinimumIndex] 之类的操作，其中 MinimumIndex 是您将使用的最小索引的绝对值。

这样，如果您的最小值是 -50，它将映射到 0。-20 将映射到 30，依此类推。

编辑：

另一种方法是在使用索引的方式上使用技巧。定义如下键函数

Key(n) = 2 * n (n >= 0)
Key(n) = -2 * n - 1. (n < 0)

这会将所有正键映射到正偶数索引，并将所有负元素映射到正奇数索引。但这可能不切实际，因为如果添加 100 个否定键，则必须将数组扩展 200。

另一件需要注意的事情：如果您打算进行查找并且键的数量是恒定的（或非常缓慢地变化），请坚持使用数组。否则，字典一点也不差。

于 2011-03-11T20:16:55.933 回答
1

字典查找非常快。搜索键的一部分（例如第 x 行中的所有图块）并不快。你可以使用字典的字典。而不是由 2 元组索引的单个 dict，而是使用这样的嵌套 dict：

somedict = {0: {}, 1:{}}
somedict[0][-5] = "thingy"
somedict[1][4] = "bing"

然后，如果您想要给定“行”中的所有图块，则只需somedict[0].

您将需要一些逻辑来在必要时添加辅助字典等等。提示：检查标准类型getitem()，或者可能是类型。setdefault()dictcollections.defaultdict

这种方法使您可以快速访问给定行中的所有图块。如果您想要给定列中的所有图块，它仍然很慢（尽管至少您不需要查看每个单元格，只需要查看每一行）。但是，如果需要，您可以通过使用两个 dicts 来解决这个问题（一个按列、行顺序，另一个按行、列顺序）。然后，更新工作量增加了一倍，这对于大多数图块都是静态的游戏来说可能无关紧要，但无论从哪个方向访问都非常容易。

如果您只需要存储数字并且大多数单元格将为 0，请查看 scipy 的稀疏矩阵类。

于 2011-03-11T20:19:43.877 回答
0

使用多维列表——通常实现为嵌套对象。您可以通过一些算术轻松地处理负索引。它可能使用比字典更多的内存，因为必须在每个可能的插槽中放置一些东西None（通常用于空插槽），但访问将通过简单的索引查找而不是像字典那样的散列来完成。

于 2011-03-11T20:16:22.603 回答