Как профилировать алгоритмы сортировки?

Question

Я кодировал несколько методов сортировки в C, и я хотел бы найти входной размер, при котором программа является оптимальной (то есть) профилирует каждый алгоритм.Но как мне это сделать?Я знаю время каждого метода, но не знаю, как найти размер, при котором он «оптимален».

Answer 1

Это зависит от некоторых факторов:

• Поведение данных : ваши данные уже частично отсортированы?или это очень случайно?

• Размер данных : для большого ввода (скажем, 1 000 или более) вы можете убедиться, что O (N ^ 2) методы сортировкипроиграет методам O (N * log (N)) ..

• Структура данных данных : это массив или список или?Метод сортировки с непоследовательным доступом к данным будет медленнее для чего-то вроде списка

Таким образом, ответ заключается в том, чтобы эмпирически запустить вашу программу с некоторыми реальными данными, которые вы, вероятно, будете обрабатывать в сочетании с изменением размера ввода.

Когда более медленный метод (например, O (N ^ 2)) побивается более быстрым методом (например, O (N * log (N))), когда размер ввода равен > X, тогда вы можете сказать, что медленнееметод 'эмпирически оптимальный' для входного размера <= X (значение зависит от характеристик входных данных).

Answer 2

Алгоритмы сортировки не имеют единственного числа, при котором они являются оптимальными.

Для чистого времени выполнения почти каждый алгоритм сортировки будет самым быстрым на наборе из 2 чисел, но в большинстве случаев он бесполезен.

Некоторые алгоритмы сортировки могут работать более эффективно на меньших наборах данных, но это не значит, что они «оптимальны» при таком размере.

Некоторые сорта также могут лучше работать с другими характеристиками данных. Существуют сортировки, которые могут быть чрезвычайно эффективными, если данные уже почти отсортированы, но могут быть очень медленными, если это не так. Другие будут работать одинаково на любом наборе заданного размера.

Более полезно взглянуть на Big O сорта (например, O (n ^ 2), O (n log n) и т. Д.) И любые специальные свойства, такие как работа с почти отсортированными данными.

Answer 3

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