Java集合排序VS自定義排序 - 速度

Question

用java分揀機，即：

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

    }); 

和

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

    }); 

周圍有 '出' 的標籤表明，該方法需要600-800毫秒內完成。 100陣列 -

此排序50時，僅僅是太大的延遲。

我的問題是，將創建自定義的方法排序數組是任何更快？

上面的代碼工作得很好，但僅僅是方法來實現速度太慢......

每個陣列（myArrayList）有大約44元。

需要600-800毫秒才能完成1次排序，因此50-100個陣列最多可能需要80000毫秒。

可執行文件：

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

如果我沒有記錯，Java的Collections.sort（）使用排序與複雜度爲O（n LG n）的算法。

如果您想要構建比Collections.sort（）更快的排序方法，則需要使用O（n）排序算法，如Radix-Sort或Counting Sort。

如果你的約束只有50-100個元素在數組中，我寧願使用Collections.sort（）而不是寫很多代碼來排序數字。當n < = 100時，O（n lg n）與O（n）之間沒有太大差別。

如果要對50-100個不同的陣列進行排序，可以使用Java Threading。

Answer 2

如果比較的執行速度很慢，那麼所有的排序都會或多或少地緩慢。首先，你確實應該確保這種排序所需的一切都可以在內存中使用。 player.getInventory（）。getItem（...）做什麼？它是否潛入數據庫？或一個文件？ 如果確實如此，那麼您的乘坐感覺很糟糕。 另外，考慮到每個項目都會比compareTo（很多）多一次。 我建議，而不是排序List<Integer>，創建List<Item>然後進行排序的。 這會大大減少您的操作次數Item i1 = o1 >= 16 ? player.getInventory().getItem(o1 - 16) : player.getEquipment().getItem(o1 - 1);

此外，如果i1.getDefinitions().getProtectionPrice()潛入文件，數據庫或類似文件，您需要預取。 您可以創建一個僅包含Integer和protectPrice的類，根據原始列表創建此類的列表，然後對其進行排序。我幾乎可以保證速度提高100倍左右。總之，我認爲你的問題不是排序算法本身，而是你如何實現compareTo，改變排序算法並不能解決你的問題。