时间戳

首页 > 解决方案 > 散列 np.array -> int 的确定性方法

python - 散列 np.array -> int 的确定性方法

问题描述

我正在创建一个将大型 numpy 数组存储在pyarrow.plasma. 我想给每个数组一个唯一的，确定性的 plasma.ObjectID，np.array可悲的是不可散列我目前的（破碎的）方法是：

import numpy as np
from pyarrow import plasma
def int_to_bytes(x: int) -> bytes:
    return x.to_bytes(
        (x.bit_length() + 7) // 8, "big"
    )  # https://stackoverflow.com/questions/21017698/converting-int-to-bytes-in-python-3
def get_object_id(arr):
    arr_id = int(arr.sum() / (arr.shape[0]))
    oid: bytes = int_to_bytes(arr_id).zfill(20)  # fill from left with zeroes, must be of length 20
    return plasma.ObjectID(oid)

但这很容易失败，例如：

arr = np.arange(12)
a1 = arr.reshape(3, 4)
a2 = arr.reshape(3,2,2)
assert get_object_id(a1) != get_object_id(a2), 'Hash collision'
# another good test case
assert get_object_id(np.ones(12)) != get_object_id(np.ones(12).reshape(4,3))
assert get_object_id(np.ones(12)) != get_object_id(np.zeros(12))

它还涉及对数组求和，这对于大型数组可能非常慢。随意假设dtype的arr将是np.uint或np.int。

我知道不可能永远不会发生哈希冲突（我只有 20 个字节的 ID，并且有超过 2^20 个）可能的输入，所以我只是在寻找 a) 计算成本更低 b) 更少的东西在实践中可能会失败

或者，理想情况下，两者都有！

标签： pythonnumpyhashpyarrow

解决方案

hashlib 模块有一些用于从字节字符串计算哈希的例程（通常用于 CRC）。您可以将 ndarray 转换为字节字符串，ndarray.tobytes但是您的示例仍然会失败，因为这些数组具有相同的字节但形状不同。所以你也可以散列形状。

def hasharr(arr):
  hash = hashlib.blake2b(arr.tobytes(), digest_size=20)
  for dim in arr.shape:
    hash.update(dim.to_bytes(4, byteorder='big'))
  return hash.digest()

示例：

>>> hasharr(a1)
b'\x9f\xd7<\x16\xb6u\xfdM\x14\xc2\xe49.\xf0P\xaa[\xe9\x0bZ'
>>> hasharr(a2)
b"Z\x18+'`\x83\xd6\xc8\x04\xd4%\xdc\x16V)\xb3\x97\x95\xf7v"

我不是 blake2b 的专家，所以你必须自己做研究才能弄清楚碰撞的可能性有多大。

我不确定你为什么要标记pyarrow，但如果你想在 pyarrow 数组上做同样的事情而不转换为 numpy，那么你可以得到一个数组的缓冲区arr.buffers()并将这些缓冲区转换为（会有多个，有些可能是None）字节字符串与buf.to_pybytes(). 只需散列所有缓冲区。这里无需担心形状，因为 pyarrow 数组始终是一维的。

推荐阅读