Быстрая сортировка против сортировки выбора (Java против C ++)

Question

Я создал два проекта. Один в C ++ и один в Java. Я сделал временные испытания для QuickSort и SelectionSort для обоих. Как ни странно, я обнаружил очень странное поведение.

Вот результаты для массива размером 10000:

SelectionSort Java: 80 мс

SelectionSort C ++: 2914 мс

QuickSort Java: 1 мс

QuickSort C ++: ~ 45 секунд

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

Итак, мой вопрос: C ++ по-разному обрабатывает QuickSort?

Я пытался сохранить одинаковые функции между языками, и они точно такие же, за исключением использования вектора в C ++ против массива int. Я бы предпочел использовать вектор в любом случае, потому что сам проект, для которого я хочу использовать сортировку в C ++, требует вектор.

Я уверен, что это глупая ошибка или что-то, что я делаю, но, пожалуйста, дайте некоторое представление о том, почему это происходит.

EDIT:

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

Answer 1

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

Просто измените функцию на void, удалите возврат конца и посмотрите, как она себя ведет.

РЕДАКТИРОВАТЬ: Если выбольше используется в Java, где почти все - ссылки на сборщик мусора, обратите внимание, что в C ++ возврат по значению (как у возвращаемого типа) обычно делает копию того, что возвращается.И как @Johannes Schaub - litb указывает, что компилятор даже не может оптимизировать возврат, потому что он не возвращает автоматическую (локальную) переменную.

EDIT2: Если вы не делаете это как упражнениеоднако вы должны использовать либо std::sort, либо std::stable_sort (последний, если вы знаете, что ваши данные уже будут почти отсортированы, или вам нужно сохранить порядок дубликатов).Например std::sort(A.begin(), A.end());

Answer 2

Вы возвращаете полный вектор при каждом рекурсивном вызове. Это занимает много времени (99,99% времени, затрачиваемого на копирование).

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

EDIT:

По-видимому, std::sort не обязательно будет быстрой сортировкой, но гарантированно будет O (n * log (n)). Источник

Answer 3

Есть еще одна проблема с вашим C ++ кодом, на которую, похоже, еще никто не указал.Если мы избавимся от временного кода, это станет довольно очевидным:

quicksort(A,0,length - 1);

SelectionSort(A,length);

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

Answer 4

Ваш код на C ++ не работает.Во-первых, стандарт уже обеспечивает быструю сортировку - std::sort.Во-вторых, вы выбрали std::vector - для массива статического размера?В-третьих, ftime, а остальные не действительные таймеры профилирования.В-третьих, вы продолжаете возвращать значения из quicksort, даже если функция берет ссылку - если вы неправильно установили флаги оптимизации, это может снизить производительность.

Answer 5

Скорее всего, проблема связана с вашей реализацией быстрой сортировки. Если вы включите заголовок и используете std::sort - что не является быстрой сортировкой, а является интросортировкой, вариант, который предназначен для улучшения производительности в худшем случае, результаты будут совсем другими:

$ ./CompareSorts 
Quick Sort Took: 1
Selection Sort Took: 101

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

$ ./CompareSorts 
Quick Sort Took: 41
Selection Sort Took: 95

Аппаратное обеспечение - Core2-Duo 2 ГГц, и я скомпилировал с g++ -O3 -o CompareSorts CompareSorts.cpp (обратите внимание, что -O3 важен: он говорит gcc оптимизировать столько, сколько может).

Answer 6

Марк Б в этот раз ударил по гвоздю. Я повторил тест с обновленным кодом на моей установке с результатами

Java QS: 7 мс

Java SS: 111мс

против

C ++ QS: 1 мс

C ++ SS: 72 мс

Answer 7

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

Не забудьте скомпилировать версию C ++ с оптимизацией (-O3).

Answer 8

Я согласен с Марком Б

Вы также должны убедиться: - запускать каждый тест самостоятельно - запустить каждый тест несколько раз, чтобы получить среднее значение - использовать одни и те же данные для всех тестов