Kotlin ❤ Sequence than List

剛好有人提到，簡單紀錄一下

還記得 RxJava Observable 也有這樣的能力： Lazy

假設我們有一萬名使用者 List<User> users，其中有五千名女性使用者。

fun getFemaleAgeList(users: List<User>): List<Int> {
  return users
    .filter { it.isFemale() } // 10k 次
    .map { it.age } // 再 5k 次
}

你可以發現原本的寫法有個瑕疵，就是會先繞完一萬使用者，找出來五千名女性後，為了詢問年紀，只好再繞一次這五千名女性。

可以第一次找出女性使用者時，就順便問一下年紀嗎？

fun getFemaleAgeList(users: List<User>): List<Int> {
  return users
    .asSequence() // Lazy
    .filter { it.isFemale() }
    .map { it.age }
    .toList() // 這樣就只會跑一圈 Loop, 總共只會 10k，遍歷同時 filter and map
}

ref. https://yongjhih.gitbooks.io/feed/content/RxJava.html

這也是為什麼當初提到：

RxJava vs. coroutine + Sequence in Kotlin 紙條

想知道為什麼會整整跑完兩個 loop 嗎？

public inline fun <T> Iterable<T>.filter(predicate: (T) -> Boolean): List<T> {
    return filterTo(ArrayList<T>(), predicate)
}
public inline fun <T, C : MutableCollection<in T>> Iterable<T>.filterTo(destination: C, predicate: (T) -> Boolean): C {
    for (element in this) if (predicate(element)) destination.add(element)
    return destination // 繞完第一圈
}
public inline fun <T, R> Iterable<T>.map(transform: (T) -> R): List<R> {
    return mapTo(ArrayList<R>(collectionSizeOrDefault(10)), transform)
}
public inline fun <T, R, C : MutableCollection<in R>> Iterable<T>.mapTo(destination: C, transform: (T) -> R): C {
    for (item in this)
        destination.add(transform(item))
    return destination  // 繞完第二圈
}

那為什麼 Sequence 只要一圈嗎？

簡單的說，就是只是註冊 filter 與 map 掛進 iterator，僅當 iterate 真正取出時，才同時做 filter() 與 map() ：

// 虛擬碼
fun Sequence.toList(): List<T> {
  val list = mutableListOf()
  val iterator = iterator()
  while (iterator.hasNext()) {
    val item = iterator.next()
    if (filter(item)) {
      list.add(map(item))
    }
  }
  return list
}

實際觀察：

public fun <T> Sequence<T>.filter(predicate: (T) -> Boolean): Sequence<T> {
    return FilteringSequence(this, true, predicate)
}
// 將 filter 掛進 iterator
internal class FilteringSequence<T>(
    private val sequence: Sequence<T>,
    private val sendWhen: Boolean = true,
    private val predicate: (T) -> Boolean
) : Sequence<T> {
    override fun iterator(): Iterator<T> = object : Iterator<T> {
        val iterator = sequence.iterator()
        var nextState: Int = -1 // -1 for unknown, 0 for done, 1 for continue
        var nextItem: T? = null
        private fun calcNext() {
            while (iterator.hasNext()) {
                val item = iterator.next()
                // 這裡是 filter
                // 跳過其他的，一直找到下一個是符合 filter 為止
               if (predicate(item) == sendWhen) {
                    nextItem = item
                    nextState = 1
                    return
                }
            }
            nextState = 0
        }
// 這裡是進入點
        override fun next(): T {
            if (nextState == -1)
                calcNext() // 跳過其他的，一直找到下一個是符合 filter 為止
            if (nextState == 0)
                throw NoSuchElementException()
            val result = nextItem
            nextItem = null
            nextState = -1
            @Suppress("UNCHECKED_CAST")
            return result as T
        }
        override fun hasNext(): Boolean {
          ...
        }
    }
}
public fun <T, R> Sequence<T>.map(transform: (T) -> R): Sequence<R> {
    return TransformingSequence(this, transform)
}
// 將 map 掛進 iterator
internal class TransformingSequence<T, R>
constructor(private val sequence: Sequence<T>, private val transformer: (T) -> R) : Sequence<R> {
    override fun iterator(): Iterator<R> = object : Iterator<R> {
        val iterator = sequence.iterator()
        override fun next(): R {
            return transformer(iterator.next()) // 這裡是 map
        }
        ...
    }
    ...
}

以前 Java6 沒有 RxJava 以及 Kotlin Sequence 時，筆者是使用：

RxList/MapList.java at master · yongjhih/RxList