numpy配列をハッシュして重複をチェックする方法

Question

この問題を解決するためにチュートリアルなどを少し検索しましたが、何も見つからないようです。

私は、n次元のnumpy配列（いくつかの画像の3D配列形式）の2つのリストを持っており、各リスト内の重複する画像をチェックしたいと考えています。リストaはトレーニングセットであり、リストbは検証セットであると言います。 ネストされたループを使用して、配列の各ペアがnp.array(a[i], b[j])を使用して等しいかどうかをチェックしますが、それは遅いです（各リストには約200,000個の配列があります）。

これを実現するよりエレガントな方法は、各リスト内のそれぞれのnumpy配列をハッシュし、これらのハッシュテーブルを使用して各エントリを比較することだと考えていました。

まず、この解決策は正しいですか。第2に、これを達成するにはどうすればいいですか？
一部のデータの例を以下に示します。

train_dataset[:3] 
array([[[-0.5  , -0.49607843, -0.5  , ..., -0.5  , 
     -0.49215686, -0.5  ], 
     [-0.49607843, -0.47647059, -0.5  , ..., -0.5  , 
     -0.47254902, -0.49607843], 
     [-0.49607843, -0.49607843, -0.5  , ..., -0.5  , 
     -0.49607843, -0.49607843], 
     ..., 
     [-0.49607843, -0.49215686, -0.5  , ..., -0.5  , 
     -0.49215686, -0.49607843], 
     [-0.49607843, -0.47647059, -0.5  , ..., -0.5  , 
     -0.47254902, -0.49607843], 
     [-0.5  , -0.49607843, -0.5  , ..., -0.5  , 
     -0.49607843, -0.5  ]], 

     [[-0.5  , -0.5  , -0.5  , ..., 0.48823529, 
      0.5  , 0.1509804 ], 
     [-0.5  , -0.5  , -0.5  , ..., 0.48431373, 
      0.14705883, -0.32745099], 
     [-0.5  , -0.5  , -0.5  , ..., -0.32745099, 
     -0.5  , -0.49607843], 
     ..., 
     [-0.5  , -0.44901961, 0.1509804 , ..., -0.5  , 
     -0.5  , -0.5  ], 
     [-0.49607843, -0.49607843, -0.49215686, ..., -0.5  , 
     -0.5  , -0.5  ], 
     [-0.5  , -0.49607843, -0.48823529, ..., -0.5  , 
     -0.5  , -0.5  ]], 

     [[-0.5  , -0.5  , -0.5  , ..., -0.5  , 
     -0.5  , -0.5  ], 
     [-0.5  , -0.5  , -0.5  , ..., -0.5  , 
     -0.5  , -0.5  ], 
     [-0.5  , -0.5  , -0.49607843, ..., -0.5  , 
     -0.5  , -0.5  ], 
     ..., 
     [-0.5  , -0.5  , -0.5  , ..., -0.48823529, 
     -0.5  , -0.5  ], 
     [-0.5  , -0.5  , -0.5  , ..., -0.5  , 
     -0.5  , -0.5  ], 
     [-0.5  , -0.5  , -0.5  , ..., -0.5  , 
     -0.5  , -0.5  ]]], dtype=float32) 

私は事前に助けていただきありがとうございます。

Answer 1

numpy_indexedパッケージ：あなたのような何かを行うことができるはず

import numpy_indexed as npi 
duplicate_images = npi.intersection(train_dataset, test_dataset) 

プラス関連機能の多くをどのこの文脈では役に立つかもしれません。

Answer 2

numpyのintersect1d（1次元セット交差）関数を使用して配列間の重複を見つけることができます。

duplicate_images = np.intersect1d(train_dataset, test_dataset) 

私は推測しているtensorflow tutorialsのいずれかから（それぞれ55000と10000の配列）電車やテストセットを使用して、この時限あなたのデータと同様です。 intersect1dを使用すると、私のマシンで完了するのに約2.4秒かかりました（パラメータassume_unique=Trueでわずか1.3秒かかりました）。あなたのようなペアワイズの比較には数分かかりました。

EDIT

この回答（上記）@ mbhall88コメントで指摘したように、この配列ではなく、アレイ自身内の要素を比較し、それぞれの「画像」の配列を比較しません。配列を比較するためにはintersect1dを使用することができますが、先に説明したようにdtypesを使いこなす必要があります。hereしかし、その答えの例は2次元配列を扱い、3次元配列を使って作業しているので、最初に2つの次元を平坦化する必要があります。このため、効率的なワンライナーがあります（私はその作者午前diclaimer）：

def intersect3d(A,B, assume_unique=False): 
    # get the original shape of your arrays 
    a1d, a2d, a3d = A.shape 
    # flatten the 2nd and 3rd dimensions in your arrays 
    A = A.reshape((a1d,a2d*a3d)) 
    B = B.reshape((len(B),a2d*a3d)) 
    # define a structured dtype so you can treat your arrays as single "element" 
    dtype=(', '.join([str(A.dtype)]*ncols)) 
    # find the duplicate elements 
    C = np.intersect1d(A.view(dtype), B.view(dtype), assume_unique=assume_unique) 
    # reshape the result and return 
    return C.view(A.dtype).reshape(-1, ncols).reshape((len(C),a2d,a3d)) 

Answer 3

それは何かを思い付くしそう難しいことではありません。

from collections import defaultdict 
import numpy as np 

def arrayhash(arr): 
    u = arr.view('u' + str(arr.itemsize)) 
    return np.bitwise_xor.reduce(u.ravel()) 

def do_the_thing(a, b, hashfunc=arrayhash): 
    table = defaultdict(list) 
    for i, a_i in enumerate(a): 
     table[hashfunc(a_i)].append(i) 

    indices = [] 
    for j, b_j in enumerate(b): 
     candidates = table[hashfunc(b_j)] 
     for i in candidates: 
      if np.array_equiv(a[i], b_j): 
       indices.append((i,j)) 

    return indices 

しかしノート：​​浮動小数点の等価性のチェック

• は限られているため、精度と丸め誤差、しばしば悪い考えです。有名な例：

  >>> 0.1 + 0.2 == 0.3 
  False 
  

• NaNでの自身に等しい比較しない：上記

  >>> np.nan == np.nan 
  False 
  

• 単純なハッシュ関数は、浮動小数点数のビット表現に関して、これは負の存在下で問題があります-0とシグナリングNaN。

も参照してください。この問題の議論：Good way to hash a float vector?