如何使用NumPy数组实现字典？

Question

我需要把大量的数字-数字对写入NumPy数组中。由于许多这些对的第二个值为0，我想制作类似于字典的东西。问题是我阅读了 NumPy 结构化数组的文档，似乎只有使用字符串作为键的页面上建造的字典才能够使用。

除此之外，我需要插入和搜索具有log(N)复杂度。我想使用常规的NumPy数组作为存储来创建自己的红黑树结构，但我相当确信还有更简单的方法来解决这个问题。

编程语言是Python 2.7.12。

- Ilman

---

为什么你需要特别使用NumPy数组？ - David Z

@David Z 因为我使用的数据量太大，无法存储在 RAM 中。这就是为什么我需要将它提供给另一种数据类型（这个链接），它支持直接写入硬盘数据库。那个东西本质上是一个 NumPy 数组，如果需要的话可以直接写入硬盘... - Ilman

啊，这是有用的信息（也可以包含在问题中）。如果有其他更容易完成此任务的大容量存储库，它还打开了使用不同的选项。 - David Z

@DavidZ 嗯，使用另一个库并不是一个真正的选择，因为我将不得不在新系统上重新做所有的事情，这可能比编写自己的包装器更困难。无论如何，我会把这个留到下周考虑。希望有人有想法... - Ilman

Answer 1

字典最基本的形式是一种叫做 HashMap 的数据结构。实现一个哈希表需要将键值转换为可以快速查找的值。一个病态的例子是使用 int 作为键：键为 1 的值将会存储在 array[1] 中，键为 2 的值将会存储在 array[2] 中，哈希函数只是恒等函数。你可以很容易地使用 numpy 数组实现它。

如果你想使用其他类型，就需要编写一个好的哈希函数来将这些键转换为数组中的唯一索引。例如，如果你知道你有一个 (int, int) 元组，并且第一个值永远不会超过 100，那么你可以使用公式 100*key[1] + key[0] 来生成哈希值。

哈希函数的实现是成功或失败的关键。

- RoadieRich

---

是的，我明白了，我可以轻松地构建我的数组，以便快速找到值的位置，但插入是个问题。如果我想保持数组排序，在插入后，我需要将每个大于插入元素的元素向右移动，从而使插入的复杂度为O(n)。我需要实现O(logN)的复杂度，可以使用红黑树（链接最好不需要自己编写... - Ilman

Answer 2

你有一个(N,2)数组，而且x[:,1]中的许多值都是0。

你所说的插入是什么意思？将一个值添加到数组中使其变为(N+1,2)？还是只是将x[i,:]更改为新的值？

那么搜索呢？numpy数组非常适合查找第i个值x[i,:]，但对于查找与z匹配的值并不是很好。 python numpy filter two dimentional array by condition

scipy.sparse实现了各种形式的稀疏矩阵，如果可能的值少于十分之一，则这些矩阵非常有用。其中一种格式是dok，即键的字典。它实际上是一个dict子类，键是2d索引元组(i,j)。其他格式将它们的值存储为数组，例如行、列和数据。

结构化数组适用于具有适度数量的命名字段的情况，每个字段可以容纳不同类型的数据。但我认为将一个(N,2)数组转换为具有2个字段的(N,)数组并没有什么帮助。

================

根据您的评论，您似乎不熟悉如何存储或访问numpy数组。

一个数组由一个平坦的1d 数据缓冲区（只是一个字节的c数组）和属性，如形状、步幅、项大小和dtype组成。

假设它是np.arange(100)。

In [1324]: np.arange(100).__array_interface__
Out[1324]: 
{'data': (163329128, False),
 'descr': [('', '<i4')],
 'shape': (100,),
 'strides': (4,)
 'typestr': '<i4',
 'version': 3}

所以，如果我要求x [50]，它会计算步幅，即每个元素4个字节，* 50个元素= 200个字节，并在c代码中请求 163329128 + 200 处的4个字节，并将它们作为整数返回（实际上是np.int32类型的对象）。

对于结构化数组，类型描述符和每个元素的字节数将更大，但访问方式相同。 对于2D数组，它将考虑形状和步幅元组以找到适当的索引。

(N,2)整数数组的步幅为(8,4)。 因此，访问x [10,1]元素的偏移量为10 * 8 + 1 * 4 = 84。 而访问x [:,1]则使用i * 8 for i in range ...偏移量。

但在所有情况下，它都依赖于值按矩形可预测的模式排列。 numpy数据结构没有什么特别之处。 它们之所以相对较快，仅因为许多操作都是编译代码编写的。

数组可以进行排序、按值访问和重新排列元素，但这不是它的强项。往往这些操作会生成一个新的数组，其中的值从旧数组中复制到新数组中以某种新的方式。

numpy 有几个内置的数组子类，主要是 np.matrix 和 np.masked_array，但它们并没有扩展访问方法。与常规的 Python 类不同，由于 numpy 有自己的编译代码，因此子类化不像常规的 Python 类那样容易。子类必须具有__new__ 方法而不是常规的__init__ 方法。

有一些 Python 模块维护排序列表，如 bisect 和 heapq。但我不认为它们能帮助解决大型内存问题。

- hpaulj

---

你可以说我想要一个按其第一个元素排序的（N，2）数组，使其具有O(logN)的插入和搜索复杂度。插入是指将新元素添加到数组中，以便它保持其排序状态。搜索是指查找给定其第一个值的元素的索引和因此第二个值。我知道这是可能的，因为这就是红黑树所做的，这也是Python字典的工作原理。我想知道是否有numpy.array的内置子类型具有这些属性，因为它具有索引... - Ilman

根据NumPy结构数组页面的说明（即使用名称而不是索引来指定元素），通过元素完成操作。另外，由于限制只能使用NumPy数组，因此不能使用scipy或其他库... - Ilman

我已经详细阐述了numpy数组的存储和访问方式。 - hpaulj