Почему numpy намного медленнее, чем matlab на примере оцифровки?

Question

Я сравниваю производительность 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 секунд

Это 560 раз быстрее!

Как яобучаясь расширять Python с помощью C ++, я реализовал свою собственную версию оцифровки (используя для этого расширенные библиотеки):

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 секунды.

Существует немного обмана, так как моя версия оцифровки предполагает, что все входы монотонны, это может объяснить, почему это даже быстрее, чем Matlab.Однако сортировка массива размером 1e + 6 занимает 0,16 секунды (с помощью numpy.sort), поэтому производительность моей функции хуже (примерно в 1,6 раза) по сравнению с функцией Matlab histc .

Итак, вопросы:

• Почему numpy.digitize такой медленный?Разве эта функция не должна быть написана в скомпилированном и оптимизированном коде?
• Почему моя собственная версия оцифровки намного быстрее, чем numpy.digitize, но все же медленнее, чем Matlab (я совершенно уверен, что использую самый быстрый алгоритм из возможных), учитывая, что я предполагаю, что входные данные уже отсортированы)?

Я использую Fedora 16, и я недавно установил библиотеки ATLAS и LAPACK (но производительность изменилась).Должен ли я, возможно, восстановить NumPy?Я не уверен, использует ли моя установка numpy соответствующие библиотеки для достижения максимальной скорости, возможно, Matlab использует лучшие библиотеки.

Обновление

На основании ответов на данный моментЯ хотел бы подчеркнуть, что функция Matlab histc не не эквивалентна to numpy.histogram , если кто-то (как я в этом случае) не заботится огистограмма.Мне нужен второй вывод hisc, который представляет собой отображение входных значений на индекс предоставленных входных лотков.Такой вывод обеспечивается с помощью простых функций digitize и searchsorted .Как говорится в одном из ответов, сортировка поиска намного быстрее, чем оцифровка .Тем не менее, сортировка поиска все еще медленнее, чем 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.digitize , если есть эквивалентная функция numpy.searchsorted что * в 1093 * 280 раз быстрее ?

2. Почему функция Matlab histc (которая также обеспечивает вывод numpy.поиск отсортирован ) в 2 раза быстрее , чем numpy.searchsorted ?

Answer 1

Сначала давайте посмотрим, почему numpy.digitize медленный. Если ваши бины оказываются монотонными, то одна из этих функций вызывается в зависимости от того, являются ли они неубывающими или не увеличивающимися (код для этого можно найти в numpy/lib/src/_compiled_base.c в numpy git repo):

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 также предполагает , что ячейки монотонно не уменьшаются.

Answer 2

Я не могу ответить, почему numpy.digitize() такой медленный - я могу подтвердить ваши настройки на моей машине.

Функция numpy.searchsorted() делает в основном то же самое, что и numpy.digitize(), но эффективно.

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

занимает около 0,15 секунд на моем компьютере и дает точно такой же результат, как и ваш код.

Обратите внимание, что ваш код Matlab делает что-то отличное от обеих этих функций - это эквивалент numpy.histogram().

Answer 3

Прежде чем на вопрос можно получить ответ, необходимо решить несколько подзапросов:

1. Чтобы получить более надежные результаты, необходимо выполнить несколько итераций тестов и усреднить их результаты.Это каким-то образом устранит эффекты запуска, которые не имеют ничего общего с алгоритмом.Кроме того, попробуйте использовать большие данные для той же цели.

2. Используйте одни и те же алгоритмы в рамках.Об этом уже говорилось в других ответах.

3. Убедитесь, что алгоритмы действительно достаточно похожи.Как они используют системные ресурсы?Как перебирать память?Если (только в качестве примера) алгоритм Matlab использует repmat, а numpy - нет, сравнение несправедливо.

4. Как распараллеливается соответствующая структура?Возможно, это связано с вашей индивидуальной конфигурацией машины / процессора.Matlab распараллеливает некоторые (но далеко не все) встроенные функции.Я не знаю о numpy / CPython.

5. Используйте профилировщик памяти, чтобы выяснить, как обе реализации ведут себя с этой точки зрения производительности.

Впоследствии (это только предположение) мы, вероятно, обнаружим, что numpy часто ведет себя медленнее, чем Matlab.Многие вопросы здесь в SO приходят к такому же выводу.Одним из объяснений может быть то, что в Matlab проще оптимизировать доступ к массивам, поскольку ему не нужно учитывать целую коллекцию объектов общего назначения (например, CPython).Требования к математическим массивам намного ниже, чем к общим массивам.Numpy, с другой стороны, использует CPython, который должен обслуживать полную библиотеку Python, а не только Numpy.Однако, согласно этому сравнительному тесту (среди многих других) Matlab все еще довольно медленный ...

Answer 4

Не думаю, что вы сравниваете одни и те же функции в 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.