Сортировка… хэш-таблицей (ещё подсчётом-деревом и HashMap'ом)

[hdfan2]

Построить DOM, вырастить чёрно-красное дерево и посадить зрение.

[imanushin]

Опубликуйте, пожалуйста, код на github (если там нет комерческой тайны).

И вопрос: а как вы замеряли производительность? Это один вызов метода?

[AlexanderUsatov]

Исходный код: github.com/AlexanderUsatov/sorting

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

[Prototik]

Гхм, измеряли время лапками? В приличном Java обществе такое порицают, перейдите на JMH.

[imanushin]

Спасибо за код! Я немного покорпел над ним — добавил сборку и т.д.
В общем — см. pull request #1. Сейчас, правда, там важная ошибка — несмотря на названия тестов, массивы создаются одного размера.

Если хотите запустить performance test: в папке src вызываете gradlew jmh

Итак, результаты (полная таблица тут) сортировки массива размера 1000 элементов с помощью jmh (как просил Prototik):

Array Sort: 56984,505 ± 243,710 ops/s
Hash Map sort: 2577,258 ± 27,491 ops/s

Или другими словами — стандартная сортировка пока быстрее.

Заодно я добавил тест, о котором говорил 1dash.

[AlexanderUsatov]

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

[imanushin]

А вот это я пропустил, массив создается абсолютно случайный.
Я добавлю Ваш алгоритм в benchmarks и перезапущу чуть позже. Как я уже говорил — в PR есть вызовы методов. Проверьте, пожалуйста, что они корректны.

[AlexanderUsatov]

Я там сегодня с утра пофиксил баг в usatovProkuratSortUsingHashMap. Про вызовы не очень понял, к сожалению. Если не сложно, поясните, пожалуйста.

[daiver19]

Я несколько раз перечитал код «Сортировка через HashMap» и каждый раз приходил к выходу, что этот код вернет массив в произвольном порядке. Можно сортировать подсчетом используя хэш таблицу вместо массива и получить некоторую экономию памяти в некоторых случаях, но в коде это не реализовано. Или я что-то упускаю?

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

[1dash]

Согласно коду, массив сортируется через Arrays.sort(res, Comparator.comparingInt(o -> o.first)) произвольного порядка не будет.

UPD: А вот usatovProkuratSortUsingHashMap не сортирует, у меня для generateArr(10, 0, 1000) выдает

720 672 128 965 694 214 778 42 893 991

[daiver19]

Именно об этой функции и шла речь. В usatovProkuratSortUsingMyHashTable сортировка есть, но как бы в общем случае эта функция эквивалентна обычной arrays.sort. Сортировкой подсчетом её так же можно назвать только с натяжкой.

[AlexanderUsatov]

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

[AlexanderUsatov]

Да, на таких входных данных я её не проверял. Действительно не сработало, завтра постараюсь переделать и обновить результаты тестов. Спасибо!

[AlexanderUsatov]

Большое спасибо, пофиксил.

[Wsl_F]

Сортировка через HashMap приведенная в статье работает за линейное время, а как нам всем хорошо известно, НЕвозможно реализовать сортировку (в общем виде), работающую быстрее, чем за O(n * log(n)). Ошибка заключается в том, что

hm.keySet()

возвращает НЕ упорядоченное множество ключей.

[AlexanderUsatov]

Мне уже указали на эту ошибку, и я её пофиксил. Обновил код в статье, на гитхабе и обновил результаты тестов. Спасибо за помощь!