Комментарии 17
Опубликуйте, пожалуйста, код на github (если там нет комерческой тайны).
И вопрос: а как вы замеряли производительность? Это один вызов метода?
Исходный код: github.com/AlexanderUsatov/sorting
Скорость работы замерял разницей во времени после и до вызова метода. Естественно, делал это больше одного раза. Но результаты были очень похожими, поэтому я не считал среднее время, а оставил результаты первого теста
Скорость работы замерял разницей во времени после и до вызова метода. Естественно, делал это больше одного раза. Но результаты были очень похожими, поэтому я не считал среднее время, а оставил результаты первого теста
Гхм, измеряли время лапками? В приличном Java обществе такое порицают, перейдите на JMH.
Спасибо за код! Я немного покорпел над ним — добавил сборку и т.д.
В общем — см. 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.
Скажите, а какой был диапазон значений при 1000 элементов? В статье я утверждал, что мой метод лучше подходит для тех случаев, когда размерность массива значительно больше количества уникальных элементов.
Я несколько раз перечитал код «Сортировка через HashMap» и каждый раз приходил к выходу, что этот код вернет массив в произвольном порядке. Можно сортировать подсчетом используя хэш таблицу вместо массива и получить некоторую экономию памяти в некоторых случаях, но в коде это не реализовано. Или я что-то упускаю?
П.С. Представленная сортировка с помощью дерева сортировкой подсчетом не является. Это буквально сортировка деревом, аналогично сортировке кучей (и, очевидно, она гораздо менее оптимальна)
П.С. Представленная сортировка с помощью дерева сортировкой подсчетом не является. Это буквально сортировка деревом, аналогично сортировке кучей (и, очевидно, она гораздо менее оптимальна)
Согласно коду, массив сортируется через Arrays.sort(res, Comparator.comparingInt(o -> o.first)) произвольного порядка не будет.
UPD: А вот usatovProkuratSortUsingHashMap не сортирует, у меня для generateArr(10, 0, 1000) выдает
720 672 128 965 694 214 778 42 893 991
UPD: А вот usatovProkuratSortUsingHashMap не сортирует, у меня для generateArr(10, 0, 1000) выдает
720 672 128 965 694 214 778 42 893 991
Именно об этой функции и шла речь. В usatovProkuratSortUsingMyHashTable сортировка есть, но как бы в общем случае эта функция эквивалентна обычной arrays.sort. Сортировкой подсчетом её так же можно назвать только с натяжкой.
Как я и говорил в статье, эта сортировка отлично подходит для случаев, когда размер массива большой, а уникальных элементов значительно меньше. Для этих случаев она, на мой взгляд, определённо будет являться сортировкой подсчётом. В Противном случае, т.е когда у нас практически все элементы разные, она тоже будет являться сортировкой подсчётом, но смысла в этом, конечно, будет немного
Да, на таких входных данных я её не проверял. Действительно не сработало, завтра постараюсь переделать и обновить результаты тестов. Спасибо!
Большое спасибо, пофиксил.
Сортировка через HashMap приведенная в статье работает за линейное время, а как нам всем хорошо известно, НЕвозможно реализовать сортировку (в общем виде), работающую быстрее, чем за O(n * log(n)). Ошибка заключается в том, что
hm.keySet()Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Сортировка… хэш-таблицей (ещё подсчётом-деревом и HashMap'ом)