Массивы вида типов примитивов в порядке убывания

У меня есть большой массив типов примитивов (дважды). Как я сортирую элементы в порядке убывания?

К сожалению, Java API не поддерживает сортировку типов примитивов с Компаратором.

Первый подход, который, вероятно, приходит на ум, должен преобразовать его в список объектов (упаковка):

double[] array = new double[1048576];    
Arrays.stream(array).boxed().sorted(Collections.reverseOrder())…

Однако упаковка каждого примитива в массиве является слишком медленной и вызывает большое давление GC!

Другой подход должен был бы отсортировать и затем реверс:

double[] array = new double[1048576];
...
Arrays.sort(array);
// reverse the array
for (int i = 0; i < array.length / 2; i++) {
     // swap the elements
     double temp = array[i];
     array[i] = array[array.length - (i + 1)];
     array[array.length - (i + 1)] = temp;
}

Этот подход является также медленным - особенно, если массив уже отсортирован вполне хорошо.

Что лучшее альтернативно?

47
задан Benedikt Waldvogel 1 November 2019 в 14:30
поделиться

0 ответов

Ваш алгоритм корректен. Но мы можем сделать оптимизацию следующим образом: При инвертировании можно попытаться сохранить другую переменную для сокращения обратного счетчика начиная с вычислений array.length-(i+1), может занять время! И также переместите объявление временного файла снаружи так, чтобы каждый раз это не было выделено

double temp;

for(int i=0,j=array.length-1; i < (array.length/2); i++, j--) {

     // swap the elements
     temp = array[i];
     array[i] = array[j];
     array[j] = temp;
}
0
ответ дан cricket_007 26 November 2019 в 19:53
поделиться

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

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

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

, Как кто-то еще указал, может быть еще лучше запуститься с сортированного массива и сохранить отсортированным при изменении содержания. Это может работать еще лучше.

0
ответ дан myplacedk 26 November 2019 в 19:53
поделиться

Я не знаю, что любой примитив сортирует средства в API ядра Java.

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

0
ответ дан Leo 26 November 2019 в 19:53
поделиться

Вы не можете использовать Компараторы для сортировки примитивных массивов.

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

1
ответ дан Krystian Cybulski 26 November 2019 в 19:53
поделиться

Был некоторый беспорядок [приблизительно 111] в других ответах. Если Вы скажете

double[] arr = new double[]{6.0, 5.0, 11.0, 7.0};
List xs = Arrays.asList(arr);
System.out.println(xs.size());  // prints 1

тогда, то у Вас будет Список с 1 элементом. Получающийся Список имеет двойное [] массив как его собственный элемент. То, что Вы хотите, должно иметь List<Double>, чьи элементы являются элементами double[].

, К сожалению, никакое решение, включающее Компараторы, не будет работать на примитивный массив. Arrays.sort только принимает Компаратор, будучи переданным Object[]. И поскольку причины описывают выше, Arrays.asList не позволит Вам составить Список из элементов Вашего массива.

Так несмотря на мой более ранний ответ, который комментарии ниже ссылки, нет никакого лучшего пути, чем ручное инвертирование массива после сортировки. Любой другой подход (такой как копирование элементов в Double[] и сортировка реверса и копирование их назад) был бы большим количеством кода и медленнее.

1
ответ дан Eli Courtwright 26 November 2019 в 19:53
поделиться

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

, Конечно, Вы могли записать свой собственный вид. Это не могло бы быть ответом, который Вы ищете, , но примечание, что, если Ваш комментарий о, "если массив уже отсортирован вполне хорошо", часто происходит, Вы могли бы преуспеть для выбора алгоритма сортировки, который обрабатывает тот случай хорошо (например, вставка), а не использует Arrays.sort() (который является сортировкой с объединением или вставкой, если число элементов является небольшим).

1
ответ дан Jason Cohen 26 November 2019 в 19:53
поделиться
double[] array = new double[1048576];

...

Согласно порядку по умолчанию возрастает

Для инвертирования порядка

Arrays.sort(array,Collections.reverseOrder());
1
ответ дан vitaut 26 November 2019 в 19:53
поделиться

Я думаю, что было бы лучше не перестроить колесо и использовать Arrays.sort ().

Да, я видел "убывающую" часть. Сортировка является твердой частью, и Вы хотите извлечь выгоду из простоты и скорости кода библиотеки Java. Как только это сделано, Вы просто инвертируете массив, который является относительно дешевым O (n) операция. Вот некоторый код , я нашел для выполнения в этом всего 4 строки:

for (int left=0, right=b.length-1; left<right; left++, right--) {
    // exchange the first and last
    int temp = b[left]; b[left]  = b[right]; b[right] = temp;
}
16
ответ дан JerryGoyal 26 November 2019 в 19:53
поделиться
Другие вопросы по тегам:

Похожие вопросы: