除此之外,我需要插入和搜索具有log(N)复杂度。我想使用常规的NumPy数组作为存储来创建自己的红黑树结构,但我相当确信还有更简单的方法来解决这个问题。
编程语言是Python 2.7.12。
除此之外,我需要插入和搜索具有log(N)复杂度。我想使用常规的NumPy数组作为存储来创建自己的红黑树结构,但我相当确信还有更简单的方法来解决这个问题。
编程语言是Python 2.7.12。
字典最基本的形式是一种叫做 HashMap
的数据结构。实现一个哈希表需要将键值转换为可以快速查找的值。一个病态的例子是使用 int
作为键:键为 1
的值将会存储在 array[1]
中,键为 2
的值将会存储在 array[2]
中,哈希函数只是恒等函数。你可以很容易地使用 numpy 数组实现它。
如果你想使用其他类型,就需要编写一个好的哈希函数来将这些键转换为数组中的唯一索引。例如,如果你知道你有一个 (int, int)
元组,并且第一个值永远不会超过 100,那么你可以使用公式 100*key[1] + key[0]
来生成哈希值。
哈希函数的实现是成功或失败的关键。
你有一个(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
。但我不认为它们能帮助解决大型内存问题。