Java Sammlung vs benutzerdefinierte Sortierung Sortierung - Geschwindigkeit

Question

mit Hilfe von Java-Sorter, das heißt:

Collections.sort(myArrayList, new Comparator<Integer>() { 
     @Override 
     public int compare(Integer o1, Integer o2) { 
     return x; 
     } 

    }); 

und

myArrayList.sort(new Comparator<Integer>() { 
     @Override 
     public int compare(Integer o1, Integer o2) { 
      return x; 
     } 

    }); 

mit umgeben 'out' Tags zeigen, dass die Methode 600-800 Millisekunden in Anspruch nimmt.

Dies ist einfach eine zu große Verzögerung beim Sortieren von 50 - 100 Arrays.

Meine Fragen ist, würden benutzerdefinierte Methoden zum Sortieren von Arrays schneller sein?

Der obige Code funktioniert sehr gut, aber es ist einfach viel zu langsam ...

Jedes Array (myArrayList) hat etwa 44 Elemente zu implementieren.

Es dauert 600-800 Millisekunden, um eine Sortierung abzuschließen, daher können 50-100 Arrays bis zu 80000 Millisekunden dauern.

Executable:

System.out(timeMillis); 
Collections.sort(fourtyFourItemsArrayL, new Comparator<Integer>() { 
      @Override 
      public int compare(Integer o1, Integer o2) { 
       Item i1 = o1 >= 16 ? player.getInventory().getItem(o1 - 16) : player.getEquipment().getItem(o1 - 1); 
       Item i2 = o2 >= 16 ? player.getInventory().getItem(o2 - 16) : player.getEquipment().getItem(o2 - 1); 
       int price1 = i1 == null ? 0 : i1.getDefinitions().getProtectionPrice(); 
       int price2 = i2 == null ? 0 : i2.getDefinitions().getProtectionPrice(); 
       if (price1 > price2) 
        return -1; 
       else if (price1 < price2) 
        return 1; 
       return 0; 
      } 

     }); 
System.out(timeMillis); 

Answer 1

Wenn mich nicht alles täuscht, die Java Collections.sort() verwenden Sortieralgorithmus mit Komplexität O (n lg n).

Wenn Sie eine eigene Sortiermethode erstellen möchten, die schneller als Collections.sort() ist, müssen Sie einen (n) Sortieralgorithmus wie Radix-Sort oder Counting Sort verwenden.

Wenn Ihre Einschränkung nur 50-100 Elemente im Array ist, verwende ich lieber Collections.sort(), anstatt viel Code zum Sortieren der Zahlen zu schreiben. Es gibt nicht viel Unterschied zwischen O (n lg n) und O (n), wenn n < = 100.

Wenn Sie 50-100 verschiedene Array sortieren möchten, können Sie Java Threading verwenden.

Answer 2

Wenn die Implementierung des Vergleichs langsam ist, wird die Sortierung mehr oder weniger langsam sein. Zunächst sollten Sie wirklich sicherstellen, dass alles, was für die Sortierung erforderlich ist, im Speicher verfügbar ist. Was macht player.getInventory(). GetItem (...)? Taucht es in eine Datenbank ein? oder eine Datei? Wenn es so ist, sind Sie in einer schlechten Fahrt. Beachten Sie auch, dass jedes Element mehr als einmal Teil eines compareTo (viel) sein wird. Ich würde vorschlagen, anstatt List<Integer> zu sortieren, erstellen Sie List<Item> dann sortieren Sie diese. dass die Anzahl der Zeiten werden Sie tun Item i1 = o1 >= 16 ? player.getInventory().getItem(o1 - 16) : player.getEquipment().getItem(o1 - 1);

Auch wenn i1.getDefinitions().getProtectionPrice() taucht in eine Datei, Datenbank oder ähnlich drastisch reduzieren, müssen Sie vorab holen das. Sie könnten eine Klasse erstellen, die nur die Ganzzahl enthält, und den protectionPrice, eine Liste dieser Klasse basierend auf der ursprünglichen Liste erstellen und diese dann sortieren. Ich kann fast eine Geschwindigkeitszunahme von 100x oder so garantieren.

Zusammenfassend glaube ich, dass Ihr Problem nicht der Sortieralgorithmus selbst ist, sondern wie Sie compareTo implementiert haben, und das Ändern des Sortieralgorithmus wird Ihr Problem nicht lösen.