Наиболее эффективное свойство хэш для массива numpy

Мне нужно иметь возможность хранить numpy array в dict для целей кеширования. Скорость хеширования важна.

array обозначает знаки, поэтому, когда фактическая идентичность объекта не имеет значения, значение равно. Mutabliity не вызывает беспокойства, поскольку меня интересует только текущая ценность.

Что мне делать, чтобы сохранить его в dict?

Мой текущий подход заключается в использовании str(arr.data), который быстрее, чем md5 в моем тестировании.

Я привел несколько примеров из ответов, чтобы получить представление об относительных временах:

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

Похоже, что для этого конкретного случая использования (малые массивы указателей) arr.tostring обеспечивает лучшую производительность.

В то время как хеширование только для чтения буфера выполняется само по себе, накладные расходы на установку записываемого флага на самом деле делают его более медленным.

Ответ 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

Вы можете попробовать xxhash через Связывание с Python. Для больших массивов это намного быстрее, чем hash(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__ для объектов массива данных, чтобы их можно было использовать как ключи в словарях или наборах Python, я думаю, что лучше сосредоточиться на скорости самого __hash__ и позволить Python обрабатывать хеш-столкновение [1].

[1] Возможно, вам придется переопределить __eq__, чтобы помочь Python управлять хеш-коллизией. Вы хотели бы, чтобы __eq__ возвращал логическое значение, а не массив логических значений, как это делается с помощью numpy.

Ответ 3

Какие у вас данные?

размер массива
У вас есть индекс несколько раз в массиве

Если ваш массив состоит только из перестановки индексов, вы можете использовать базовое преобразование

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

и используйте '10' как hash_key через

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()

Теперь вы можете использовать массив (shape = (base_size,)) вместо dict для доступа к значениям.

Ответ 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)

Я думаю, что это лучше, чем делать hash(str(a)), потому что последний может путать массивы с уникальными данными в середине, но нулями по краям.