为什么在数字化示例中 numpy 比 matlab 慢得多？

我正在比较性能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 秒

现在让我们尝试同样的例子Matlab使用等效函数histc

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 秒

That's 快 560 倍！

当我学习用 C++ 扩展 Python 时，我实现了自己的 digitalize 版本（使用 boost 库进行扩展）：

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秒

有一点作弊，因为我的 digitalize 版本假设输入都是单调的，这可能解释了为什么它比 Matlab 更快。然而，对大小为 1e+6 的数组进行排序需要 0.16 秒（使用 numpy.sort），因此导致我的函数的性能下降worse与 Matlab 函数相比（约 1.6 倍）histc.

所以问题是：

• 为什么 numpy.digitize 这么慢？这个函数不应该用编译和优化的代码编写吗？
• 为什么我自己的 digitalize 版本比 numpy.digitize 快得多，但仍然比 Matlab 慢（鉴于我假设输入已经排序，我非常有信心使用最快的算法）？

我使用的是 Fedora 16，最近安装了 ATLAS 和 LAPACK 库（但性能发生了很大的变化）。我应该重建 numpy 吗？我不确定我安装的 numpy 是否使用了适当的库来获得最大速度，也许 Matlab 使用了更好的库。

Update

根据到目前为止的答案，我想强调Matlab函数histc is 不等同 to numpy.直方图如果有人（在这种情况下像我一样）不关心直方图。我需要 hisc 的第二个输出，它是从输入值到提供的输入箱索引的映射。这样的输出由 numpy 函数提供digitize and 搜索排序。正如其中一个答案所说，搜索排序比digitize。然而，搜索排序是仍然比 Matlab 慢 2 倍:

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 秒

所以现在的问题是：

1. 拥有是什么感觉numpy.数字化如果有一个等价的函数numpy.searchsorted这是快 280 倍?

2. 为什么Matlab函数histc（它还提供了输出numpy.searchsorted) 快 2 倍 than numpy.searchsorted?

首先我们来看看为什么numpy.digitize是慢的。如果发现您的 bin 是单调的，则根据 bin 是非递减还是非递增来调用这些函数之一（此代码可在numpy/lib/src/_compiled_base.c在 numpy git 存储库中）：

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;
}

正如你所看到的，它正在进行线性搜索。线性搜索比二分搜索慢得多，所以你可以找到它为什么慢的答案。我会打开a ticket https://github.com/numpy/numpy/issues/2656为此，请在 numpy 跟踪器上进行。

其次，我认为 Matlab 实际上比 C++ 代码慢，因为Matlab还假设 http://www.mathworks.com/help/techdoc/ref/histc.html垃圾箱是单调非递减的。