为什么在数字化示例中，NumPy比Matlab慢得多？

Question

为什么在数字化示例中，NumPy比Matlab慢得多？

15

我正在比较 numpy 和 matlab 的性能，在几种情况下，我观察到numpy明显较慢（索引、数组上的简单操作，如绝对值、乘法、求和等）。让我们看下面这个例子，它有点惊人，涉及到函数digitize（我打算用它来同步时间戳）：

import numpy as np
import time
scale=np.arange(1,1e+6+1)
y=np.arange(1,1e+6+1,10)
t1=time.time()
ind=np.digitize(scale,y)
t2=time.time()
print 'Time passed is %2.2f seconds' %(t2-t1)

结果如下：

经过的时间为55.91秒

现在让我们尝试使用等效函数histc来执行相同的例子Matlab

scale=[1:1e+6];
y=[1:10:1e+6];
tic
[N,bin]=histc(scale,y);
t=toc;
display(['Time passed is ',num2str(t), ' seconds'])

结果是：

经过的时间为0.10237秒

这快了560倍！

因为我正在学习如何用C++扩展Python，所以我使用boost库实现了自己的digitize版本：

import analysis # my C++ module implementing digitize
t1=time.time()
ind2=analysis.digitize(scale,y)
t2=time.time()
print 'Time passed is %2.2f seconds' %(t2-t1)
np.all(ind==ind2) #ok

结果是:

时间过去了0.02秒。我的digitize版本存在一些欺骗性，因为它假定输入都是单调的，这可能解释了为什么它甚至比Matlab更快。然而，对一个大小为1e+6的数组进行排序需要0.16秒（使用numpy.sort），因此我的函数的表现比Matlab函数histc差（约为1.6倍）。

问题是：

1. 为什么numpy.digitize如此缓慢？难道这个函数不应该是用编译和优化代码编写的吗？ 2. 为什么我的digitize版本比numpy.digitize快得多，但仍然比Matlab慢（我非常有信心，我使用的是最快的算法，因为我假设输入已经排序）？

我正在使用Fedora 16，最近安装了ATLAS和LAPACK库（但性能没有改变）。也许我应该重新构建numpy？我不确定我安装的numpy是否使用适当的库以获得最大速度，也许Matlab正在使用更好的库。

更新：

根据迄今为止的答案，我想强调，如果某人（像我一样）不关心直方图，则Matlab函数histc与numpy.histogram不等价。我需要hisc的第二个输出，即将输入值映射到提供的输入bin的索引。numpy函数digitize和searchsorted提供了这样的输出。正如其中一个答案所说，searchsorted比digitize快得多。然而，searchsorted仍然比Matlab慢了一倍。

t1=time.time()
ind3=np.searchsorted(y,scale,"right")
t2=time.time()
print 'Time passed is %2.2f seconds' %(t2-t1)

np.all(ind==ind3) #ok

结果是

经过的时间为0.21秒

现在的问题是:

如果有一个速度快280倍的等效函数numpy.searchsorted，那么为什么还需要numpy.digitize?
为什么Matlab函数histc（也提供numpy.searchsorted的输出）比numpy.searchsorted 快2倍？

- Mannaggia

1

你能否编辑你的问题，包括你的C++版本的digitize？如果没有看到它，很难说为什么你的版本可能与numpy中的版本表现不同... - talonmies

1

我不明白这些函数与ATLAS或者LAPACK有什么关系。这些库在此处并未被使用，因此不会影响结果。 - user492238

4个回答

6

我不能回答为什么numpy.digitize()运行如此缓慢 - 我可以在我的机器上证实你的时间。

numpy.searchsorted()函数基本上和numpy.digitize()做了同样的事情，但更有效率。

ind = np.searchsorted(y, scale, "right")

在我的机器上大约需要0.15秒，并且给出的结果与你的代码完全相同。

请注意，你的Matlab代码与这两个函数有所不同--它等价于numpy.histogram()。

- Sven Marnach

谢谢Sven，np.searchsorted比numpy.digitize做同样的事情要快得多！在我的例子中，我得到了0.21秒。正如我写给@JoshAdel的那样，numpy.histogram()与Matlab中的histc不等价，它可能更类似于hist（除了hist将提供的间隔的中心作为bin而不是边缘）。histc的美妙之处在于它不仅返回直方图（我根本不需要），还返回从输入到边缘的映射（我需要用于同步目的）。仍未解决的问题是为什么searchsorted比matlab慢了一倍（histc的第二个输出）。 - Mannaggia

2

在回答这个问题之前，需要解决几个子问题：

为了获得更可靠的结果，您应该运行多次测试并平均它们的结果。这将消除与算法无关的启动效果。同时，尝试使用更大的数据。
在框架之间使用相同的算法。这已经在其他答案中提到过。
确保算法足够相似。它们如何利用系统资源？如何迭代内存？例如，如果Matlab算法使用repmat而numpy不使用，则比较就不公平。
对应的框架如何并行化？这可能与您的个人机器/处理器配置有关。Matlab确实会并行化一些（但远非全部）内置函数。我不知道numpy / CPython。
使用内存分析工具来查找两个实现在性能方面的行为。

之后（这只是一个猜测），我们可能会发现，numpy通常比Matlab表现更慢。许多SO上的问题得出了相同的结论。一个解释可能是，Matlab更容易优化数组访问，因为它不需要考虑整个通用对象集合（如CPython）。对数学数组的要求比对通用数组的要求低得多。另一方面，numpy确实利用了CPython，它必须为整个Python库服务-不仅仅是numpy。但是，根据这个比较测试（以及许多其他测试），Matlab仍然表现得相当慢...

- user492238

1

我认为您没有在numpy和matlab中比较相同的函数。根据文档，与histc等效的函数应该是np.histogram。我没有matlab进行比较，但在我的计算机上执行以下操作时：

In [7]: import numpy as np

In [8]: scale=np.arange(1,1e+6+1)

In [9]: y=np.arange(1,1e+6+1,10)

In [10]: %timeit np.histogram(scale,y)
10 loops, best of 3: 135 ms per loop

我得到了一个大致相当于histc的数字。

- JoshAdel

谢谢你的回答，但我担心 Matlab 的 histc 函数并不等同于 np.histogram。histc 函数还会返回一个将输入值映射到区间的映射关系（作为第二个输出）。这正是我所需要的，np.digitize 函数提供了这种映射关系。请参考 help(np.digitize)： "返回输入数组中每个值所属的区间的索引。" - Mannaggia

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Justin Peel · Accepted Answer

首先，让我们看一下为什么numpy.digitize很慢。如果发现您的区间是单调的，那么将根据区间是非递减还是非递增之一调用这些函数之一（此代码位于numpy git存储库中的numpy/lib/src/_compiled_base.c）：

static npy_intp
incr_slot_(double x, double *bins, npy_intp lbins)
{
    npy_intp i;

    for ( i = 0; i < lbins; i ++ ) {
        if ( x < bins [i] ) {
            return i;
        }
    }
    return lbins;
}

static npy_intp
decr_slot_(double x, double * bins, npy_intp lbins)
{
    npy_intp i;

    for ( i = lbins - 1; i >= 0; i -- ) {
        if (x < bins [i]) {
            return i + 1;
        }
    }
    return 0;
}

可以看到，它正在执行线性搜索。线性搜索比二分搜索慢得多，这就是为什么它很慢的原因。我将在numpy跟踪器上开启一个工单。

其次，我认为Matlab实际上比你的C++代码还要慢，因为Matlab也假设bin是单调不降的。