4

サイズ効率の良い辞書または連想配列に使用できるアルゴリズムは何ですか? たとえば、このキー/値セットでは、値の重複「Alice」をどのように回避できますか?

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

Dictionary でPython の実装を確認しましたが、実装はサイズではなく速度 (O(1) を維持) に重点を置いているようです。

4

3 に答える 3

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
于 2013-07-09T16:59:51.567 に答える