左转循环一个numpy数组的最快方法(如pop,推送队列)

Question

使用numpy数组,我想执行此操作:

• 移动x[1],...,x[n-1]到x[0],...,x[n-2](左移位),
• 在最后一个索引中写一个新值:x[n-1] = newvalue.

对于先进先出队列(仅倒置)pop(),这类似于a push(newvalue).

一个天真的实现是:x[:-1] = x[1:]; x[-1] = newvalue.

使用的另一个实现np.concatenate更慢:np.concatenate((x[1:], np.array(newvalue).reshape(1,)), axis=0).

有最快的方法吗？

Answer 1

我知道我迟到了，这个问题已经得到了满意的回答，但我只是面临着类似的情况，用于记录流数据的缓冲区。

您提到“先进后出”是一个堆栈，但您的示例演示了一个队列，因此我将分享一个不需要复制即可将新项目排队的队列解决方案。（您最终需要使用 numpy.roll 进行一份副本，以将最终数组传递给另一个函数。）

您可以使用带有指针的循环数组来跟踪尾部的位置（您将在队列中添加新项目的位置）。

如果你从这个数组开始：

x[0], x[1], x[2], x[3], x[4], x[5]
                               /\
                              tail

如果您想删除 x[0] 并添加 x[6]，您可以使用最初为数组分配的内存来完成此操作，而无需复制

x[6], x[1], x[2], x[3], x[4], x[5]
 /\
tail

等等...

x[6], x[7], x[2], x[3], x[4], x[5]
       /\
      tail

每次入队时，都会将尾部向右移动一位。您可以使用模数来很好地进行此包装：new_tail = (old_tail + 1) % length。

找到队列的头部总是在尾部之后的一个位置。这可以使用相同的公式找到：head = (tail + 1) % length。

            head
             \/
x[6], x[7], x[2], x[3], x[4], x[5]
       /\
      tail

这是我为此循环缓冲区/数组创建的类的示例：

x[0], x[1], x[2], x[3], x[4], x[5]
                               /\
                              tail

当您必须将大量项目放入队列而不需要传递数组副本时，这比切片快几个数量级。

访问项目和替换项目的时间复杂度为 O(1)。入队和查看都是 O(1)。复制数组需要 O(n) 时间。

基准测试结果：

(thermal_venv) PS X:\win10\repos\thermal> python -m timeit -s "import benchmark_circular_buffer as bcb" "bcb.slice_and_copy()"
10 loops, best of 5: 36.7 msec per loop

(thermal_venv) PS X:\win10\repos\thermal> python -m timeit -s "import benchmark_circular_buffer as bcb" "bcb.circular_buffer()" 
200000 loops, best of 5: 1.04 usec per loop

(thermal_venv) PS X:\win10\repos\thermal> python -m timeit -s "import benchmark_circular_buffer as bcb" "bcb.slice_and_copy_assignemnt()"
2 loops, best of 5: 166 msec per loop

(thermal_venv) PS X:\win10\repos\thermal> python -m timeit -r 5 -n 4 -s "import benchmark_circular_buffer as bcb" "bcb.slice_and_copy_assignemnt()"
4 loops, best of 5: 159 msec per loop

(thermal_venv) PS X:\win10\repos\thermal> python -m timeit -r 5 -n 4 -s "import benchmark_circular_buffer as bcb" "bcb.circular_buffer_assignment()" 
4 loops, best of 5: 511 msec per loop

我的 GitHub 上有一个测试脚本和一个处理 2D 数组的实现

Answer 2

经过一些实验,很明显:

• 复制是必需的,
• 对于nparray(numpy数组)来说,最简单快捷的方法就是切片和复制.

所以解决方案是:x[:-1] = x[1:]; x[-1] = newvalue.

这是一个小基准:

>>> x = np.random.randint(0, 1e6, 10**8); newvalue = -100
>>> %timeit x[:-1] = x[1:]; x[-1] = newvalue
1000 loops, best of 3: 73.6 ms per loop
>>> %timeit np.concatenate((x[1:], np.array(newvalue).reshape(1,)), axis=0) 
1 loop, best of 3: 339 ms per loop

但是,如果您不需要快速访问数组中的所有值,而只需要快速访问第一个或最后一个值,则使用a deque更智能.