Java技術Web開發高級語言其他技術腳本語言數據庫大數據教程XML技術專業教育框架軟件工具教程通信技術微軟技術軟件測試手機開發前端技術人工智能實例代碼

Arrays.sort() 和 Collections.sort() 之間的差異

瀏覽人數：332最近更新：

    1. 概述

    排序是計算機科學中的一項基本操作，對於跨各種應用程式的資料組織和操作至關重要。

    在本教程中，我們將比較 Java 常用的排序方法： Arrays.sort()和Collections.sort() 。雖然服務於相同的主要功能（對資料進行排序），但每種方法都有自己的功能、注意事項和最佳用例。

    2. 基本概述

    讓我們先檢查這兩種方法之間的根本差異。

    2.1. Arrays.sort()

    Arrays.sort()方法是 Java 中用來對陣列進行排序的實用函數。它允許對原始資料類型和物件的陣列進行排序。無論我們處理的是數字資料還是字母字串， Arrays.sort()都可以按升序排列元素。此外，我們可以使用物件陣列的自訂比較器來修改行為。此方法是java.util.Arrays類別的一部分，該類別提供了一套用於數組操作的實用程式。

    2.2. Collections.sort()

    另一方面， Collections.sort()是為 Java 的 Collection Framework 中的List介面的實例進行排序而設計的。與僅限於陣列的Arrays.sort()不同， Collections.sort()可以對更多動態資料結構進行排序，例如ArrayList 、 LinkedList和其他實作List介面的類別。 Collections.sort()是java.util.Collections類別的成員，該類別是一個實用程式類，其中充滿了用於操作集合的靜態方法。

    3.穩定性

    假設我們有一組任務：

    tasks = new ArrayList<>();
 tasks.add(new Task(1, 1, "2023-09-01"));
 tasks.add(new Task(2, 2, "2023-08-30"));
 tasks.add(new Task(3, 1, "2023-08-29"));
 tasks.add(new Task(4, 2, "2023-09-02"));
 tasks.add(new Task(5, 3, "2023-09-05"));
 tasks.add(new Task(6, 1, "2023-09-03"));
 tasks.add(new Task(7, 3, "2023-08-28"));
 tasks.add(new Task(8, 2, "2023-09-01"));
 tasks.add(new Task(9, 1, "2023-08-28"));
 tasks.add(new Task(10, 2, "2023-09-04"));
 tasks.add(new Task(11, 3, "2023-08-31"));
 tasks.add(new Task(12, 1, "2023-08-30"));
 tasks.add(new Task(13, 3, "2023-09-02"));

    我們希望先按優先順序然後按截止日期對它們進行排序。我們將使用兩種不同的方法對它們進行排序。在第一種情況下，我們將使用Collections提供的穩定演算法：

    final List<Task> tasks = Tasks.supplier.get();
 Collections.sort(tasks, Comparator.comparingInt(Task::getPriority));
 System.out.println("After sorting by priority:");
 for (Task task : tasks) {
 System.out.println(task);
 }
 Collections.sort(tasks, Comparator.comparing(Task::getDueDate));
 System.out.println("\nAfter sorting by due date:");
 for (Task task : tasks) {
 System.out.println(task);
 }

    此外，我們將使用不穩定的演算法對任務進行排序。因為 Java 不提供使用不穩定演算法對引用類型清單進行排序的選項，所以我們有一個簡單的快速排序實作：

    List<Task> tasks = Tasks.supplier.get();
 quickSort(tasks, Comparator.comparingInt(Task::getPriority));
 System.out.println("After sorting by priority:");
 for (Task task : tasks) {
 System.out.println(task);
 }
 quickSort(tasks, Comparator.comparing(Task::getDueDate));
 System.out.println("\nAfter sorting by due date:");
 for (Task task : tasks) {
 System.out.println(task);
 }

    代碼總體是一樣的。唯一的區別是使用的演算法。排序分兩步驟進行。第一步依優先順序對任務進行排序，第二步則依截止日期對任務進行排序。

    結果的差異很微妙，但可能會顯著影響程式碼的功能並引入難以偵錯的錯誤。穩定版本產生以下輸出：

    After sorting by due date:
 Task: #9 | Priority: 1 | Due Date: 2023-08-28
 Task: #7 | Priority: 3 | Due Date: 2023-08-28
 Task: #3 | Priority: 1 | Due Date: 2023-08-29
 Task: #12 | Priority: 1 | Due Date: 2023-08-30
 Task: #2 | Priority: 2 | Due Date: 2023-08-30
 Task: #11 | Priority: 3 | Due Date: 2023-08-31
 Task: #1 | Priority: 1 | Due Date: 2023-09-01
 Task: #8 | Priority: 2 | Due Date: 2023-09-01
 Task: #4 | Priority: 2 | Due Date: 2023-09-02
 Task: #13 | Priority: 3 | Due Date: 2023-09-02
 Task: #6 | Priority: 1 | Due Date: 2023-09-03
 Task: #10 | Priority: 2 | Due Date: 2023-09-04
 Task: #5 | Priority: 3 | Due Date: 2023-09-05

    任務按日期排序，日期相同時將保存先前的優先順序排序。而不穩定的版本給了我們這個：

    After sorting by due date:
 Task: #9 | Priority: 1 | Due Date: 2023-08-28
 Task: #7 | Priority: 3 | Due Date: 2023-08-28
 Task: #3 | Priority: 1 | Due Date: 2023-08-29
 Task: #2 | Priority: 2 | Due Date: 2023-08-30
 Task: #12 | Priority: 1 | Due Date: 2023-08-30
 Task: #11 | Priority: 3 | Due Date: 2023-08-31
 Task: #1 | Priority: 1 | Due Date: 2023-09-01
 Task: #8 | Priority: 2 | Due Date: 2023-09-01
 Task: #4 | Priority: 2 | Due Date: 2023-09-02
 Task: #13 | Priority: 3 | Due Date: 2023-09-02
 Task: #6 | Priority: 1 | Due Date: 2023-09-03
 Task: #10 | Priority: 2 | Due Date: 2023-09-04
 Task: #5 | Priority: 3 | Due Date: 2023-09-05

    任務#2 和#12 有相同的截止日期，但優先順序相反。這是因為不穩定的演算法在處理相同但可區分的項目時會產生不確定的行為。

    因為原語沒有標識或附加參數，所以我們可以使用不穩定的演算法對它們進行排序。它們唯一擁有的就是一個值，這就是為什麼我們不關心用於原語的演算法的穩定性。如上例所示，穩定性特徵對於物體排序至關重要。

    這就是為什麼Arrays.sort()對基元使用不穩定演算法的相同實現，例如快速排序或雙軸快速排序。在處理參考類型的集合時， Arrays.sort()和Collections.sort()使用相同的實現，通常是合併排序或 TimSort。

    4. 複雜性

    讓我們舉一個簡單的例子來比較合併排序和快速排序，以顯示這些演算法之間的差異，以及最終Collections.sort()和Arrays.sort()之間的差異。我們將為它們使用簡單的實作。這樣做的部分原因是Java不提供這些演算法，所以我們可以直接選擇它們，部分原因是目前的演算法有太多的調整和改進。因此，很難為它們開發類似的測試案例。

    我們將執行以下測試來比較吞吐量：

    @Measurement(iterations = 2, time = 10, timeUnit = TimeUnit.MINUTES)
 @Warmup(iterations = 5, time = 10)
 public class PerformanceBenchmark {

 private static final Random RANDOM = new Random();
 private static final int ARRAY_SIZE = 10000;
 private static final int[] randomNumbers = RANDOM.ints(ARRAY_SIZE).toArray();
 private static final int[] sameNumbers = IntStream.generate(() -> 42).limit(ARRAY_SIZE).toArray();
 public static final Supplier<int[]> randomNumbersSupplier = randomNumbers::clone;
 public static final Supplier<int[]> sameNumbersSupplier = sameNumbers::clone;

 @Benchmark
 @BenchmarkMode(Mode.Throughput)
 @Fork(value = 1, jvmArgs = {"-Xlog:gc:file=gc-logs-quick-sort-same-number-%t.txt,filesize=900m -Xmx6gb -Xms6gb"})
 public void quickSortSameNumber() {
 Quicksort.sort(sameNumbersSupplier.get());
 }
 @Benchmark
 @BenchmarkMode(Mode.Throughput)
 @Fork(value = 1, jvmArgs = {"-Xlog:gc:file=gc-logs-quick-sort-random-number-%t.txt,filesize=900m -Xmx6gb -Xms6gb"})
 public void quickSortRandomNumber() {
 Quicksort.sort(randomNumbersSupplier.get());
 }
 @Benchmark
 @BenchmarkMode(Mode.Throughput)
 @Fork(value = 1, jvmArgs = {"-Xlog:gc:file=gc-logs-merge-sort-same-number-%t.txt,filesize=900m -Xmx6gb -Xms6gb"})
 public void mergeSortSameNumber() {
 MergeSort.sort(sameNumbersSupplier.get());
 }
 @Benchmark
 @BenchmarkMode(Mode.Throughput)
 @Fork(value = 1, jvmArgs = {"-Xlog:gc:file=gc-logs-merge-sort-random-number-%t.txt,filesize=900m -Xmx6gb -Xms6gb"})
 public void mergeSortRandomNumber() {
 MergeSort.sort(randomNumbersSupplier.get());
 }
 }

    執行這些測試後，我們得到了兩個工件：一個是效能指標，另一個是垃圾收集日誌。

    4.1.時間複雜度

    讓我們回顧一下上述測試的效能指標：

    Benchmark Mode Cnt Score Error Units
 PerformanceBenchmark.mergeSortRandomNumber thrpt 4 1489.983 ± 401.330 ops/s
 PerformanceBenchmark.quickSortRandomNumber thrpt 4 2757.273 ± 29.606 ops/s

    首先，使用快速排序對隨機數進行排序，一般來說，速度幾乎是合併排序的兩倍。快速排序就地發生這一事實降低了影響效能的空間複雜度，我們將在下一節中討論這一點。

    此外，我們可以看到，在某些情況下，快速排序可能會很快退化：

    Benchmark Mode Cnt Score Error Units
 PerformanceBenchmark.mergeSortSameNumber thrpt 4 5295.502 ± 98.624 ops/s
 PerformanceBenchmark.quickSortSameNumber thrpt 4 118.211 ± 0.117 ops/s

    例如，當所有數字都相同時，MergeSort 的效能要好得多，而且速度非常快。儘管我們使用的是快速排序和合併排序的簡單實現，但其行為通常與其更優化和更複雜的對應項相似。

    請記住，演算法的效能與其時間複雜度可能不相關，因為我們應該額外考慮很多事情：空間複雜度、隱藏常數因子、最佳化、適應性等。

    快速排序和雙樞軸快速排序的上限高於合併排序或 TimSort。然而，由於一系列的改進和檢查，性能問題變得可以忽略不計，總體上可以忽略不計。因此，我們可以假設歸併排序、TimSort、快速排序和雙樞軸快速排序具有相同的時間複雜度。

    例如，DualPivotQuicksort.sort() 方法會考慮許多參數，例如平行化、陣列大小、預先排序運行，甚至遞歸深度。根據基本類型和陣列的大小，Java 可以使用不同的演算法，例如插入排序或計數排序。這就是為什麼很難比較高度最佳化的演算法；它們通常會產生類似的結果。

    4.2.空間複雜度

    如前所述，儘管快速排序和雙樞軸快速排序演算法不穩定，但它們需要權衡，因為它們使用的空間較少。根據實現的不同，它們最多可能具有 O(log*n) 空間複雜度。這是一個很好的功能，可能會對效能產生重大影響。在我們的例子中，讓我們集中精力對隨機數進行排序。

    雖然這些演算法的時間複雜度被認為大致相同，但效能卻存在巨大差異：

    Benchmark Mode Cnt Score Error Units
 PerformanceBenchmark.mergeSortRandomNumber thrpt 4 1489.983 ± 401.330 ops/s
 PerformanceBenchmark.quickSortRandomNumber thrpt 4 2757.273 ± 29.606 ops/s

    為了研究這種差異，我們可以查看垃圾收集日誌。我們將使用 IBM Garbage Collection 和 Memory Visualizer：

    變體歸併排序快速排序
    強制收集計數00
    完整系列00
    氣相層析模式G1G1
    平均垃圾收集暫停（毫秒）0.330.47
    分配失敗觸發的回收次數26848第588章
    垃圾收集暫停所花費的時間比例 (%)0.720.02
    停止世界垃圾收集暫停所花費的時間比例 (%)0.720.02
    未暫停的時間比例 (%)99.2899.98
    年輕回收－平均垃圾回收暫停（毫秒）0.330.47
    年輕集合 – 集合之間的平均間隔（毫秒）46.62124

    正如我們所看到的，MergeSort 的垃圾收集事件數量明顯更高（26848 比 588），這是可以理解的，因為演算法使用更多空間。

    4.3.最佳化

    由於歸併排序和 TimSort 需要更多空間，因此對基元使用不穩定演算法是最佳化步驟，假設快速排序和雙樞軸快速排序退化為 O(n^2) 的情況可以忽略不計。從技術上講，可以對引用類型的集合使用不穩定的排序演算法並提高效能。如果穩定性不重要或相同的物件不可區分，則可以這樣做。

    我們可以對包裝類別使用的改進之一是將它們轉換為基元，進行排序，然後將它們轉換回來。讓我們考慮以下測試：

    @Measurement(iterations = 2, time = 10, timeUnit = TimeUnit.MINUTES)
 @Warmup(iterations = 5, time = 10)
 @Fork(value = 2)
 public class ObjectOverheadBenchmark {

 private static final ThreadLocalRandom RANDOM = ThreadLocalRandom.current();

 @State(Scope.Benchmark)
 public static class Input {
 public Supplier<List<Integer>> randomNumbers = () -> RANDOM.ints().limit(10000).boxed().collect(Collectors.toList());
 }

 @Benchmark
 @BenchmarkMode(Mode.Throughput)
 public void sortingPrimitiveArray(Input input, Blackhole blackhole) {
 final int[] array = input.randomNumbers.get().stream().mapToInt(Integer::intValue).toArray();
 Arrays.sort(array);
 final List<Integer> result = Arrays.stream(array).boxed().collect(Collectors.toList());
 blackhole.consume(result);
 }

 @Benchmark
 @BenchmarkMode(Mode.Throughput)
 public void sortingObjectArray(Input input, Blackhole blackhole) {
 final Integer[] array = input.randomNumbers.get().toArray(new Integer[0]);
 Arrays.sort(array);
 blackhole.consume(array);
 }

 @Benchmark
 @BenchmarkMode(Mode.Throughput)
 public void sortingObjects(Input input, Blackhole blackhole) {
 final List<Integer> list = input.randomNumbers.get();
 Collections.sort(list);
 blackhole.consume(list);
 }
 }

    事實上，我們在這裡使用Arrays.sort()顯著提高了Collection.sort():

    Benchmark Mode Cnt Score Error Units
 ObjectOverheadBenchmark.sortingObjectArray thrpt 4 982.849 ± 19.201 ops/s
 ObjectOverheadBenchmark.sortingObjects thrpt 4 976.778 ± 10.580 ops/s
 ObjectOverheadBenchmark.sortingPrimitiveArray thrpt 4 1998.818 ± 373.654 ops/s

    對int[]進行排序可使效能提高 100% 以上。

    5. Arrays.sort()和Collections.sort()的實作細節

    請注意前面部分中使用的演算法和測試。它們不反映庫實現的效能，因為它們具有更複雜的流程，允許它們優化特定案例。提供這些測試只是為了提供有關這兩種演算法的簡單實現的內部工作原理的更多直觀資訊。

    如果沒有底層演算法，幾乎不可能比較Collections.sort()和Arrays.sort() 。

    底層演算法是決定這兩種方法複雜性和效能的關鍵部分。因為Collections.sort()的實作考慮到了穩定性，所以它們使用合併排序或 TimSort。同時，排序基元不需要此屬性，可以使用快速排序或雙軸快速排序。

    為了更好地理解這些方法，我們研究了它們直接使用的排序演算法。

    六，結論

    排序是計算機科學的基石操作之一，可以跨許多應用程式進行高效的資料操作。透過了解演算法之間的差異，我們可以根據您的特定要求在編碼和最佳化效能和功能時做出更明智的決策。

    因此，儘管本文旨在強調Collections.sort()和Arrays.sort().它也是理解不同排序演算法之間差異的一個很好的指南。與往常一樣，可以在 GitHub 上找到實作該演算法的程式碼。

    本作品係原創或者翻譯，採用《署名-非商業性使用-禁止演繹4.0國際》許可協議

    最新文章

    為 Spring Cloud Gateway 設定 CORS 策略按任何匹配字段過濾列表在 Hibernate 中使用 Array/JSON/XML 類型儲存基本陣列和集合Kafka 中的消費者搜索Java中從類別載入器取得類別路徑使用 Java 確定 Excel 檔案中的空白行使用 Spring Boot 自動建立資料庫架構帶有請求正文的 HTTP 刪除尋找數組中第一個重複元素的索引在 Java 中將 JDBC 結果集轉換為 CSV