Реализация алгоритма для улучшения

Question

Я считаю, что у нас есть реализации алгоритмов (например, реализация конкретного алгоритма сортировки на языке С ++), которые могут быть не такими эффективными, как могли бы.

Я хотел бы написать исследовательскую работу, обсуждающую, как можно улучшить такую ​​реализацию. Это может быть на любом языке программирования, однако C, C ++, Python, Java или любой непатентованный язык будут идеальными.

Вам известно о какой-либо реализации алгоритма, которая, по вашему мнению, может быть улучшена?

Answer 1

По моему опыту:

• Распараллеливание :
  • Visual C ++ - OpenMP
  • Панель инструментов параллельных вычислений MATLAB , например parfor
  • Кластерные вычисления Например. Luster
• Аппаратное обеспечение:
  • Intel Pentium 4 - Оптимизация SSE2

А именно в MATLAB вы можете ускорить процесс, написав функции C / C ++, к которым можно получить доступ через MEX-функции .

Я понимаю, что некоторые из них являются собственностью!

Answer 2

У Джона Бентли (где-то) есть пример того, как алгоритм торгового агента был увеличен в производительности в 50 раз при сохранении той же сигнатуры big-O.

В одной из лекций он сказал об академиках, которые обижаются, в результате чего они, вероятно, не будут возражать, что их зарплата будет улучшена аналогичным фактором!

Я лично оптимизировал некоторые программы с коэффициентом 100, не меняя их big-O.

Вот пример оптимизации с коэффициентом около 40 без изменения big-O.

Вы можете сделать это с любой программой, если это еще не было сделано. Чем оно больше, тем лучше.

Это помогает?

Answer 3

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

Мой совет, изучите эти статьи, прежде чем пытаться придумать что-то новое. Вероятность того, что ваша работа будет либо ошибаться, либо она уже была опубликована. Существует небольшая вероятность того, что ваша работа будет новой.