python - 将 NumPy 数组转换为集合花费的时间太长

Question

我正在尝试执行以下操作

from numpy import *
x = array([[3,2,3],[711,4,104],.........,[4,4,782,7845]])  # large nparray
for item in x:
    set(item)

与以下情况相比需要很长时间:

x = array([[3,2,3],[711,4,104],.........,[4,4,782,7845]])  # large nparray
for item in x:
    item.tolist()

为什么将 NumPy 数组转换为 set 需要更长的时间比到 list ?
我的意思是基本上两者都有复杂性 O(n) ?

Answer 1

TL;DR:set()函数使用 Python 迭代协议(protocol)创建一个集合。但是在 NumPy 数组上迭代(在 Python 级别)太慢以至于使用 tolist()在进行迭代之前将数组转换为 Python 列表会(快得多)。

要理解为什么迭代 NumPy 数组如此缓慢，重要的是要知道 Python 对象、Python 列表和 NumPy 数组是如何存储在内存中的。

Python 对象需要一些簿记属性(如引用计数、指向其类的链接等)以及它所代表的值。例如整数 ten = 10看起来像这样:



蓝色圆圈是您在 Python 解释器中为变量 ten 使用的“名称”。而较低的对象(实例)实际上代表整数(因为簿记属性在这里并不重要，我在图像中忽略了它们)。

一个 Python list只是 Python 对象的集合，例如 mylist = [1, 2, 3]会像这样保存:



这次列表引用了 Python 整数 1 , 2和 3和名称 mylist仅引用 list实例。

但是一个数组 myarray = np.array([1, 2, 3])不将 Python 对象存储为元素:



值 1 , 2和 3直接存储在 NumPy array实例。

有了这些信息，我就可以解释为什么要迭代 array与 list 上的迭代相比要慢得多:

每次访问 list 中的下一个元素时list只返回一个存储的对象。这非常快，因为该元素已经作为 Python 对象存在(它只需要将引用计数加一)。

另一方面，当您想要 array 的元素时在返回之前，它需要为包含所有簿记内容的值创建一个新的 Python“框”。当您遍历数组时，它需要为数组中的每个元素创建一个 Python 框:



创建这些框很慢，主要原因是迭代 NumPy 数组比迭代存储值的 Python 集合(列表/元组/集/字典)慢得多 和他们的盒子 :

import numpy as np
arr = np.arange(100000)
lst = list(range(100000))

def iterateover(obj):
    for item in obj:
        pass

%timeit iterateover(arr)
# 20.2 ms ± 155 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit iterateover(lst)
# 3.96 ms ± 26.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

set “构造函数”只是对对象进行迭代。

我无法明确回答的一件事是为什么 tolist方法要快得多。最后，生成的 Python 列表中的每个值都需要位于“Python 框”中，因此 tolist 没有太多工作要做可以避免。但我确定的一件事是 list(array)比 array.tolist() 慢:

arr = np.arange(100000)

%timeit list(arr)
# 20 ms ± 114 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit arr.tolist()
# 10.3 ms ± 253 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

每一个都有 O(n)运行时复杂性，但常数因素非常不同。

在您的情况下，您确实比较了 set()至 tolist() - 这不是一个特别好的比较。比较 set(arr) 会更有意义至 list(arr)或 set(arr.tolist())至 arr.tolist() :

arr = np.random.randint(0, 1000, (10000, 3))

def tosets(arr):
    for line in arr:
        set(line)

def tolists(arr):
    for line in arr:
        list(line)

def tolists_method(arr):
    for line in arr:
        line.tolist()

def tosets_intermediatelist(arr):
    for line in arr:
        set(line.tolist())

%timeit tosets(arr)
# 72.2 ms ± 2.68 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit tolists(arr)
# 80.5 ms ± 2.18 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit tolists_method(arr)
# 16.3 ms ± 140 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit tosets_intermediatelist(arr)
# 38.5 ms ± 200 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

所以如果你想要 set你最好使用 set(arr.tolist()) .对于更大的数组，使用 np.unique 可能是有意义的。但是因为您的行只包含 3 个可能会变慢的项目(对于数千个元素，它可能会快得多!)。

在您询问 numba 的评论中，是的，numba 确实可以加快速度。 Numba supports typed sets (only numeric types) ，但这并不意味着它总是更快。

我不确定 numba 如何(重新)实现 set s 但因为它们是输入的，所以它们很可能也避免了“Python 框”并将值直接存储在 set 中。 :



集合比 list 更复杂s 因为它们涉及 hash es 和空槽(Python 对集合使用开放寻址，所以我假设 numba 也会)。

像 NumPy array numba set直接保存值。所以当你转换一个 NumPy array到 NumPy set (或反之亦然)它根本不需要使用“Python 盒子”，所以当你创建 set 时s in a numba nopython 功能它甚至会比 set(arr.tolist())快得多手术:

import numba as nb
@nb.njit
def tosets_numba(arr):
    for lineno in range(arr.shape[0]):
        set(arr[lineno])

tosets_numba(arr)  # warmup
%timeit tosets_numba(arr)
# 6.55 ms ± 105 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

这大约比 set(arr.tolist()) 快五倍方法。但重要的是要强调我没有返回 set s 从函数。当您 返回 set从 nopython numba 函数到 Python Numba 创建了一个 python 集合——包括为集合中的所有值“创建盒子”(这是 numba 隐藏的东西)。

仅供引用:如果你通过 list，同样的装箱/拆箱会发生s 到 Numba nopython 函数或从这些函数返回列表。那么什么是 O(1) Python 中的操作是 O(n)与 Numba 一起操作!这就是为什么通常最好将 NumPy 数组传递给 numba nopython 函数(即 O(1))。



我假设如果您 返回这些集合 从函数(现在不太可能，因为 numba 目前不支持集合列表)它会更慢(因为它创建了一个 numba 集 和 后来将它转换为 python 集)或者只是稍微快一点(如果转换 numbaset -> pythonset 真的非常快)。

就我个人而言，仅当我不需要从函数中返回它们并在函数内对集合执行所有操作时，我才会将 numba 用于集合 和 仅当 nopython 模式支持集合上的所有操作时。在任何其他情况下，我都不会在这里使用 numba。

请注意: from numpy import *应该避免，当你这样做时，你隐藏了几个 python 内置函数( sum ， min ， max ，...)，它把很多东西放到你的全局变量中。更好用 import numpy as np . np.在函数调用前面使代码更清晰，不需要输入太多。