3

以下のクラスのオブジェクトを使用して作成されたキーを持つ辞書を考えてみましょう:

class Point( object ):

    def __init__( self, x, y ):
        self.x = x
        self.y = y

    def __eq__( self, other ):
        return self.x == other.x

    def __hash__( self ):
        return self.x.__hash__()

    def __ne__( self, other ):
        return self.x != other.x

>>> a = Point(1,1)
>>> b = Point(0, 2)
>>> dct = {}
>>> dct[a] = 15
>>> dct[b] = 16
>>> dct[a]
15
>>> c = Point(1,None)
>>> dct[c]
15

これは、とが同じハッシュを共有し、等しいcために発生します。指定された戻り値を返すa関数を実装する O(1) 方法はありますか (以下の O(n) 実装とは対照的に?):ca

def getKey( dct, key ):
    for k in dct:
        if k == key:
            return k
    return None
4

4 に答える 4

2

あなたの関数は常にNoneまたはkeyを返すので、私はあなたの主張を理解していません...

複雑さによると、少なくとも O(log(n)) が必要になるとします。たとえば、 dct が私が想定している辞書である場合、次のようになります。

def getKey( dct, key ):
    if dct.has_key(key):
        return key
    return None

その値を返したい場合は、次を使用してください: dct.get(key, None)

于 2012-05-31T22:40:20.730 に答える
1

おそらく、キーと値自体で構成されるタプルまたはリストとして辞書の値を作成できます。あなたの例を使用して：

>>> a = Point(1,1)
>>> b = Point(0, 2)
>>> dct = {}
>>> dct[a] = (15, a)
>>> dct[b] = (16, b)
>>> dct[a] 
(15, <Point object at 0xb769dc2c>)
>>> c = Point(1,None)
>>> dct[c]
(15, <Point object at 0xb769dc2c>)

これで、次のようにa使用できます。c

>>> dct[c][1]
于 2012-05-31T23:06:22.213 に答える
1

これは、c と a が同じハッシュを共有するために発生します。

いいえ; これは、それらがハッシュを共有し、互いに同等であるために発生します。

一般に、等しくないオブジェクトは同じ値にハッシュされる可能性があります。(等しいオブジェクトは同じ値にハッシュする必要があります。)

オブジェクト__eq__が同じ x 座標を持つ場合、オブジェクトは等しいと定義します。これは明らかに間違っています。両方の座標が等しい場合にのみ等しくなります。

しかし、それはあなたが本当にやろうとしていることではないようです。c「given , get 」したい場合a、実際に求めているのは、与えられた点で、同じ x 座標を持つ他のすべての点を見つけることです。

それは簡単です: x 座標値をその座標を持つ点にマッピングする dict を作成します。

于 2012-05-31T23:12:41.513 に答える
0

つまり、オブジェクトのリストとオブジェクト X が与えられた場合、X と同じハッシュ値を持つリスト内の要素を見つけます。

class A(object):
    def __init__(self, x, blah):
        self.x = x
        self.blah = blah
    def __eq__(self, other):
        return self.x == other.x
    def __hash__(self):
        return self.x
    def __repr__(self):
        return '%d-%s' % (self.x, self.blah)


ls = [A(1, 'one'), A(2, 'FOO'), A(3, 'three')]
test = A(2, 'BAR')
print test, '=', (set(ls) - (set(ls) - set([test]))).pop()

set(ls)辞書の例で作業するには、次のように置き換えますviewkeys。

dct = dict(zip(ls, range(100)))
print test, '=', (dct.viewkeys() - (dct.viewkeys() - set([test]))).pop()
于 2012-05-31T23:12:19.903 に答える