對數組中的整數進行遞歸求和
1. 概述
當我們處理數字時,對數組中的所有整數求和是常見的操作。此外,遞歸通常可以提供優雅的解決方案。
在本教程中,我們將探討如何使用遞迴對數組中的整數求和。
2. 數組複製的遞迴
首先,讓我們初始化一個整數陣列:
private static final int[] INT_ARRAY = { 1, 2, 3, 4, 5 };
顯然,上面數組中的整數和是15。
對陣列中的數字求和的常用方法是 sum (array[0-n]) = array[0] + array[1] + array[2] + array[3] + … + array[n].
這個方法很簡單。或者,我們可以從不同的角度來看待這個問題:數組中的數字總和等於第一個數字加上子數組中其餘數字的總和:
sumOf(array[0..n]) = array[0] + sumOf(subArray[1..n]).
現在,如果我們將sumOf()
視為函數或方法,我們可以看到sumOf()'s
主體再次呼叫sumOf()
。因此, sumOf()
是一種遞歸方法。
由於 Java 不允許我們在創建數組後更改數組的長度,因此從數組中刪除元素在技術上是不可能的。但是 Java 提供了多種複製數組的方法。我們可以使用這些方法來建立子數組。
當我們實作遞歸方法時,定義基本情況至關重要。基本情況是退出遞迴的某一點。否則,如果沒有基本情況,該方法將無休止地遞歸呼叫自身,直到拋出StackOverflowError
為止。
在我們的例子中,基本情況是子數組只有一個元素。這是因為取出唯一的數字後子數組為空。
那麼接下來我們來實作一下遞歸方法:
int sumIntArray1(int[] array) {
if (array.length == 1) {
return array[0];
} else {
return array[0] + sumIntArray1(Arrays.copyOfRange(array, 1, array.length));
}
}
正如我們在sumIntArray1()
方法中看到的,我們使用Arrays.copyOfRange()
方法來建立子陣列。
如果我們將範例輸入傳遞給該方法,則遞歸步驟如下所示:
sumIntarray1(array) = array[0] + sumOfArray1(arr1{2, 3, 4, 5})
= 1 + (arr1[0] + sumIntarray1(arr2{3, 4, 5}))
= 1 + (2 + (arr2[0] + sumIntarray1(arr3{4, 5})))
= 1 + (2 + (3 + (arr3[0] + sumIntarray1(arr4{5})))) <-- (arr4.length == 1) Base case reached
= 1 + (2 + (3 + (4 + (5))))
= 15
接下來,讓我們使用INT_ARRAY
測試該方法:
assertEquals(15, sumIntArray1(INT_ARRAY));
3. 不建立數組副本的遞歸
在sumIntArray1()
方法中,我們使用Arrays.copyOfRange()
方法來初始化子陣列。然而,每次呼叫此方法時都會建立一個新數組。如果我們面對一個巨大的整數數組,這種方法會創建許多數組物件。
我們知道我們應該避免創建不必要的物件以獲得更好的效能。那麼,接下來,讓我們看看是否可以改進sumIntArray1()
方法。
這個想法是將所需的索引傳遞到下一個遞歸步驟。然後,我們可以重複使用相同的陣列物件:
int sumIntArray2(int[] array, int lastIdx) {
if (lastIdx == 0) {
return array[lastIdx];
} else {
return array[lastIdx] + sumIntArray2(array, lastIdx - 1);
}
}
如果我們使用INT_ARRAY
輸入測試它,測試就會通過:
assertEquals(15, sumIntArray2(INT_ARRAY, INT_ARRAY.length - 1))
接下來,讓我們來了解sumIntArray2()
方法的工作原理。
此方法採用兩個參數:整數陣列 ( array
) 和我們打算計算總和的最後一個索引 ( lastIdx
) 。這次,遞歸遵循以下規則:
sumOf(array[0..n], n) = array[n] + sumOf(array[0..n], n-1).
正如我們所看到的,我們在每個遞歸步驟中重複使用原始陣列。這種方法的基本情況是當lastIdx
為零時,這表示我們反向(從n ->0
)遍歷整個陣列:
sumIntArray2(array, 4) = array[4] + sumOfArray2(array, 3)
= 5 + (array[3] + sumIntArray2(array, 2))
= 5 + (4 + (array[2] + sumIntArray2(array, 1)))
= 5 + (4 + (3 + (array[1] + sumIntArray2(array, 0))))
= 5 + (4 + (3 + (2 + (array[0])))) <-- (idx == 0) Base case reached
= 5 + (4 + (3 + (2 + (1))))
= 15
最後,我們進行效能比較,看看在給定相同輸入的情況下, sumIntArray2()
是否比sumIntArray1().
4. 對兩種遞歸解決方案進行基準測試
我們將使用 JMH(Java Microbenchmark Harness)對這兩個遞歸解決方案進行基準測試。因此,我們首先創建一個基準類別:
@BenchmarkMode(Mode.AverageTime)
@State(Scope.Thread)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 2)
@Fork(1)
@Measurement(iterations = 5)
public class SumArrayBenchmark {
public static void main(String[] args) throws Exception {
Options options = new OptionsBuilder()
.include(SumArrayBenchmark.class.getSimpleName())
.build();
new Runner(options).run();
}
@Param({ "10", "10000" })
public int size;
int[] array;
@Setup
public void setup() {
var r = new Random();
array = new int[size];
for (int i = 0; i < size; i++) {
array[i] = r.nextInt();
}
}
@Benchmark
public int withArrayCopy() {
return sumIntArray1(array);
}
@Benchmark
public int withoutArrayCopy() {
return sumIntArray2(array, array.length - 1);
}
}
我們的目標是對這兩種解決方案進行基準測試。因此,為簡潔起見,我們不會討論每個 JMH 配置或註解。但是,了解**SumArrayBenchmark
使用兩個不同的輸入陣列執行每個解決方案至關重要:**
- 包含 10 個隨機數的陣列
- 數組由 10000 個隨機整數組成
此外, JMH 對每個解決方案上的每個輸入數組進行五次迭代,確保對其效能進行徹底評估。
接下來,讓我們來看看SumArrayBenchmark
產生的輸出:
Benchmark (size) Mode Cnt Score Error Units
SumArrayBenchmark.withArrayCopy 10 avgt 5 30,576 ± 0,584 ns/op
SumArrayBenchmark.withArrayCopy 10000 avgt 5 7314150,000 ± 82516,421 ns/op
SumArrayBenchmark.withoutArrayCopy 10 avgt 5 6,764 ± 0,032 ns/op
SumArrayBenchmark.withoutArrayCopy 10000 avgt 5 30140,685 ± 91,804 ns/op
如報告所示, withoutArrayCopy()
解決方案比withArrayCopy()
方法快得多:
- 數組[10] ~ 快 5 倍 (30576/6764)
- 數組[10000] ~ 快 242 倍 (7314150/30140)
5. 結論
在本文中,我們探討了兩種對數組中的整數進行遞歸求和的方法。此外,我們還使用 JMH 工具分析了它們的性能。 “withoutArrayCopy”解決方案比“withArrayCopy”方法快得多。
與往常一樣,範例的完整原始程式碼可在 GitHub 上取得。