将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数组转换为a而set不是a list？需要更长的时间？我的意思是基本上都有复杂性O(n)？

Answer 1

TL; DR:该set()函数使用Pythons迭代协议创建一个集合.但是在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实例中.

有了这些信息,我可以解释为什么迭代arraya比使用迭代的迭代慢得多list:

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

另一方面,当你想要一个元素时array,需要在返回之前为所有簿记内容创建一个新的Python"框".迭代数组时,需要为数组中的每个元素创建一个Python框:

创建这些框很慢,迭代NumPy数组的主要原因要比迭代存储值及其框的 Python集合(lists/tuples/sets/dictionaries)慢得多:

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列表每个值需要在"巨蟒盒子",所以没有太多的工作,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)

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

你在评论中提到了关于numba的评论,是的,numba确实可以加快这个速度.Numba支持类型集(仅限数字类型),但这并不意味着它总是更快.

我不确定numba(重新)是如何实现set的,但因为它们是键入的,所以它们也可能避免使用"Python框"并将值直接存储在set:

集合比lists 更复杂,因为它涉及hashes和空槽(Python对集合使用开放寻址,所以我也假设numba也是如此).

和NumPy一样,arraynumba set直接保存了这些值.因此,当您将NumPy转换为arraynumba set(或反之亦然)时,根本不需要使用"Python框",因此当您set在numba nopython函数中创建s时,它甚至比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是隐藏).

仅供参考:如果您将lists 传递给Numba nopython函数或从这些函数返回列表,则会发生相同的装箱/拆箱.那么O(1)Python中的一个O(n)操作就是使用Numba 进行操作!这就是为什么将NumPy数组传递给numba nopython函数(也就是说)通常会更好O(1).

我假设如果你从函数中返回这些集合(现在不是真的可能,因为numba当前不支持集合列表)它会更慢(因为它创建了一个numba集,后来将它转换为python集)或者仅稍快一点(如果转换麻木 - > pythonset真的非常快).

我个人只会因为我不需要从函数返回它们并在函数内部对集合执行所有操作而且只有在nopython模式下支持集合上的所有操作时才使用numba for sets .在任何其他情况下,我不会在这里使用numba.

刚一说明:from numpy import *应避免,你隐藏一些蟒蛇的内置功能,当你做到这一点(sum,min,max,...)和它把很多东西到你的全局.更好用import numpy as np.在np.前面的函数调用中,使代码更清晰,并没有太多的类型.