1

__hash__と__eq__はセットの識別にどのように使用されますか？たとえば、ドミノパズルを解くのに役立つコードは次のとおりです。

class foo(object):
    def __init__(self, one, two):
        self.one = one
        self.two = two
    def __eq__(self,other):
        if (self.one == other.one) and (self.two == other.two): return True
        if (self.two == other.one) and (self.one == other.two): return True
        return False
    def __hash__(self):
        return hash(self.one + self.two)

s = set()

for i in range(7):
    for j in range(7):
        s.add(foo(i,j))
len(s) // returns 28 Why?

__eq __（）のみを使用する場合、len（s）は49になります。オブジェクト（たとえば、1-2と2-1）は同じではないが、同じドミノを表すことを理解しているので、問題ありません。そこでハッシュ関数を追加しました。
今では私が望むように動作しますが、1つのことを理解していませんでした。1-3と2-2のハッシュは同じである必要があるため、同じオブジェクトのようにカウントされ、セットに追加されるべきではありません。しかし、彼らはそうします！私は立ち往生しています。

4

5 に答える 5

4

dict / setの目的での同等性は、で定義されている同等性に依存し__eq__ます。ただし、equalと比較するオブジェクトは同じハッシュ値を持つ必要があるため、が必要__hash__です。同様の議論については、この質問を参照してください。

ハッシュ自体は、2つのオブジェクトが辞書で同じものとしてカウントされるかどうかを決定しません。ハッシュは、一方向にしか機能しない「ショートカット」のようなものです。2つのオブジェクトのハッシュが異なる場合、それらは完全に等しくありません。しかし、それらが同じハッシュを持っている場合でも、それらは等しくない可能性があります。

あなたの例では、さまざまなことを定義__hash__し__eq__て実行します。ハッシュはドミノの数字の合計にのみ依存しますが、同等性は両方の個々の数字に（順番に）依存します。等しいドミノが等しいハッシュを持っているのは依然として事実であるため、これは合法です。ただし、上で述べたように、等しい合計のドミノが等しいと見なされるという意味ではありません。一部の等しくないドミノは、依然として等しいハッシュを持ちます。しかし、平等は依然としてによって決定され__eq__、__eq__両方の数値を順番に調べます。したがって、それがそれらが等しいかどうかを決定するものです。

__hash__あなたの場合に行うべき適切なことは、両方を定義し、順序__eq__対に依存することであるように思われます---つまり、最初に2つの数値の大きい方を比較し、次に小さい方を比較します。これは、2-1と1-2が同じであると見なされることを意味します。

于 2013-01-16T06:35:29.337 に答える
2

ハッシュは、Pythonがオブジェクトを配置するのに役立つヒントにすぎません。セット内のオブジェクトfooを検索する場合でも、セット内の各オブジェクトをと同じハッシュでチェックする必要がありますfoo。

それはアルファベットのすべての文字のための本棚を持っているようなものです。コレクションに新しい本を追加したい場合は、そのコピーをまだ持っていない場合に限ります。あなたは最初に適切な手紙のために棚に行きます。しかし、それからあなたはそれが同じであるかどうか見るために、棚の上の各本を見て、それをあなたの手にあるものと比較しなければなりません。すでに棚に何かがあるからといって、新しい本を捨てることはありません。

他の値を使用して「重複」を除外する場合は、ドミノの合計値を最初に表示したドミノにマップするdictを使用します。組み込みのPythonの動作を、まったく異なるものを意味するように破壊しないでください。（あなたが発見したように、とにかく、この場合は機能しません。）

于 2013-01-16T06:34:36.853 に答える
1

ハッシュ関数の要件はx == y、2つの値の場合、hash(x) == hash(y)。逆は真である必要はありません。

文字列のハッシュを検討することで、これが当てはまる理由を簡単に理解できます。それhash(str)が32ビットの数値を返し、4文字より長い文字列をハッシュしているとしましょう（つまり、32ビットより多く含まれています）。可能なハッシュ値よりも多くの可能な文字列があるため、等しくない文字列の中には同じハッシュを共有する必要があるものがあります（これは鳩の巣原理の適用です）。

Pythonセットはハッシュテーブルとして実装されます。オブジェクトがセットのメンバーであるかどうかを確認するとき、オブジェクトはそのハッシュ関数を呼び出し、その結果を使用してバケットを選択し、次に等式演算子を使用して、バケット内のアイテムのいずれかに一致するかどうかを確認します。

あなたの実装では、2-2と1-3のドミノはハッシュバケットに入れられますが、それらは等しく比較されません。したがって、両方をセットに追加できます。

于 2013-01-16T08:00:34.783 に答える
0

これについてはPythonデータモデルのドキュメントで読むことができますが、簡単な答えは、ハッシュ関数を次のように書き直すことができるということです。

def __hash__(self):
    return hash(tuple(sorted((self.one, self.two))))
于 2013-01-16T06:34:07.990 に答える
0

イーブイの答えの音は好きですが、実装を想像するのは困難でした。これが、イーブイから提供された回答の私の解釈、説明、および実装です。

  • 2つのドミノ値の合計を辞書のキーとして使用します。
  • いずれかのドミノ値をディクショナリ値として格納します。

たとえば、ドミノ「12」の場合、合計は3であるため、辞書キーは3になります。次に、いずれかの値（1または2）を選択して、その位置に格納できます（最初の値1を選択します）。 ）。

domino_pairs = {}
pair = '12'
pair_key = sum(map(int, pair))
domino_pairs[pair_key] = int(pair[0]) # Store the first pair's first value.
print domino_pairs

出力：

{3: '1'}

ドミノペアから1つの値のみを格納していますが、他の値は辞書のキーと値から簡単に計算できます。

pair = '12'
pair_key = sum(map(int, pair))
domino_pairs[pair_key] = int(pair[0]) # Store the first pair's first value.
# Retrieve pair from dictionary.
print pair_key - domino_pairs[pair_key] # 3-1 = 2

出力：

2

ただし、2つの異なるペアの合計が同じである可能性があるため、1つのキーに対して複数の値を格納する必要があります。したがって、単一のキー（つまり、2つのペアの合計）に対する値のリストを格納します。これを関数に入れる：

def add_pair(dct, pair):
  pair_key = sum(map(int, pair))
  if pair_key not in dct:
    dct[pair_key] = []
  dct[pair_key].append(int(pair[0]))

domino_pairs = {}
add_pair(domino_pairs, '22')
add_pair(domino_pairs, '04')
print domino_pairs

出力：

{4: [2, 0]}

意味あり。両方のペアの合計は4になりますが、各ペアの最初の値は異なるため、両方を格納します。これまでの実装では、重複が許可されます。

domino_pairs = {}
add_pair(domino_pairs, '40')
add_pair(domino_pairs, '04')
print domino_pairs

出力

   {4: [4, 0]}

'40'と'04'はDominoで同じであるため、両方を保存する必要はありません。重複をチェックする方法が必要です。これを行うために、新しい関数を定義しますhas_pair：

 def has_pair(dct, pair):
  pair_key = sum(map(int, pair))
  if pair_key not in dct:
    return False
  return (int(pair[0]) in dct[pair_key] or 
    int(pair[1]) in dct[pair_key])

通常どおり、合計（辞書キー）を取得します。辞書にない場合、ペアは存在できません。ディクショナリにある場合は、ペアのいずれかの値がディクショナリ「バケット」に存在するかどうかを確認する必要があります。このチェックをに挿入してadd_pair、重複するドミノペアを追加しないようにします。

def add_pair(dct, pair):
  pair_key = sum(map(int, pair))
  if has_pair(dct, pair):
    return
  if pair_key not in dct:
    dct[pair_key] = []
  dct[pair_key].append(int(pair[0]))

重複するドミノペアの追加が正しく機能するようになりました。

domino_pairs = {}
add_pair(domino_pairs, '40')
add_pair(domino_pairs, '04')
print domino_pairs

出力：

{4: [4]}

最後に、print関数は、ドミノペアの合計と、同じペアからの1つの値のみを格納することと、ペア自体を格納することとがどのように同じかを示します。

def print_pairs(dct):
  for total in dct:
    for a in dct[total]:
      a = int(a)
      b = int(total) - int(a)
      print '(%d, %d)'%(a,b)

テスト：

domino_pairs = {}
add_pair(domino_pairs, '40')
add_pair(domino_pairs, '04')
add_pair(domino_pairs, '23')
add_pair(domino_pairs, '50')
print_pairs(domino_pairs)

出力：

(4, 0)
(2, 3)
(5, 0)
于 2016-03-12T14:00:35.267 に答える