Как ускорить функцию сортировки в Matlab?

Question

Я использовал встроенную функцию сортировки Matlab:

[temp, Idx] = sort(M,2);

Я хотел бы иметь отсортированный индекс каждой строки M, который представляет собой матрицу размером> 50 тыс.

Я много искал, но ничего не нашел .. Буду очень признателен, если у вас есть какие-либо комментарии!

Answer 1

Чтобы получить представление о том, сколько у вас есть возможностей для улучшения, я бы предложил написать тестовую программу на C и использовать qsort или на C ++, а затем отсортировать пользователя и тщательно рассчитать его на 7000 входах размера 7000 (или любой другой настройке, которая у вас есть)в Matlab).

Я собираюсь дать вам мою оценку: возможно, сортировка Matlab выполняется (по правильно векторизованному коду, как ваш) так же быстро, как C ++, и вы просто видите эффект от запуска алгоритмаэто берет O (n ^ 2 log n).* в маркетинговом материале Matlab сообщается, что его функция сортировки была быстрее, чем qsort C, но принимайте ее с крошкой соли.

Answer 2

Сортировка в основном O (n log n).

Пока у вас достаточно эффективная реализация, вряд ли это сильно изменится.

Тем не менее, как отмечается в комментарии Эндрю Янке, многопоточность может значительно улучшить ситуацию.

Программирование на GPU может стать способом ускорения. Если у вас R2010b или более поздняя версия, вы можете использовать ускоренные версии встроенных функций, таких как sort из Mathworks.

В противном случае напишите mex-оболочку вокруг библиотеки CUDA Thrust , которая включает в себя сортировку.

Answer 3

Лучший способ ускорить этот вид - получить более быстрый компьютер.Это также ускорит все остальное.:)

Дело в том, что вы редко можете ускорить один звонок до чего-то вроде сортировки.MATLAB уже делает это эффективно, используя оптимизированный код для внутреннего использования.(Перечитайте ответ carlosdc.) Иногда вы можете получить поддержку от инструментов, написанных в самой MATLAB.

Итак, что вы можете сделать?Если не покупать этот новый компьютер, вы можете посмотреть на свой общий код.Один единственный вид такого размера никогда не был такой большой проблемой.Но причина делать это снова и снова.Тщательно продумайте код, можете ли вы изменить поток или избежать многократной повторной сортировки.Изменение алгоритма часто является гораздо более значительным источником улучшения, чем крошечный бит, который вы когда-либо получали, даже если бы вы могли улучшить этот вид.

Answer 4

Вы можете написать свою собственную функцию сортировки в C / C ++ как MEX. В документации MATLAB есть примеры для этого.

Существует множество алгоритмов сортировки , которые лучше, чем другие в крайних случаях, например, почти отсортированные данные или стабильность (что не имеет значения в MATLAB, поскольку все его типы являются типами значений).

Ваши данные числовые или строковые? Для строк, вероятно, существуют специальные алгоритмы для сортировки ASCII, иногда естественная сортировка предпочтительнее.