Große Arrays primitiver Typen in absteigender Reihenfolge sortieren

Lesezeit: 6 Minuten

Benutzer-Avatar
Benedikt Waldvogel

Ich habe ein groß Array primitiver Typen (doppelt). Wie sortiere ich die Elemente ein? absteigende Reihenfolge?

Leider unterstützt die Java-API keine Sortierung von Primitive Typen mit einem Komparator.

Der erste Ansatz, der Ihnen wahrscheinlich in den Sinn kommt, ist die Umwandlung in eine Liste von Objekten (Boxing):

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

Diese Lösung ist wahrscheinlich für viele (oder sogar die meisten) Anwendungsfälle aber gut genug Boxen jedes Primitiv im Array ist zu langsam und verursacht viel GC-Druck wenn das Array groß ist!

Ein anderer Ansatz wäre, zu sortieren und dann umzukehren:

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;
}
   

Dieser Ansatz kann auch zu langsam sein wenn das Array schon recht gut sortiert ist.

Was ist eine bessere Alternative, wenn die Arrays groß sind und Leistung das Hauptoptimierungsziel ist?

Benutzer-Avatar
Benutzer29480

Ich denke, es wäre am besten, das Rad nicht neu zu erfinden und Arrays.sort() zu verwenden.

Ja, ich habe den “absteigenden” Teil gesehen. Das Sortieren ist der schwierige Teil, und Sie möchten von der Einfachheit und Geschwindigkeit des Java-Bibliothekscodes profitieren. Sobald das erledigt ist, kehren Sie einfach das Array um, was eine relativ billige O(n)-Operation ist. Hier ist ein Code Ich fand, dies in nur 4 Zeilen zu tun:

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;
}

  • Diese Antwort sollte akzeptiert werden. Es ist viel schneller als die Alternativen (Boxen + Sortieren + Unboxen, mit oder ohne Streams)

    – Tucuxi

    18. Oktober 2021 um 17:27 Uhr

  • Das Sortieren plus Umkehren des Arrays ist sogar eine mögliche Lösung, die Sie in meiner Frage finden. Es ist wahrscheinlich eine gute Lösung für die meisten Fälle. In dem Fall, nach dem ich gefragt habe, war die Geschwindigkeit jedoch wirklich wichtig, und es war wahrscheinlich, dass das Array bereits sortiert war. In diesem Fall ist das Umkehren des Arrays ein erheblicher Overhead, selbst wenn es sich nur um eine O(n)-Operation handelt. Letztendlich sollte eine Optimierung wie der Einsatz von „Java Primitive“ sicherlich nur dann angewendet werden, wenn ein guter Benchmark zeigt, dass sich die Kosten (zB die zusätzliche Abhängigkeit) wirklich lohnen.

    – Benedikt Waldvogel

    Vor 17 Stunden


Benutzer-Avatar
Brandon

Java-Primitive Enthält Funktionen zum Sortieren von primitiven Arrays basierend auf einem benutzerdefinierten Komparator. Mit ihm und Java 8 könnte Ihr Beispiel folgendermaßen geschrieben werden:

double[] array = new double[1048576];
...
Primitive.sort(array, (d1, d2) -> Double.compare(d2, d1), false);

Wenn Sie Maven verwenden, können Sie es einbinden mit:

<dependency>
    <groupId>net.mintern</groupId>
    <artifactId>primitive</artifactId>
    <version>1.2.1</version>
</dependency>

Wenn du passierst false als drittes Argument zu sortverwendet es eine instabile Sortierung, eine einfache Bearbeitung von Javas eingebautem Dual-Pivot-Quicksort. Das bedeutet, dass die Geschwindigkeit nahe an der der eingebauten Sortierung liegen sollte.

Vollständige Offenlegung: Ich habe die Java Primitive Library geschrieben.

  • Dies ist ein großartiges, einfaches Projekt auf GitHub. Sehr gute Arbeit! Auch das sollten Leser beachten true als drittes Argument zu sort wird eine einfache Bearbeitung von Javas eingebautem TimSort verwenden, das stabil ist.

    – Kevinarpe

    18. April 2016 um 11:02 Uhr

Hier ist ein Einzeiler, der Streams in Java 8 verwendet

int arr = new int[]{1,2,3,4,5};
Arrays.stream(arr).boxed().sorted(Collections.reverseOrder()).mapToInt(Integer::intValue).toArray();

  • Boxen jedes Primitiv im Array ist zu teuer für große Arrays!

    – Benedikt Waldvogel

    1. November 2019 um 14:25 Uhr


  • Großartig, danke. Es ist gut, einen funktionierenden Einzeiler mit Standard-Java-Methoden zu haben. Wenn es für große Arrays tatsächlich zu langsam ist, ist es immer möglich, es umzugestalten.

    – Eric Duminil

    25. Mai 2020 um 12:28 Uhr

Guave verfügt über Methoden zum Konvertieren primitiver Arrays in Listen von Wrapper-Typen. Das Schöne daran ist, dass diese Listen Live-Ansichten sind, sodass Operationen auf ihnen auch auf den zugrunde liegenden Arrays funktionieren (ähnlich wie bei Arrays.asList()aber für Primitiven).

Auf jeden Fall kann an jede dieser Listen weitergegeben werden Collections.reverse():

int[] intArr = { 1, 2, 3, 4, 5 };
float[] floatArr = { 1.0f, 2.0f, 3.0f, 4.0f, 5.0f };
double[] doubleArr = { 1.0d, 2.0d, 3.0d, 4.0d, 5.0d };
byte[] byteArr = { 1, 2, 3, 4, 5 };
short[] shortArr = { 1, 2, 3, 4, 5 };
Collections.reverse(Ints.asList(intArr));
Collections.reverse(Floats.asList(floatArr));
Collections.reverse(Doubles.asList(doubleArr));
Collections.reverse(Bytes.asList(byteArr));
Collections.reverse(Shorts.asList(shortArr));
System.out.println(Arrays.toString(intArr));
System.out.println(Arrays.toString(floatArr));
System.out.println(Arrays.toString(doubleArr));
System.out.println(Arrays.toString(byteArr));
System.out.println(Arrays.toString(shortArr));

Ausgabe:

[5, 4, 3, 2, 1]
[5.0, 4.0, 3.0, 2.0, 1.0]
[5.0, 4.0, 3.0, 2.0, 1.0]
[5, 4, 3, 2, 1]
[5, 4, 3, 2, 1]

Benutzer-Avatar
Jason Cohen

Ihre Implementierung (die in der Frage) ist schneller als zB Wrapping mit toList() und Verwenden eines Komparator-basierten Verfahrens. Das automatische Boxen und Durchlaufen von Komparatormethoden oder umschlossenen Collections-Objekten ist weitaus langsamer als das einfache Umkehren.

Natürlich könnten Sie Ihre eigene Sorte schreiben. Das ist vielleicht nicht die Antwort, nach der Sie suchen, aber Beachten Sie, dass Sie, wenn Ihr Kommentar zu “wenn das Array bereits ziemlich gut sortiert ist” häufig vorkommt, möglicherweise besser daran tun, einen Sortieralgorithmus zu wählen, der diesen Fall gut behandelt (z. B. Einfügen), anstatt ihn zu verwenden Arrays.sort() (was Mergesort oder Einfügen ist, wenn die Anzahl der Elemente klein ist).

  • Sie können Arrays.toList nicht auf einem Double aufrufen[] und lass es tun, was du willst; Arrays.toList muss ein Double übergeben werden[] und nicht ein Array primitiver Typen.

    – Eli Courtwright

    18. Oktober 2008 um 17:19 Uhr

  • Arrays.asList(neues double[]{}); kompiliert ok.

    – Johnstok

    18. Oktober 2008 um 17:27 Uhr

  • Das ist mein Punkt; Ich fasse dieses Problem in meiner neu bearbeiteten Antwort zusammen.

    – Eli Courtwright

    18. Oktober 2008 um 17:34 Uhr

Benutzer-Avatar
Krystjan Cybulski

Sie können Komparatoren nicht zum Sortieren primitiver Arrays verwenden.

Am besten implementieren (oder leihen Sie sich eine Implementierung) eines Sortieralgorithmus angemessen für Ihren Anwendungsfall, um das Array zu sortieren (in Ihrem Fall in umgekehrter Reihenfolge).

  • Sie können Arrays.toList nicht auf einem Double aufrufen[] und lass es tun, was du willst; Arrays.toList muss ein Double übergeben werden[] und nicht ein Array primitiver Typen.

    – Eli Courtwright

    18. Oktober 2008 um 17:19 Uhr

  • Arrays.asList(neues double[]{}); kompiliert ok.

    – Johnstok

    18. Oktober 2008 um 17:27 Uhr

  • Das ist mein Punkt; Ich fasse dieses Problem in meiner neu bearbeiteten Antwort zusammen.

    – Eli Courtwright

    18. Oktober 2008 um 17:34 Uhr

Benutzer-Avatar
verrückt

Ich denke, die einfachste Lösung ist immer noch:

  1. Erhalten der natürlichen Reihenfolge des Arrays
  2. Finden des Maximums innerhalb dieses sortierten Arrays, das dann das letzte Element ist
  3. Verwenden einer for-Schleife mit Dekrementoperator

Wie bereits von anderen gesagt: Die Verwendung von toList ist zusätzlicher Aufwand, Arrays.sort(array,Collections.reverseOrder()) funktioniert nicht mit Primitives und die Verwendung eines zusätzlichen Frameworks scheint zu kompliziert zu sein, wenn alles, was Sie brauchen, bereits eingebaut und daher wahrscheinlich schneller ist als Gut…

Beispielcode:

import java.util.Arrays;

public class SimpleDescending {

    public static void main(String[] args) {

        // unsorted array
        int[] integerList = {55, 44, 33, 88, 99};

        // Getting the natural (ascending) order of the array
        Arrays.sort(integerList);

        // Getting the last item of the now sorted array (which represents the maximum, in other words: highest number)
        int max = integerList.length-1;

        // reversing the order with a simple for-loop
        System.out.println("Array in descending order:");
        for(int i=max; i>=0; i--) {
            System.out.println(integerList[i]);
        }

        // You could make the code even shorter skipping the variable max and use
        // "int i=integerList.length-1" instead of int "i=max" in the parentheses of the for-loop
    }
}

1381960cookie-checkGroße Arrays primitiver Typen in absteigender Reihenfolge sortieren

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy