9

我遇到的实际问题是我想(float, str)在 RAM 中存储一个长排序的元组列表。一个普通的列表不适合我的 4Gb RAM，所以我想我可以使用两个numpy.ndarrays.

数据源是 2 元组的可迭代对象。numpy有一个fromiter功能，但我该如何使用它？迭代中的项目数是未知的。由于内存限制，我不能先将它消耗到列表中。我想过itertools.tee，但是这里似乎增加了很多内存开销。

我想我可以做的是分块使用迭代器并将它们添加到数组中。那么我的问题是，如何有效地做到这一点？我是否应该制作 2 个二维数组并向它们添加行？（然后我需要将它们转换为一维）。

或者也许有更好的方法？我真正需要的只是在对数时间内通过相应数字的值搜索字符串数组（这就是我想按浮点值排序的原因）并使其尽可能紧凑。

PS iterable 没有排序。

4

2 回答 2

8

也许使用以下方法构建一个单一的结构化数组np.fromiter：

import numpy as np


def gendata():
    # You, of course, have a different gendata...
    for i in xrange(N):
        yield (np.random.random(), str(i))

N = 100

arr = np.fromiter(gendata(), dtype='<f8,|S20')

按第一列排序，将第二列用于决胜局将花费 O(N log N) 时间：

arr.sort(order=['f0','f1'])

通过第一列中的值查找行可以searchsorted在 O(log N) 时间内完成：

# Some pseudo-random value in arr['f0']
val = arr['f0'][10]
print(arr[10])
# (0.049875262239617246, '46')

idx = arr['f0'].searchsorted(val)
print(arr[idx])
# (0.049875262239617246, '46')

您在评论中提出了许多重要问题；让我尝试在这里回答他们：

  • numpybook 中解释了基本的dtype。可能有一个或两个额外的 dtypes（就像float16那本书写完之后添加的一样，但是基础知识都在那里解释了。）

    在线文档中可能会进行更深入的讨论。这是对您在此处提到的示例的一个很好的补充。

  • Dtypes 可用于定义具有列名或默认列名的结构化数组。'f0','f1'等是默认列名。由于我在'<f8,|S20'未能提供列名时定义了 dtype，因此 NumPy 将第一列命名为 ，第二列命名'f0'为 'f1'。如果我们使用

    dtype='[('fval','<f8'), ('text','|S20')]

    那么结构化数组arr将具有列名'fval'和 'text'.

  • 不幸的是，dtype 必须在np.fromiter调用时固定。您可以想象gendata一次迭代以发现字符串的最大长度，构建您的 dtype，然后调用 np.fromiter（并再次迭代gendata），但这相当繁琐。如果您事先知道字符串的最大大小当然更好。（|S20将字符串字段定义为具有 20 个字节的固定长度。）
  • NumPy 数组将预定义大小的数据放置在固定大小的数组中。将数组（甚至是多维数组）视为一维内存的连续块。（这是一种过度简化——存在不连续的数组——但将有助于您对以下内容的想象。）NumPy 通过利用固定大小（由 设置dtype）来快速计算访问所需的偏移量来获得其大部分速度数组中的元素。如果字符串的大小可变，那么 NumPy 就很难找到正确的偏移量。硬，我的意思是 NumPy 需要一个索引或以某种方式重新设计。NumPy 根本不是以这种方式构建的。
  • NumPy 确实有一个objectdtype，它允许您将 4 字节指针放置到您想要的任何 Python 对象。这样，您就可以拥有带有任意 Python 数据的 NumPy 数组。不幸的是，该np.fromiter 函数不允许您创建 dtype 数组object。我不知道为什么会有这个限制......
  • 请注意，指定np.fromiter时具有更好的性能count。通过知道count（行数）和 dtype（以及每行的大小）NumPy 可以为结果数组预先分配足够的内存。如果不指定count，那么 NumPy 会猜测数组的初始大小，如果太小，它会尝试调整数组的大小。如果可以扩展原始内存块，那么您很幸运。但是如果 NumPy 必须分配一个全新的内存块，那么所有旧数据都必须复制到新位置，这将显着降低性能。
于 2013-02-25T21:28:58.887 回答
1

这是一种从-tuplesN生成器中构建单独数组的方法：N

import numpy as np
import itertools as IT


def gendata():
    # You, of course, have a different gendata...
    N = 100
    for i in xrange(N):
        yield (np.random.random(), str(i))


def fromiter(iterable, dtype, chunksize=7):
    chunk = np.fromiter(IT.islice(iterable, chunksize), dtype=dtype)
    result = [chunk[name].copy() for name in chunk.dtype.names]
    size = len(chunk)
    while True:
        chunk = np.fromiter(IT.islice(iterable, chunksize), dtype=dtype)
        N = len(chunk)
        if N == 0:
            break
        newsize = size + N
        for arr, name in zip(result, chunk.dtype.names):
            col = chunk[name]
            arr.resize(newsize, refcheck=0)
            arr[size:] = col
        size = newsize
    return result

x, y = fromiter(gendata(), '<f8,|S20')

order = np.argsort(x)
x = x[order]
y = y[order]

# Some pseudo-random value in x
N = 10
val = x[N]
print(x[N], y[N])
# (0.049875262239617246, '46')

idx = x.searchsorted(val)
print(x[idx], y[idx])
# (0.049875262239617246, '46')

上面的fromiter函数以块（大小chunksize）读取迭代。它根据需要调用 NumPy 数组方法resize来扩展结果数组。

我使用了一个小的默认值chunksize，因为我是在小数据上测试这段代码。当然，您会想要更改默认块大小或传递chunksize具有更大值的参数。

于 2013-02-28T14:22:59.463 回答