Почему numpy намного медленнее, чем Matlab на примере с цифрами?

Я сравниваю производительность numpy vs matlab, в нескольких случаях я заметил, что numpy значительно медленнее (индексирование, простые операции над массивами, такие как абсолютное значение, умножение, сумма и т.д.). Давайте рассмотрим следующий пример, который как-то поражает, включая функцию оцифровать (которую я планирую использовать для синхронизации временных меток):

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 с помощью С++, я внедрил свою собственную версию оцифровки (используя библиотеки 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 секунды

Есть немного мошенничества, так как моя версия оцифровки предполагает, что входные данные являются монотонными, это может объяснить, почему это даже быстрее, чем 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 не эквивалентна для numpy.histogram, если кто-то (как и я в этом случае) не заботится о гистограмме. Мне нужен второй вывод hisc, который представляет собой отображение из входных значений в индекс предоставленных входных бинов. Такой вывод обеспечивается с помощью функции numpy оцифровки и поиска. Как говорится в одном из ответов, поиск сортируется намного быстрее, чем оцифровка. Однако поиск в сортировке по-прежнему медленнее, чем 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 секунды

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

  • В чем смысл numpy.digitize, если есть эквивалентная функция numpy.searchsorted, которая 280 раз быстрее?

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

Ответы

Ответ 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 на самом деле медленнее, чем ваш С++-код, потому что Matlab также предполагает, что ящики монотонно неубедительны.

Ответ 2

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

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

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

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

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

Ответ 3

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

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

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

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

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

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

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

Ответ 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.