优化的Python字典/负索引存储

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

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

我将坐标键存储到游戏中充当拼贴阵列的对象。这些在某些时候会是负面的，所以我不能使用列表或某种稀疏数组（我认为这是术语？）。我可以：加速字典查找，所以这不是问题找到一种能够支持稀疏，负面指数的容器？我会使用一个列表，但随后查询将从O（log n）变为O（n）以找到（x，y）处的区域。（我想我的时间也在这里）。

已邀请:

5 个回复

递劝臼类洪

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

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

然后，如果你想要给定“行”中的所有图块，它只是somedict[0]。您需要一些逻辑来在必要时添加辅助字典等等。提示：在标准dict类型上检查getitem()和setdefault()，或者可能是collections.defaultdict类型。此方法使您可以快速访问给定行中的所有切片。如果您想要给定列中的所有切片，它仍然很慢（尽管至少您不需要查看每个单元格，只需查看每一行）。但是，如果需要，您可以通过使用两个dicts（一个在列中，行顺序，另一个在行，列顺序）来解决这个问题。然后更新成为工作量的两倍，这对于大多数图块是静态的游戏可能无关紧要，但在任一方向上访问都非常容易。如果您只需要存储数字并且大部分单元格都是0，请查看scipy的稀疏矩阵类。

穗揣

Python字典非常快，使用整数元组不会成为问题。然而，您的用例似乎有时您需要进行单坐标检查，并且遍历所有dict当然是慢的。但是，您可以使用三个词典加速数据结构以获得所需的访问权限，而不是进行线性搜索：

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, [])]

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

爆刺疤灯

首先加速字典查找，所以这不是问题字典查找非常快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']

现在只需将它包装在一个类或一个模块中，你就会离开，而且一如既往，如果它没有足够快的轮廓和测试，你会猜测。

末钉蹈泰唬

一种替代方案是简单地改变指数，使其为正。例如。如果您的指数是连续的，就像这样：

...
-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。还有一点需要注意：如果您打算进行查找并且键的数量是恒定的（或者非常缓慢地变化），请坚持使用数组。否则，词典一点也不差。

抹持奠糙驰

使用多维列表 - 通常作为嵌套对象实现。你可以通过一点算术轻松地处理负指数。它可能使用比字典更多的内存，因为必须在每个可能的插槽中放置一些内容（对于空插槽通常为12ѭ），但是访问将通过简单的索引查找而不是像字典一样进行散列。

要回复问题请先登录或注册

优化的Python字典/负索引存储

5 个回复

发起人

indices

问题状态

优化的Python字典/负索引存储

与内容相关的链接

5 个回复

发起人

indices

问题状态