
這篇文章會用 TDD 手刻 myTake、myTakeLast、myDrop、myDropLast,搞懂切片操作的提前終止邏輯,以及從尾巴取資料時的滑動視窗手法
| Kotlin | C# LINQ | 備註 |
|---|---|---|
take(n) |
Take(n) |
|
takeLast(n) |
TakeLast(n) (.NET Core 2.0+) |
C# 給 IEnumerable,Kotlin 只給 List |
drop(n) |
Skip(n) |
命名差異:Kotlin 叫 drop,C# 叫 Skip |
dropLast(n) |
SkipLast(n) (.NET Core 2.0+) |
同上 |
C# 早期只有 Take 和 Skip,從尾巴操作的 TakeLast / SkipLast 是 .NET Core 2.0(.NET Standard 2.1)才補上的。Kotlin 從一開始四個就都有
還有一個容易踩到的雷:n 是負數時,Kotlin 四個函式全部都會拋 IllegalArgumentException,C# 則是一個都不拋,一律把負數當 0 看待,Take / TakeLast 回傳空集合,Skip / SkipLast 則是原封不動把整串還給你。帶著這個習慣寫 Kotlin,會直接吃到例外
take(n) 保留前 n 個,丟掉剩下的。drop(n) 丟掉前 n 個,保留剩下的。兩者剛好互補
val numbers = listOf(1, 2, 3, 4, 5)
numbers.take(3) // [1, 2, 3]
numbers.drop(3) // [4, 5]
// take(3) + drop(3) = 原本的 list
takeLast 和 dropLast 是從尾巴來的版本
numbers.takeLast(2) // [4, 5]
numbers.dropLast(2) // [1, 2, 3]
套到共用的 employees 資料,這四個函式通常拿來處理「目前順序」下的前後段
employees.take(3).map { it.name } // [Alice, Bob, Charlie]
employees.drop(3).map { it.name } // [Diana, Eve, Frank, Grace]
employees.takeLast(2).map { it.name } // [Frank, Grace]
employees.dropLast(2).map { it.name } // [Alice, Bob, Charlie, Diana, Eve]
C# 用 Take/Skip,Kotlin 用 take/drop。drop 來自函式語言,Haskell、Scala、F# 都用這個名字,語意是「把前 n 個丟掉,留下尾巴」。Skip 比較符合命令式直覺(「跳過前 n 個」),意思上隱含「之後還會處理」,跟 LINQ 的 lazy 管道隱喻吻合
兩個動詞各自合理。Kotlin 承襲函式語言的傳統,C# 貼著自己 LINQ 的「資料管道」隱喻
@Test
fun `take first 3 elements`() {
val numbers = listOf(1, 2, 3, 4, 5)
val result = numbers.myTake(3)
assertEquals(listOf(1, 2, 3), result)
}
@Test
fun `take 0 returns empty`() {
val numbers = listOf(1, 2, 3)
val result = numbers.myTake(0)
assertEquals(emptyList<Int>(), result)
}
@Test
fun `take exactly size returns all`() {
val numbers = listOf(1, 2, 3)
val result = numbers.myTake(3)
assertEquals(listOf(1, 2, 3), result)
}
@Test
fun `take more than size returns all`() {
val numbers = listOf(1, 2, 3)
val result = numbers.myTake(10)
assertEquals(listOf(1, 2, 3), result)
}
@Test
fun `take on empty list returns empty`() {
val empty = emptyList<Int>()
val result = empty.myTake(3)
assertEquals(emptyList<Int>(), result)
}
@Test
fun `take negative throws`() {
val numbers = listOf(1, 2, 3)
val exception = assertThrows<IllegalArgumentException> { numbers.myTake(-1) }
assertEquals("Requested element count -1 is less than zero.", exception.message)
}
邊界案例很重要:n = 0 回傳空 List,n 剛好等於 size 和超過 size 都回傳全部,空集合回傳空 List,n 是負數拋 IllegalArgumentException
前置檢查只斷言例外型別是不夠的。錯誤訊息也是 API 的一部分,把 n 的值帶進訊息裡才有除錯價值,所以順手把訊息內容一起驗證
還有兩個行為,用 listOf 是測不出來的。take 的實作會分兩條路走:能事先知道大小的集合走一條,只能從頭疊代的走另一條。全部測試都餵 listOf,等於只走了其中一條。而「拿夠了就停」這件事,光看回傳值也看不出來,得有東西幫我們記帳
class CountingIterable<T>(private val source: List<T>) : Iterable<T> {
var visited = 0
private set
override fun iterator(): Iterator<T> = object : Iterator<T> {
private var index = 0
override fun hasNext(): Boolean = index < source.size
override fun next(): T {
visited++
return source[index++]
}
}
}
它只實作 Iterable,不是 Collection,所以沒有 size 可查;每取走一個元素就把 visited 加一
這個類別純粹是為了寫測試生出來的道具,正式程式碼裡不會這樣搞。平常想知道某段邏輯跑了幾次,在 lambda 裡塞個 count++ 就解決了,day 27 驗證 Sequence 的 lazy 行為用的就是這招;真有效能疑慮也是拿 profiler 去量,不會寫成單元測試。特地包一個類別出來,確實有點 over-design
會走到這一步,是因為這裡要測的不只是次數,還有「receiver 不是 Collection」這個身分。listOf 永遠是 Collection,計數器塞在哪都改變不了這件事,只能自己做一個型別對的來源。多出來的那一層是為了型別,不是為了計數,也只有手刻 stdlib 這種練習題才會這樣子做
@Test
fun `take stops early on non-Collection iterable`() {
val source = CountingIterable((1..1000).toList())
val result = source.myTake(3)
assertEquals(listOf(1, 2, 3), result)
assertEquals(3, source.visited)
}
@Test
fun `take more than size on non-Collection iterable returns all`() {
val source = CountingIterable(listOf(1, 2, 3))
val result = source.myTake(10)
assertEquals(listOf(1, 2, 3), result)
}
第一個測試裡的 assertEquals(3, source.visited) 是重點:一千筆資料只碰了三筆。第二個測試補的是「要的比有的多」在沒有 size 可查時的情況,這時停止條件從頭到尾不會成立,迴圈得自己走到底
fun <T> Iterable<T>.myTake(n: Int): List<T> {
require(n >= 0) { "Requested element count $n is less than zero." }
if (n == 0) {
return emptyList()
}
if (this is Collection && n >= size) {
return toList()
}
val result = ArrayList<T>()
var count = 0
for (element in this) {
result.add(element)
count++
if (count == n) {
break
}
}
return result
}
require(n >= 0) 是 Kotlin 的前置條件檢查函式。條件不成立就拋 IllegalArgumentException,比手寫 if-throw 乾淨
this is Collection 的型別檢查讓我們在集合大小已知時直接判斷 n 是否超過 size,省去不必要的迴圈
迴圈裡的 break 是 take 的特色:拿夠了就停,不需要跑完整個集合。如果集合有一百萬筆資料但只要前 10 筆,跑 10 次就結束。前面 CountingIterable 量到的 visited == 3 就是這件事的證據。這個特性在 day 27 的 Sequence 會變得更有意義
目前的實作邏輯已經正確,但 ArrayList<T>() 沒有預先指定容量。我們知道最多只會放 n 個元素,可以一開始就把容量開好,避免迴圈過程中陣列擴容
fun <T> Iterable<T>.myTake(n: Int): List<T> {
require(n >= 0) { "Requested element count $n is less than zero." }
if (n == 0) {
return emptyList()
}
if (this is Collection && n >= size) {
return toList()
}
val result = ArrayList<T>(n) // 預先指定容量
var count = 0
for (element in this) {
result.add(element)
count++
if (count == n) {
break
}
}
return result
}
這一步跟 stdlib 的距離又近了一點,完整的比對留到後面的「與 stdlib 原始碼比較」一節
@Test
fun `takeLast 3 elements`() {
val numbers = listOf(1, 2, 3, 4, 5)
val result = numbers.myTakeLast(3)
assertEquals(listOf(3, 4, 5), result)
}
@Test
fun `takeLast 0 returns empty`() {
val numbers = listOf(1, 2, 3)
val result = numbers.myTakeLast(0)
assertEquals(emptyList<Int>(), result)
}
@Test
fun `takeLast exactly size returns all`() {
val numbers = listOf(1, 2, 3)
val result = numbers.myTakeLast(3)
assertEquals(listOf(1, 2, 3), result)
}
@Test
fun `takeLast more than size returns all`() {
val numbers = listOf(1, 2, 3)
val result = numbers.myTakeLast(10)
assertEquals(listOf(1, 2, 3), result)
}
@Test
fun `takeLast on empty list returns empty`() {
val empty = emptyList<Int>()
val result = empty.myTakeLast(3)
assertEquals(emptyList<Int>(), result)
}
@Test
fun `takeLast negative throws`() {
val numbers = listOf(1, 2, 3)
val exception = assertThrows<IllegalArgumentException> { numbers.myTakeLast(-1) }
assertEquals("Requested element count -1 is less than zero.", exception.message)
}
@Test
fun `takeLast result is independent of source`() {
val source = mutableListOf(1, 2, 3, 4, 5)
val result = source.myTakeLast(2)
source.clear()
assertEquals(listOf(4, 5), result)
}
@Test
fun `takeLast on non-Collection iterable`() {
val source = CountingIterable(listOf(1, 2, 3, 4, 5))
val result = source.myTakeLast(2)
assertEquals(listOf(4, 5), result)
assertEquals(5, source.visited)
}
@Test
fun `takeLast more than size on non-Collection iterable returns all`() {
val source = CountingIterable(listOf(1, 2, 3))
val result = source.myTakeLast(10)
assertEquals(listOf(1, 2, 3), result)
}
前面幾個測試照著 take 那組改。真正決定實作長相的是後面三個
takeLast result is independent of source 要求回傳值跟來源脫鉤:把來源清空之後,結果還是得完好。takeLast on non-Collection iterable 則要求連不知道自己有多長的序列也能從尾巴取,而且 visited == 5 說明這件事沒有捷徑,全部五筆都得經手。最後一個補的是「要的比有的多」,這時緩衝從頭到尾沒滿過
fun <T> Iterable<T>.myTakeLast(n: Int): List<T> {
require(n >= 0) { "Requested element count $n is less than zero." }
if (n == 0) {
return emptyList()
}
val buffer = ArrayDeque<T>(n)
for (element in this) {
if (buffer.size == n) {
buffer.removeFirst()
}
buffer.addLast(element)
}
return buffer.toList()
}
receiver 是 Iterable<T>,跟 take 一樣。既然事先不知道序列有多長,也就算不出尾端從哪裡開始,那就換個思路:一邊走一邊只留住「最後看到的 n 個」。這個手法叫滑動視窗(sliding window)
ArrayDeque 是 Kotlin 1.4 加進 stdlib 的雙端佇列,兩端的進出都是攤還 O(1)。緩衝滿了就從頭擠掉一個,再從尾巴補上新的,走完序列時留在裡面的正好是最後 n 個
這裡用的是 kotlin.collections.ArrayDeque,它在預設 import 裡。如果你的檔案有 import java.util.*,拿到的會是 java.util.ArrayDeque,行為雖然一樣,但那個不是 MutableList
這個寫法的記憶體只跟 n 有關,跟來源多長無關。一千萬筆資料取最後 3 筆,緩衝從頭到尾只佔 3 個位置。代價是整個序列一定要走完,這點跟 drop 一樣,沒有提前終止的餘地
C# 的 TakeLast 走的正是這條路。它的簽章是 IEnumerable<TSource> 的擴充,內部拿一個佇列滾,跟我們這版是同一個構想
Iterable 版本能用在任何序列上,但它對 List 這種已經知道自己有多長的集合來說是虧的:明明可以直接算出起點跳過去,卻還在滾緩衝
補一個 List 版本
fun <T> List<T>.myTakeLast(n: Int): List<T> {
require(n >= 0) { "Requested element count $n is less than zero." }
if (n == 0) return emptyList()
if (n >= size) return toList()
return subList(size - n, size).toList()
}
size 已知,起點就是 size - n,subList 直接框出尾端區間,不需要任何緩衝。subList 拿到的是原 List 的 view,toList() 複製一份出來,這正是前面那個 independent of source 測試要的
兩個版本同名同參數,可以並存嗎?可以。擴充函式的多載解析看的是編譯期的靜態型別,而且會挑最具體的那個 receiver。變數宣告成 List<Int> 就走 List 版,宣告成 Iterable<Int> 就走 Iterable 版,即使執行期裝的是同一個 ArrayList
stdlib 自己也有這樣一對,last() 就同時有 Iterable 和 List 兩個版本,List 版直接取 lastIndex。不過它多做了一件我們沒做的事:Iterable 版裡面還藏了一道執行期的 is List 檢查,靜態型別挑錯了照樣救得回來(day 06 手刻 myLast 時寫的就是這道檢查)。我們這兩個 myTakeLast 沒有這層保險,宣告成 Iterable 就真的去滾緩衝
補上 List 版之後,Red 階段那幾個用 listOf 寫的測試就全部改走 List 版了,Iterable 版從此只剩 CountingIterable 那兩個測試在守。剛講的「靜態型別決定走哪個」,活例子就在自己的測試檔案裡
stdlib 選的是 List 這條路,而且比我們更講究:先處理 n 為 0、n 大於等於 size、n 等於 1 的快速路徑,接著開一個容量 n 的 ArrayList,receiver 是 RandomAccess 就用 index 迴圈從 size - n 複製到尾,不是的話改用 listIterator(size - n) 走訪複製。我們用 subList 拿 view 再複製比較省事,結果相同
stdlib 沒有 Iterable 版本的 takeLast,Sequence 也沒有。要對一般序列從尾巴取,得自己寫,或先 toList() 再取。C# 把 TakeLast 給了 IEnumerable,Kotlin 只給 List,兩邊在這裡做了不一樣的選擇
@Test
fun `drop first 2 elements`() {
val numbers = listOf(1, 2, 3, 4, 5)
val result = numbers.myDrop(2)
assertEquals(listOf(3, 4, 5), result)
}
@Test
fun `drop 0 returns all`() {
val numbers = listOf(1, 2, 3)
val result = numbers.myDrop(0)
assertEquals(listOf(1, 2, 3), result)
}
@Test
fun `drop exactly size returns empty`() {
val numbers = listOf(1, 2, 3)
val result = numbers.myDrop(3)
assertEquals(emptyList<Int>(), result)
}
@Test
fun `drop more than size returns empty`() {
val numbers = listOf(1, 2, 3)
val result = numbers.myDrop(10)
assertEquals(emptyList<Int>(), result)
}
@Test
fun `drop on empty list returns empty`() {
val empty = emptyList<Int>()
val result = empty.myDrop(3)
assertEquals(emptyList<Int>(), result)
}
@Test
fun `drop negative throws`() {
val numbers = listOf(1, 2, 3)
val exception = assertThrows<IllegalArgumentException> { numbers.myDrop(-1) }
assertEquals("Requested element count -1 is less than zero.", exception.message)
}
@Test
fun `drop visits every element on non-Collection iterable`() {
val source = CountingIterable(listOf(1, 2, 3, 4, 5))
val result = source.myDrop(2)
assertEquals(listOf(3, 4, 5), result)
assertEquals(5, source.visited)
}
最後一個測試把 CountingIterable 拿來用在相反的方向。take 那邊量到的是「只碰三筆就收手」,drop 這邊量到的是「五筆全碰過」。同一個工具,測出來的是兩個函式在效能上的根本差別
fun <T> Iterable<T>.myDrop(n: Int): List<T> {
require(n >= 0) { "Requested element count $n is less than zero." }
if (n == 0) {
return toList()
}
val result = ArrayList<T>()
var count = 0
for (element in this) {
if (count >= n) {
result.add(element)
}
count++
}
return result
}
跟 take 相反:前 n 個跳過,之後的才加進結果。但有個差異:drop 沒辦法提前終止,必須跑完整個集合才能收集完剩餘元素
目前用「疊代時計數 count,超過 n 才加入」的寫法可讀,但當 receiver 有已知大小時有更直接的做法。stdlib 的 drop 一樣只定義在 Iterable<T> 上,型別判斷全在它內部:如果是 Collection 就知道結果大小是 size - n,可以先把 ArrayList 容量開好;起點也不用逐一數,是 List 的話再看它是不是 RandomAccess,是就從 index n 開始迴圈複製,不是就用 listIterator(n) 跳到位置再複製;至於是 Collection 但不是 List 的(例如 Set),還是得逐一數過去,只是容量先開好了。另一種可行做法是用 subList(n, size) 拿 view 再複製,只是 stdlib 沒選這條
把「能不能提前知道大小」這個分支邏輯留到後面的「Iterable vs List」一節再談
@Test
fun `dropLast 2 elements`() {
val numbers = listOf(1, 2, 3, 4, 5)
val result = numbers.myDropLast(2)
assertEquals(listOf(1, 2, 3), result)
}
@Test
fun `dropLast 0 returns all`() {
val numbers = listOf(1, 2, 3)
val result = numbers.myDropLast(0)
assertEquals(listOf(1, 2, 3), result)
}
@Test
fun `dropLast exactly size returns empty`() {
val numbers = listOf(1, 2, 3)
val result = numbers.myDropLast(3)
assertEquals(emptyList<Int>(), result)
}
@Test
fun `dropLast more than size returns empty`() {
val numbers = listOf(1, 2, 3)
val result = numbers.myDropLast(10)
assertEquals(emptyList<Int>(), result)
}
@Test
fun `dropLast on empty list returns empty`() {
val empty = emptyList<Int>()
val result = empty.myDropLast(3)
assertEquals(emptyList<Int>(), result)
}
@Test
fun `dropLast negative throws`() {
val numbers = listOf(1, 2, 3)
val exception = assertThrows<IllegalArgumentException> { numbers.myDropLast(-1) }
assertEquals("Requested element count -1 is less than zero.", exception.message)
}
@Test
fun `dropLast on non-Collection iterable`() {
val source = CountingIterable(listOf(1, 2, 3, 4, 5))
val result = source.myDropLast(2)
assertEquals(listOf(1, 2, 3), result)
assertEquals(5, source.visited)
}
@Test
fun `dropLast more than size on non-Collection iterable returns empty`() {
val source = CountingIterable(listOf(1, 2, 3))
val result = source.myDropLast(10)
assertEquals(emptyList<Int>(), result)
}
dropLast exactly size 和 dropLast more than size 的結果都是空 List,但要分開測:一個是「剛好要丟掉全部」,一個是「要丟的比有的還多」。實作換了寫法之後,這兩種情況常常走的不是同一條路
fun <T> Iterable<T>.myDropLast(n: Int): List<T> {
require(n >= 0) { "Requested element count $n is less than zero." }
if (n == 0) {
return toList()
}
val result = ArrayList<T>()
val buffer = ArrayDeque<T>(n)
for (element in this) {
if (buffer.size == n) {
result.add(buffer.removeFirst())
}
buffer.addLast(element)
}
return result
}
把它跟 myTakeLast 擺在一起看,會發現是同一個迴圈
// myTakeLast:擠出去的丟掉,最後回傳留在緩衝裡的
if (buffer.size == n) buffer.removeFirst()
buffer.addLast(element)
return buffer.toList()
// myDropLast:擠出去的收進結果,緩衝裡剩下的丟掉
if (buffer.size == n) result.add(buffer.removeFirst())
buffer.addLast(element)
return result
同一個 n 大小的緩衝滾過整個序列,takeLast 要的是最後留在裡面的,dropLast 要的是被擠出來的。兩個函式互補,緩衝的兩邊剛好各給一個
為什麼被擠出來的就一定是答案?因為一個元素會被擠出緩衝,代表它後面至少還有 n 個元素排隊。既然它離結尾還有 n 個以上的距離,就輪不到被丟掉。反過來,走完序列還留在緩衝裡的那 n 個,正是最靠近尾巴的 n 個
n == 0 那行 early return 不能拿掉。少了它,第一輪的 buffer.size == n 立刻成立(兩邊都是 0),程式會對空的緩衝呼叫 removeFirst(),直接吃到 NoSuchElementException。myTakeLast 的 n == 0 也是同樣的道理,不是為了少跑幾行才寫的
跟 takeLast 一樣,List 有捷徑可走
fun <T> List<T>.myDropLast(n: Int): List<T> {
require(n >= 0) { "Requested element count $n is less than zero." }
return take((size - n).coerceAtLeast(0))
}
dropLast(n) 就是「留下前 size - n 個」,size 已知的話,一行委派給 take 就結束了(這裡的 take 是 stdlib 的,換成前面手刻的 myTake 也一樣)。n 超過 size 時 size - n 會變負數,coerceAtLeast(0) 夾成 0,take(0) 自然回傳空 List。這就是前面說「兩種情況走的不是同一條路」的意思:在緩衝版是「滿了沒有」的差別,在 List 版是「要不要夾負數」的差別
stdlib 的 dropLast 也是 take(size - n),同樣有夾住負數的處理,沒有再用 subList。原因是 take 本身就會把前面那段複製成新 List,再走一次 subList 沒有好處。跟 takeLast 一樣,stdlib 沒有提供 Iterable 版本
四個函式的 Iterable 版都寫完了,其中兩個還多寫了 List 版。同樣一件事給了兩種寫法,差別到底在哪?
| 函式 | Iterable 版本的走訪成本 |
知道 size 就能省掉 |
|---|---|---|
take(n) |
走 n 個就停 | n 超過 size 時直接複製全部 |
takeLast(n) |
走完全部,外加 n 大小的緩衝 | 跳到 size - n,不用緩衝 |
drop(n) |
走完全部 | 先開好結果容量,跳到第 n 個 |
dropLast(n) |
走完全部,外加 n 大小的緩衝 | 委派 take(size - n) |
四個裡面只有 take 有機會不走完序列,這個優勢到 day 27 的 Sequence 會放大。另外三個不管知不知道 size,資料都得跑過一遍
緩衝則是尾端操作獨有的成本。takeLast 和 dropLast 在不知道 size 時得額外拿 n 個位置記帳,take 和 drop 不用;size 已知的話這筆開銷完全省得掉,因為起點算得出來
要注意知道 size 省下的是常數,不是複雜度。List 版本的 takeLast 一樣要複製 n 個元素出來,只是不必為了找到起點而走完前面那段。RandomAccess 的 ArrayList 定位是 O(1),但 List 這個介面本身不保證,LinkedList 就得一步步走過去,stdlib 因此會先檢查 receiver 是不是 RandomAccess 再決定走法
stdlib 的取捨是:take 和 drop 給 Iterable,takeLast 和 dropLast 只給 List。看起來的理由是與其提供一個對誰都能用但對誰都不夠快的版本,不如只在划算的型別上開放,剩下的情況要求呼叫端先 toList()。C# 選了另一邊,TakeLast 對 IEnumerable 全面開放,代價就是我們手刻的那個緩衝
原始碼位置:kotlin.collections 的 _Collections.kt
takeLast 和 dropLast 的比對在各自的 Refactor 已經談過,這裡補上 take。跟我們的版本比,它還多做了兩件事
public fun <T> Iterable<T>.take(n: Int): List<T> {
require(n >= 0) { "Requested element count $n is less than zero." }
if (n == 0) return emptyList()
if (this is Collection) {
if (n >= size) return toList()
if (n == 1) return listOf(first())
}
var count = 0
val list = ArrayList<T>(n)
for (item in this) {
list.add(item)
if (++count == n)
break
}
return list.optimizeReadOnlyList()
}
預先指定容量那點我們在 Refactor 已經跟上了,剩下兩個差異。第一,n == 1 的時候直接回傳 listOf(first()),省去建立 ArrayList 的開銷。第二,最後呼叫 optimizeReadOnlyList() 收尾
optimizeReadOnlyList() 是 stdlib 的內部函式,它只做大小判斷、不包 wrapper:size 為 0 時回傳 emptyList(),size 為 1 時回傳 listOf(this[0]),其餘情況直接回傳原本那個 list(else -> this)。0 和 1 兩種情況換成更輕量的單例或單元素實作,省下 ArrayList 的記憶體開銷
切片操作看起來單純,動手寫才會發現差別藏在「知不知道長度」。從頭取的 take、drop 對 Iterable 就夠用;從尾取的 takeLast、dropLast 在不知道 size 的情況下,得靠一個 n 大小的緩衝滾完整個序列才有答案。同一個緩衝,留在裡面的是 takeLast,被擠出來的是 dropLast
stdlib 選擇只把尾端操作開放給 List,不提供 Iterable 版本。要對一般序列從尾巴取,得自己寫或先 toList()
下一篇是條件版的切片:takeWhile 和 dropWhile。不是取「幾個」,是取「直到條件不滿足為止」
同步刊登於 Blog
圖片來源:AI 產生