python - 大小高效的字典(关联数组)实现

Question

有哪些算法可用于尺寸高效 A dictionary or associative array ？例如，对于这个键/值集，如何避免值中出现重复的“Alice”？

{
    "Pride and Prejudice": "Alice",
    "The Brothers Karamazov": "Pat",
    "Wuthering Heights": "Alice"
}

我检查了Python's implementation on dictionary ，但似乎实现的重点是速度(保持 O(1))而不是大小。

Answer 1

如 bennofs 所述在评论中，你可以使用 intern()确保相同的字符串只存储一次:

class InternDict(dict):

    def __setitem__(self, key, value):
        if isinstance(value, str):
            super(InternDict, self).__setitem__(key, intern(value))
        else:
            super(InternDict, self).__setitem__(key, value)

这是一个效果示例:

>>> d = {}
>>> d["a"] = "This string is presumably too long to be auto-interned."
>>> d["b"] = "This string is presumably too long to be auto-interned."
>>> d["a"] is d["b"]
False
>>> di = InternDict()
>>> di["a"] = "This string is presumably too long to be auto-interned."
>>> di["b"] = "This string is presumably too long to be auto-interned."
>>> di["a"] is di["b"]
True