[PYTHON] numpy 배열을 위해 해시 할 수있는 가장 효율적인 속성

numpy 배열을 위해 해시 할 수있는 가장 효율적인 속성

나는 캐싱 목적을 위해 dict에 numpy 배열을 저장할 수 있어야한다. 해시 속도가 중요합니다.

배열은 인덱스를 나타내므로 객체의 실제 ID는 중요하지 않지만 값은입니다. 내가 현재의 가치에만 관심이 있기 때문에, 변경 가능성은 관심사가 아니다.

그것을 사전에 저장하려면 해시해야합니까?

내 현재 접근 방식은 테스트에서 md5보다 빠른 str (arr.data)을 사용하는 것이다.

상대적 시간에 대한 아이디어를 얻으려는 답변의 몇 가지 예를 통합했습니다.

In [121]: %timeit hash(str(y))
10000 loops, best of 3: 68.7 us per loop

In [122]: %timeit hash(y.tostring())
1000000 loops, best of 3: 383 ns per loop

In [123]: %timeit hash(str(y.data))
1000000 loops, best of 3: 543 ns per loop

In [124]: %timeit y.flags.writeable = False ; hash(y.data)
1000000 loops, best of 3: 1.15 us per loop

In [125]: %timeit hash((b*y).sum())
100000 loops, best of 3: 8.12 us per loop

이 특별한 사용 사례 (작은 배열의 인덱스)에서는 array.tostring이 최상의 성능을 제공합니다.

읽기 전용 버퍼 해싱은 자체적으로 빠르지 만 쓰기 가능한 플래그를 설정하는 오버 헤드로 인해 실제로 느려집니다.

해결법

1. ==============================

   1.기본 버퍼를 읽기 전용으로 만들면 간단히 해싱 할 수 있습니다.

   기본 버퍼를 읽기 전용으로 만들면 간단히 해싱 할 수 있습니다.

   >>> a = random.randint(10, 100, 100000)
   >>> a.flags.writeable = False
   >>> %timeit hash(a.data)
   100 loops, best of 3: 2.01 ms per loop
   >>> %timeit hash(a.tostring())
   100 loops, best of 3: 2.28 ms per loop
   

   매우 큰 배열의 경우 hash (str (a))는 훨씬 빠르지 만 배열의 작은 부분 만 고려합니다.

   >>> %timeit hash(str(a))
   10000 loops, best of 3: 55.5 us per loop
   >>> str(a)
   '[63 30 33 ..., 96 25 60]'
   

2. ==============================

   2.Python 바인딩을 통해 xxhash를 시도 할 수 있습니다. 대형 배열의 경우 해시 (x.tostring ())보다 훨씬 빠릅니다.

   Python 바인딩을 통해 xxhash를 시도 할 수 있습니다. 대형 배열의 경우 해시 (x.tostring ())보다 훨씬 빠릅니다.

   IPython 세션의 예 :

   >>> import xxhash
   >>> import numpy
   >>> x = numpy.random.rand(1024 * 1024 * 16)
   >>> h = xxhash.xxh64()
   >>> %timeit hash(x.tostring())
   1 loops, best of 3: 208 ms per loop
   >>> %timeit h.update(x); h.intdigest(); h.reset()
   100 loops, best of 3: 10.2 ms per loop
   

   그런데 Stack Overflow에 게시 된 다양한 블로그와 답변에서 sha1 또는 md5를 해시 함수로 사용하는 사람들을 볼 수 있습니다. 성능상의 이유로 이러한 "안전한"해시 함수는 다소 느리기 때문에 일반적으로 허용되지 않습니다. 해시 충돌이 가장 큰 걱정거리 중 하나 인 경우에만 유용합니다.

   그럼에도 불구하고 해시 충돌은 항상 발생합니다. 그리고 데이터 배열 객체에 __hash__을 구현하여 파이썬 사전이나 세트의 키로 사용할 수 있다면 __hash__ 자체의 속도에 집중하고 Python이 해시 충돌을 처리하도록하는 것이 더 좋다 (1).

   [1] 파이썬이 해시 충돌을 관리 할 수 ​​있도록하려면 __eq__도 무시해야 할 수도 있습니다. __eq__가 numpy에 의해 수행 된 boolean의 배열이 아닌 boolean을 반환하기를 원할 것입니다.

3. ==============================

   3.어떤 종류의 데이터가 있습니까?

   어떤 종류의 데이터가 있습니까?

   배열이 인덱스의 순열로만 구성된 경우에는 기본 변환을 사용할 수 있습니다

   (1, 0, 2) -> 1 * 3**0 + 0 * 3**1 + 2 * 3**2 = 10(base3)
   

   를 통해 hash_key로 '10'을 (를) 사용하십시오.

   import numpy as num
   
   base_size = 3
   base = base_size ** num.arange(base_size)
   max_base = (base * num.arange(base_size)).sum()
   
   hashed_array = (base * array).sum()
   

   이제 dict 대신 배열 (shape = (base_size,))을 사용하여 값에 액세스 할 수 있습니다.

4. ==============================

   4.파티에 늦게 왔지만 큰 배열의 경우, 나는 그 샘플을 무작위로 서브 샘플링하여 해시하는 것이 좋다고 생각합니다.

   파티에 늦게 왔지만 큰 배열의 경우, 나는 그 샘플을 무작위로 서브 샘플링하여 해시하는 것이 좋다고 생각합니다.

   def subsample_hash(a):
       rng = np.random.RandomState(89)
       inds = rng.randint(low=0, high=a.size, size=1000)
       b = a.flat[inds]
       b.flags.writeable = False
       return hash(b.data)
   

   후자의 경우에는 중간에 고유 한 데이터가 있지만 가장자리 주변에 0이있는 배열을 혼동 할 수 있기 때문에 해시 (str (a))를 수행하는 것보다 낫다고 생각합니다.

from https://stackoverflow.com/questions/16589791/most-efficient-property-to-hash-for-numpy-array by cc-by-sa and MIT license