109

Pythondictは非常に便利なデータ構造です。

d = {'a': 1, 'b': 2}

d['a'] # get 1

値でインデックスを付けたい場合もあります。

d[1] # get 'a'

このデータ構造を実装する最も効率的な方法はどれですか? それを行う公式の推奨方法はありますか？

4

8 に答える 8

81

これは、 Python 辞書の値からキーを検索dictすることに触発され、次の 2) と 3) を許可するように変更された双方向のクラスです。

ご了承ください ：

    1. 標準辞書が変更されると、逆ディレクトリが自動更新されます。 bd.inversebd
    1. 逆ディレクトリ bd.inverse[value]は、常にそのようなリストです。keybd[key] == value
    1. https://pypi.python.org/pypi/bidictbidictのモジュールとは異なり、ここでは同じ値を持つ 2 つのキーを使用できます。これは非常に重要です。

コード：

class bidict(dict):
    def __init__(self, *args, **kwargs):
        super(bidict, self).__init__(*args, **kwargs)
        self.inverse = {}
        for key, value in self.items():
            self.inverse.setdefault(value,[]).append(key) 

    def __setitem__(self, key, value):
        if key in self:
            self.inverse[self[key]].remove(key) 
        super(bidict, self).__setitem__(key, value)
        self.inverse.setdefault(value,[]).append(key)        

    def __delitem__(self, key):
        self.inverse.setdefault(self[key],[]).remove(key)
        if self[key] in self.inverse and not self.inverse[self[key]]: 
            del self.inverse[self[key]]
        super(bidict, self).__delitem__(key)

使用例:

bd = bidict({'a': 1, 'b': 2})  
print(bd)                     # {'a': 1, 'b': 2}                 
print(bd.inverse)             # {1: ['a'], 2: ['b']}
bd['c'] = 1                   # Now two keys have the same value (= 1)
print(bd)                     # {'a': 1, 'c': 1, 'b': 2}
print(bd.inverse)             # {1: ['a', 'c'], 2: ['b']}
del bd['c']
print(bd)                     # {'a': 1, 'b': 2}
print(bd.inverse)             # {1: ['a'], 2: ['b']}
del bd['a']
print(bd)                     # {'b': 2}
print(bd.inverse)             # {2: ['b']}
bd['b'] = 3
print(bd)                     # {'b': 3}
print(bd.inverse)             # {2: [], 3: ['b']}
于 2014-02-19T22:34:23.233 に答える
46

キーと値のペアを逆の順序で追加することにより、同じ辞書自体を使用できます。

d={'a':1,'b':2}
revd=dict([reversed(i) for i in d.items()])
d.update(revd)
于 2010-07-23T13:59:45.623 に答える
39

貧乏人の双方向ハッシュ テーブルは、たった 2 つの辞書を使用することになります (これらはすでに高度に調整されたデータ構造です)。

インデックスにはBidictパッケージもあります。

Bidict のソースは github にあります。

于 2010-07-23T13:41:45.057 に答える
7

以下のコード スニペットは、可逆 (全単射) マップを実装します。

class BijectionError(Exception):
    """Must set a unique value in a BijectiveMap."""

    def __init__(self, value):
        self.value = value
        msg = 'The value "{}" is already in the mapping.'
        super().__init__(msg.format(value))


class BijectiveMap(dict):
    """Invertible map."""

    def __init__(self, inverse=None):
        if inverse is None:
            inverse = self.__class__(inverse=self)
        self.inverse = inverse

    def __setitem__(self, key, value):
        if value in self.inverse:
            raise BijectionError(value)

        self.inverse._set_item(value, key)
        self._set_item(key, value)

    def __delitem__(self, key):
        self.inverse._del_item(self[key])
        self._del_item(key)

    def _del_item(self, key):
        super().__delitem__(key)

    def _set_item(self, key, value):
        super().__setitem__(key, value)

この実装の利点は、 a のinverse属性BijectiveMapが再び a になることBijectiveMapです。したがって、次のようなことができます。

>>> foo = BijectiveMap()
>>> foo['steve'] = 42
>>> foo.inverse
{42: 'steve'}
>>> foo.inverse.inverse
{'steve': 42}
>>> foo.inverse.inverse is foo
True
于 2015-12-25T05:12:17.380 に答える
1

このようなもの、多分：

import itertools

class BidirDict(dict):
    def __init__(self, iterable=(), **kwargs):
        self.update(iterable, **kwargs)
    def update(self, iterable=(), **kwargs):
        if hasattr(iterable, 'iteritems'):
            iterable = iterable.iteritems()
        for (key, value) in itertools.chain(iterable, kwargs.iteritems()):
            self[key] = value
    def __setitem__(self, key, value):
        if key in self:
            del self[key]
        if value in self:
            del self[value]
        dict.__setitem__(self, key, value)
        dict.__setitem__(self, value, key)
    def __delitem__(self, key):
        value = self[key]
        dict.__delitem__(self, key)
        dict.__delitem__(self, value)
    def __repr__(self):
        return '%s(%s)' % (type(self).__name__, dict.__repr__(self))

複数のキーが指定された値を持つ場合にどうするかを決定する必要があります。特定のペアの双方向性は、後で挿入したペアによって簡単に破壊される可能性があります。可能な選択肢を1つ実装しました。

例 ：

bd = BidirDict({'a': 'myvalue1', 'b': 'myvalue2', 'c': 'myvalue2'})
print bd['myvalue1']   # a
print bd['myvalue2']   # b
于 2010-07-23T13:58:42.987 に答える
0

まず、キーと値のマッピングが 1 対 1 であることを確認する必要があります。そうしないと、双方向のマップを作成できません。

次に、データセットの大きさは? データが少ない場合は、2 つの別々のマップを使用し、更新時に両方を更新します。または、更新/削除が組み込まれた 2 つの dict の単なるラッパーであるBidictのような既存のソリューションを使用することをお勧めします。

しかし、データセットが大きく、2 つの辞書を維持することが望ましくない場合:

  • キーと値の両方が数値の場合は、補間を使用してマッピングを近似する可能性を検討してください。キーと値のペアの大部分がマッピング関数 (およびその
    逆関数) でカバーできる場合は、外れ値をマップに記録するだけで済みます。

  • ほとんどのアクセスが一方向 (キー -> 値) である場合は、時間と
    スペースを交換するために逆マップを段階的に構築してもまったく問題ありません。

コード：

d = {1: "one", 2: "two" }
reverse = {}

def get_key_by_value(v):
    if v not in reverse:
        for _k, _v in d.items():
           if _v == v:
               reverse[_v] = _k
               break
    return reverse[v]
于 2015-12-25T07:42:10.813 に答える