时间戳

首页 > 解决方案 > 如何在范围（n）中具有整数键的字典和长度为 n 的列表之间进行选择？

python - 如何在范围（n）中具有整数键的字典和长度为 n 的列表之间进行选择？

问题描述

问题的简短版本：

在比较键是范围（n）中的整数的字典和长度为 n 的列表时，哪些是实现的关键点，可以在其中一个或另一个之间进行选择？诸如“如果你对你的对象做很多这样的事情，那么字典会更好”。

问题的长版本

我不确定我的实施的以下细节是否对这个问题很重要......所以就是这样。为了让我的代码更加 Pythonic，我实现了 UserList 的一个子类，它接受一个整数和一个表示基数 l 中的整数的列表作为索引。

from collections import UserList

class MyList(UserList):
    """
    A list that can be accessed both by a g-tuple of coefficients in range(l)
    or the corresponding integer.
    """
    def __init__(self, data=None, l=2, g=None):
        self.l = l
        if data == None:
            if g == None:
                raise ValueError
            self.data = [0]*(l**g)
        else:
            self.data = data
        
    def __setitem__(self, key, value):
        if isinstance(key, int):
            self.data[key] = value
        else:
            self.data[self.idx(key)] = value

    def __getitem__(self, key):
        if isinstance(key, int):
            return self.data[key]
        return self.data[self.idx(key)]

    def idx(self, key):
        l = self.l
        idx = 0
        for i, value in enumerate(key):
            idx += value*l**i
        return idx

可以这样使用：

L = MyList(l=4, g=2) #creates a list of length 4**2 initialized at zero
L[9] = 'Hello World'
L[9] == L[1,2]

我已经将这个类泛化为也接受l成为一个基元组（让我们称之为泛化类MyListTuple），但代码在 SageMath 中，所以我也不想将它转换为纯 python，但它工作得很好。

它看起来像这样：

L = MyListTuple(l=[2,4], g=2) #creates a list of length 2^2*4^2 initialized at zero
L[0,9] = 'Hello World'
L[0,9] == L[[0,0],[1,2]]

我想改进的下一部分我目前使用一个字典，其中的键是整数元组（所以你可以将它访问d[9,13,0]为如上所述（所以对于 l=4 将是d[[1,2], [1,3], [0,0]]）。

这与我在 中所做的非常相似MyListTuple，但在这种情况下，很多键从未使用过。

所以我的问题是：如何在创建一个相当于 MyListTuple 处理给定键的 UserDict 子类或仅使用 MyListTuple 之间进行选择，即使在大多数情况下大多数条目都不会被使用？或者正如我上面所说的，在使用这种结构时，我应该寻找哪些细节来在两者之间进行选择？（比如“如果你对你的对象做了很多这样的事情，那么字典会更好”）

标签： pythonlistdictionary

解决方案

（只会尝试解决一般的“列表与字典”部分。
对此持保留态度；来自用户，而不是实施者。
这不是一个真正的答案，更多的是一个大评论。）

列表（可能是双向链表）应该
在任何地方提供有效的插入和删除（仅修改指向
下一个/上一个元素的指针，O(1)）。
搜索将是低效的（O(n) - 检查所有项目 -
和缓存未命中* - 参考的错误位置 - ）。
（*vs 连续存储在内存中的项目（例如 numpy.array））。

Dict（某种哈希映射）理论上应该提供
有效的搜索、插入和删除（摊销 O(1)）；
但这可能取决于哈希函数的质量、
桶的大小、使用模式等（我不太了解）。


由于缓存未命中/引用的错误局部性
（跟随指针，而不是按顺序访问内存），按顺序遍历所有项目对两者来说都是低效的。

据我所知：由于缺乏更好的 替代方案（C 数组、C++ std::array/std::vector/ 等），您可以在 Python
中将列表用作可变序列（当您需要
遍历所有项目时） 。
）。 当搜索比插入/删除更重要/经常时，
您将使用 dicts 基于键进行快速查找/搜索。

推荐阅读