Tembel Diziler

Önceki ders her dönüşümün bir koleksiyon aldığını ve yeni bir koleksiyon verdiğini gösterdi. map dört elemanlı listeden dört elemanlı liste kurar, filter bu listeden bir üçüncüsünü kurar; zincirde her adım kendi ara listesini bırakır. Çoğu zaman bu sorun olmaz. Ama kaynak çok büyükse, sonsuzsa ya da yalnızca ilk eşleşen eleman isteniyorsa, her adımın tüm elemanları işlemesi gereksiz iş demektir.

Kotlin bu durum için tembel dizi (Sequence) sunar. Tembel dizi elemanları saklayan bir kap değil, elemanları sırayla üretme tarifidir. Üzerine eklenen map, filter gibi ara işlemler bir şey hesaplamaz; yalnızca tarife bir adım ekleyip yeni bir tembel dizi döndürür. Hesabı başlatan, sonucu çıkaran işlemlere uç işlem denir: toList, first, count ve benzerleri. Uç işlem gelince elemanlar zincirden bir bir geçer: ilk eleman bütün ara işlemlerden geçip sonuca ulaşır, ancak ondan sonra ikinci eleman başlar. Tembellik burada bir ölçü ekseni değildir, yalnız davranışı açıklayan bir özelliktir: değerin ne zaman hesaplandığını soran kategori bu kursta kullanılmaz. Ölçü sorusu önceki derslerdeki gibi kalır: bu iki değeri eşit yapan ne?

Dikkat edilecek bir ad çakışması vardır. Kotlin’de dizi (Array, IntArray) elemanları ardışık bellekte tutan sabit boyutlu bir yapıdır. Tembel dizi ise Sequence arayüzüdür ve aynı adı taşımaz; bu derste “dizi” dendiğinde her zaman Sequence kastedilir ve ayrım gereken yerde “tembel dizi” yazılır. Dört ölçüt, Criterion ve summarize önceki derslerdeki gibidir.

// Criterion.kt — iki degeri esit yapan olcutu siniflandirir
class Criterion(val label: String, first: Any?, twin: Any?, other: Any?) {
    val sameObject = first === twin
    val equalTwin = first == twin
    val equalOther = first == other

    val name: String = when {
        sameObject -> "tekil"
        !equalTwin -> "kimlik"
        !equalOther -> "icerik"
        else -> "kismi-icerik"
    }

    fun report() {
        println("$label: ayni-nesne=$sameObject, ikiz=$equalTwin, farkli=$equalOther -> $name")
    }
}

fun summarize(checks: List<Criterion>) {
    for (name in listOf("tekil", "kimlik", "icerik", "kismi-icerik")) {
        println("$name: ${checks.count { it.name == name }}")
    }
}

Liste Hemen, Tembel Dizi Parça Parça

Fark en açık yan etkiyle görünür. Aşağıdaki blok aynı iki işlemi aynı dört elemana önce tembel diziyle, sonra listeyle uygular. Her lambda bir kaydı log’a ekler, böylece hangi adımın ne zaman koştuğu sonradan okunur. Tembel dizi için sırayla üç şey sorulur: zincir kurulduktan hemen sonra kaç kayıt var, first() ne döndürüyor ve kayıtlar hangi sırada. Liste için ise yalnız kayıt sayısı ve ilk eleman sorulur.

// Main.kt — liste hemen, tembel dizi parca parca isler
fun main() {
    val log = mutableListOf<String>()
    val lazy = sequenceOf(1, 2, 3, 4)
        .map { log.add("map$it"); it * 2 }
        .filter { log.add("filter$it"); it > 2 }
    println(log.size)
    println(lazy.first())
    println(log)

    val eagerLog = mutableListOf<String>()
    val eager = listOf(1, 2, 3, 4)
        .map { eagerLog.add("map$it"); it * 2 }
        .filter { eagerLog.add("filter$it"); it > 2 }
    println(eagerLog.size)
    println(eager.first())
}

0
4
[map1, filter2, map2, filter4]
8
4

Birinci satır, zincir kurulduğunda tembel dizide hiçbir lambdanın koşmadığını gösterir: ara işlemler tarife eklendi, hesap başlamadı. İkinci satırda first() uç işlem olarak çalıştı ve 4 döndürdü. Üçüncü satır neyin çalıştığını söyler. İlk eleman 1, map1 ile 2 oldu, filter2 onu eledi (2 > 2 doğru değil). İkinci eleman 2, map2 ile 4 oldu, filter4 onu geçirdi ve first() ilk eşleşmeyi bulunca durdu. 3 ve 4 elemanları hiç işlenmedi. Toplam dört kayıt tutuldu.

Listede aynı zincir sekiz kayıt bıraktı: dört map, dört filter. Beşinci satırdaki 4 aynı sonucu verir, ama önce dört eleman da eşlendi, sonra dört eleman da süzüldü ve yalnız ardından first() çağrıldı. Aradaki fark sonucun değil, işin farkıdır. Sonuç aynı çıkar; tembel dizi gereksiz elemanı işlemez, ara liste kurmaz. Bu, yan etkisi olan lambdalarda kayıt sırasını da değiştirir: listede önce bütün map’ler, sonra bütün filter’lar koşar; tembel dizide her eleman kendi zincirini tamamlar.

KE13. Bu ölçümler dört elemanlı bir Int kaynağı ve yan etkili lambdalar için. Yan etkisiz saf lambdalarla zincirin kaç elemanı işlediği ve kaynağın büyüklüğüyle iş miktarının nasıl değiştiği ölçülmedi.

Sonsuz Kaynak ve Kaynak Türleri

Tembel dizi elemanları baştan saklamadığı için kaynağı sonsuz olabilir. generateSequence(1) { it * 2 } ilk eleman olarak 1 verir, sonrakini bir önceki elemandan üretir ve hiç bitmez. Sonlu bir sonuç almak için zincire take ya da takeWhile gibi sınırlayıcı bir işlem eklenir. sequence { ... } kurucusu ise içinde yield çağıran bir blok alır: her yield bir eleman üretir ve blok bir sonraki elemanın istenmesine kadar durur. Bir listeden tembel diziye geçmek için asSequence() kullanılır. Son iki ölçüm, aynı tembel dizinin iki kez toList() ile toplanabildiğini gösterir.

// Main.kt — sonsuz kaynak ve kaynak turleri
fun main() {
    println(generateSequence(1) { it * 2 }.take(6).toList())
    println(generateSequence(1) { it + 1 }.map { it * it }.takeWhile { it < 50 }.toList())
    println(listOf(3, 8, 11).asSequence().filter { it > 5 }.count())
    val squares = sequence {
        var n = 1
        while (true) {
            yield(n * n)
            n++
        }
    }
    println(squares.drop(2).take(3).toList())
    val twice = sequenceOf(1, 2, 3).map { it + 1 }
    println(twice.toList())
    println(twice.toList())
}

[1, 2, 4, 8, 16, 32]
[1, 4, 9, 16, 25, 36, 49]
2
[9, 16, 25]
[2, 3, 4]
[2, 3, 4]

İlk satır ikinin kuvvetlerinden altı eleman alır. İkinci satır doğal sayıların karelerini üretir ve elli ya da daha büyük karede durur; son eleman 49’dur. Üçüncü satırda liste tembel diziye çevrilir, süzülür ve sayılır: 8 ve 11 beşten büyüktür, sonuç 2. Dördüncü satır sequence { } ile yazılmış sonsuz bir kare üreticisinden ilk iki elemanı atar (1 ve 4) ve sonraki üçünü alır. Son iki satır aynı tembel dizinin iki kez toplandığını ve iki kez aynı sonucu verdiğini gösterir. sequenceOf ile kurulmuş bir dizi birden çok kez dolaşılabilir; her uç işlem tarifi baştan işletir. Bu her tembel diziye genellenemez, ama bu dersin kaynakları için doğrudur.

Burada bir sınır da var: sonsuz kaynakta sınırlayıcı işlem unutulursa program bitmez. take ya da takeWhile gibi bir işlem olmadan toList() çağırmak, sonsuz bir koleksiyonu belleğe sığdırmaya çalışır. Tembel dizi sonsuzluğu mümkün kılar, ama sonlu bir sonucu kurma sorumluluğunu çağırana bırakır.

KE14. Bu ölçümler generateSequence, sequence, sequenceOf ve asSequence kaynakları için. generateSequence’in tohumsuz biçimi gibi yalnız bir kez dolaşılabilen kaynakların ikinci dolaşımda ne yaptığı ve sınırlayıcı işlemsiz sonsuz kaynağın sonucu ayrıca ölçülmedi.

Ölçüt: Kimlik

Tembel diziler kendi içeriklerini saklamaz, tarif taşır. Bu yüzden iki tembel dizinin eşitliği sorusu, iki listeninkinden farklı bir cevap verir. Aşağıdaki blok iki ayrı sequenceOf(1, 2) kurar, ikisini == ile karşılaştırır ve Criterion ile adlandırır. other yalnız ikinci elemanı farklı bir tembel dizidir. İkinci ölçümde tembel diziler aynı listeden asSequence() ile iki kez kurulur: kaynak aynı liste olsa bile her çağrı yeni bir tembel dizi döndürür.

// Main.kt — iki tembel dizi
fun main() {
    val list = listOf(1, 2)
    val checks = listOf(
        Criterion("sequenceOf", sequenceOf(1, 2), sequenceOf(1, 2), sequenceOf(1, 3)),
        Criterion("asSequence", list.asSequence(), list.asSequence(), sequenceOf(1, 3)),
    )
    for (check in checks) check.report()
    summarize(checks)
}

sequenceOf: ayni-nesne=false, ikiz=false, farkli=false -> kimlik
asSequence: ayni-nesne=false, ikiz=false, farkli=false -> kimlik
tekil: 0
kimlik: 2
icerik: 0
kismi-icerik: 0

İki ölçüm de kimlik çıktı. İkizler ayrı nesnelerdir ve eşit değildir; yani iki sequenceOf(1, 2) aynı elemanları üretecek olsa da == ile karşılaştırınca false verir. Bunun nedeni Sequence’in equals’ı tanımlamamasıdır: eşitlik varsayılan davranışa, yani kimliğe düşer. Bu dersin ölçütü budur: kimlik. other ölçümü burada bir şey anlatmaz: ikiz zaten eşit çıkmadığı için ölçüt farkli değerine bakmadan kimlik olur. İkinci ölçüm daha öğreticidir: aynı list değişkeninden iki kez kurulan tembel diziler bile eşit çıkmaz, çünkü eşitlik kaynağın aynı olmasını aramaz.

KE15. Bu ölçümler sequenceOf ve asSequence ile kurulan tembel diziler için. Ara işlemlerle türetilmiş tembel dizilerin (map, filter sonuçları) kendi aralarındaki eşitliği ve generateSequence sonucunun eşitliği ayrıca ölçülmedi.

Sınırlayıcı Ölçüm

Peki iki tembel diziyi karşılaştırmanın bir yolu var mı? Var, ama karşılaştırma tembel dizi üzerinde değil, toplanmış hâl üzerinde yapılır. toList() tembel diziyi tüketir ve bir liste kurar; liste tipi equals’ı içeriğe göre tanımladığı için sonuç değişir. Aşağıdaki blok aynı iki tembel diziyi üç biçimde ölçer: olduğu gibi, toList() ile ve toSet() ile. Kümeli ölçümde other aynı elemanları ters sırada veren bir tembel dizidir.

// Main.kt — toplaninca icerik
fun main() {
    val checks = listOf(
        Criterion("tembel", sequenceOf(1, 2), sequenceOf(1, 2), sequenceOf(1, 3)),
        Criterion("toplanmis", sequenceOf(1, 2).toList(), sequenceOf(1, 2).toList(), sequenceOf(1, 3).toList()),
        Criterion("kume", sequenceOf(1, 2).toSet(), sequenceOf(1, 2).toSet(), sequenceOf(2, 1).toSet()),
    )
    for (check in checks) check.report()
    summarize(checks)
}

tembel: ayni-nesne=false, ikiz=false, farkli=false -> kimlik
toplanmis: ayni-nesne=false, ikiz=true, farkli=false -> icerik
kume: ayni-nesne=false, ikiz=true, farkli=true -> kismi-icerik
tekil: 0
kimlik: 1
icerik: 1
kismi-icerik: 1

Sınırlayıcı ölçüm şudur: eşitliği değer değil, değerin tutulduğu tip verir. Aynı elemanlar tembel dizide kimlik, listede icerik, kümede kismi-icerik ölçütünü verir. Üçünde de elemanlar 1 ve 2 iken ölçütü değiştiren tek şey kabın tipidir. İlk satır önceki ölçümün tekrarıdır. İkinci satır toList() sonrasında ikizin eşit, farklı olanın eşit olmadığını gösterir. Üçüncü satır kümede sıranın fark yaratmadığını gösterir: other ters sırada olsa da eşit çıkar. Böylece ilk iki dersin ölçütleri bu derste yan yana görünür.

Pratik çıkarım şudur: iki tembel diziyi karşılaştırmak gerekiyorsa karşılaştırma öncesinde uygun bir koleksiyona toplanır. Hangi koleksiyona toplanacağı, hangi eşitliğin istendiğine bağlıdır: sıra önemliyse toList(), önemli değilse toSet(). Ayrıca toplama tembel diziyi tüketir; sonsuz bir tembel diziyi toplamadan önce sınırlamak gerekir.

KE16. Bu ölçümler Int elemanlı iki elemanlı tembel diziler için. Elemanları kendi eşitliğini tanımlamayan sınıflar olan tembel dizilerin toplanmış hâllerinin eşitliği ayrıca ölçülmedi.

İşlem Sırası Sonucu Değiştirir

Tembel dizide ara işlemlerin sırası yalnız işi değil, bazen sonucu da değiştirir. filter ve take ikilisi bunun en açık örneğidir. filter { it % 2 == 0 }.take(2) önce çift elemanları süzer, sonra ilk ikisini alır. take(2).filter { it % 2 == 0 } ise önce ilk iki elemanı alır, sonra yalnız onları süzer. Aşağıdaki blok altı elemanlı bir kaynağa iki sırayı da uygular ve her filter çağrısını kaydeder. Kayıtlar filter’a giren elemanları sırayla gösterir.

// Main.kt — filter ve take sirasi
fun main() {
    val firstLog = mutableListOf<Int>()
    val filterFirst = sequenceOf(1, 2, 3, 4, 5, 6)
        .filter { firstLog.add(it); it % 2 == 0 }
        .take(2)
        .toList()
    println(filterFirst)
    println(firstLog)

    val secondLog = mutableListOf<Int>()
    val takeFirst = sequenceOf(1, 2, 3, 4, 5, 6)
        .take(2)
        .filter { secondLog.add(it); it % 2 == 0 }
        .toList()
    println(takeFirst)
    println(secondLog)
}

[2, 4]
[1, 2, 3, 4]
[2]
[1, 2]

Önce süzüp sonra alan zincir iki çift sayı bulana kadar dolaştı: filter dört elemanı gördü ve [2, 4] verdi. Önce alıp sonra süzen zincirde filter yalnız ilk iki elemanı gördü ve tek eleman, [2], kaldı. İki zincir aynı işlemlerden kuruldu; sonuçları farklıdır. Bu, ara işlemlerin birbirinin yerine geçebilir sayılmaması gerektiğini söyler.

KE17. Bu ölçümler filter ve take ikilisi için. map ile take sırasının, drop ve takeWhile gibi diğer sınırlayıcıların kayıt sıraları ayrıca ölçülmedi.

Sıralama Tembelliği Bozar

Her ara işlem elemanı tek tek geçirmez. sorted() bir tembel diziyi sıralamak için bütün elemanları görmek zorundadır: ilk sonuç elemanı ancak en küçüğü bulduktan sonra bilinir. Bu yüzden zincire sorted() girince, kalan işlemler tembel olsa bile, kaynak baştan sona dolaşılır. Ölçüm bunu onEach ile görünür kılar; onEach her elemanı geçirirken bir kayıt bırakır. İlk zincirde sorted() vardır, ikincisinde yoktur ve ikisi de first() ile biter.

// Main.kt — sorted tum elemanlari ister
fun main() {
    val sortedLog = mutableListOf<Int>()
    val smallest = sequenceOf(3, 1, 2, 5, 4)
        .onEach { sortedLog.add(it) }
        .sorted()
        .first()
    println(smallest)
    println(sortedLog)

    val plainLog = mutableListOf<Int>()
    val head = sequenceOf(3, 1, 2, 5, 4)
        .onEach { plainLog.add(it) }
        .first()
    println(head)
    println(plainLog)
}

1
[3, 1, 2, 5, 4]
3
[3]

sorted() olan zincir en küçük sayıyı, 1’i buldu, ama bunun için beş elemanın hepsini gördü. Kayıt kaynağın tam sırasıdır. sorted() olmayan zincir ilk elemanı, 3’ü aldı ve durdu; kayıtta yalnız o var. Kural budur: tembel dizinin kazancı, zincirdeki hiçbir adımın bütün elemanları beklememesine bağlıdır. sorted, sortedBy ve sortedDescending gibi işlemler bu zinciri keser. Sınırlayıcı bir işlem varsa onu sıralamadan önce koymak, sıralanacak elemanları azaltır.

KE18. Bu ölçümler sorted() ve first() için. sortedBy, sortedDescending ve distinct gibi diğer işlemlerin kaç elemanı beklediği ayrıca ölçülmedi.

Tek Dolaşımlık Dizi

Önceki bölümde sequenceOf ile kurulan dizinin iki kez toplanabildiği görüldü. Bu her tembel dizi için geçerli değildir. Bir Iterator’dan asSequence() ile kurulan dizi, yineleyicinin elemanlarını yalnız bir kez verebilir; ikinci dolaşımda aynı yineleyici zaten tükenmiştir. Kotlin bu dizileri tek dolaşımlık sayar ve ikinci uç işlemde IllegalStateException fırlatır. Hata, dizi iki yerde kullanıldığında ortaya çıkar; zinciri kuran kodda görünmez.

// Main.kt — tek dolasimlik dizi
fun main() {
    val once = listOf(1, 2, 3).iterator().asSequence()
    println(once.toList())
    try {
        println(once.toList())
    } catch (e: IllegalStateException) {
        println(e::class.simpleName)
    }
    val again = listOf(1, 2, 3).asSequence()
    println(again.toList())
    println(again.toList())
}

[1, 2, 3]
IllegalStateException
[1, 2, 3]
[1, 2, 3]

İlk toplama [1, 2, 3] verdi. İkinci toplama IllegalStateException fırlattı ve yakalandı. Aynı elemanlar bu kez listOf(1, 2, 3).asSequence() ile kurulduğunda iki toplama da aynı sonucu verdi: dizi kaynak listeyi her seferinde baştan dolaşır. Fark, kaynağın yeniden dolaşılabilir olup olmamasıdır. Bir tembel diziyi birden çok kez kullanacak kod, dizinin hangi kaynaktan kurulduğunu bilmeli; emin değilse ara sonucu toList() ile bir koleksiyona alıp onu kullanmalıdır.

KE19. Bu ölçümler Iterator.asSequence() ve List.asSequence() için. constrainOnce() ile bir diziyi bilerek tek dolaşımlık yapmak ve hata mesajının metni ölçülmedi.

Özet

• Tembel dizide ara işlemler uç işlem gelene kadar çalışmaz; uç işlem gelince her eleman bütün zincirden geçer. Liste her adımda bütün elemanları işler, tembel dizi gereksiz elemanı hiç işlemez.
• generateSequence ve sequence { } sonsuz kaynak kurar; sonlu sonuç take ya da takeWhile ile alınır. Sınırlayıcı unutulursa program bitmez.
• İki ayrı kurulmuş tembel dizi eşit değildir; Sequence equals tanımlamaz. Bu dersin ölçütü: kimlik.
• Sınırlayıcı ölçüm: aynı elemanlar toList() ile toplanınca icerik, toSet() ile toplanınca kismi-icerik verir; eşitliği değerin tuttuğu tip belirler.

Sonraki Adım

Bu ders tembel dizinin tarif olduğunu ve tarifin tek başına bir değer olmadığını gösterdi. Elemanların zamanla, başka bir iş beklenirken gelmesi gerektiğinde ise tarifin kendisi de beklemek zorundadır. Bir sonraki ders bu bekleyen hesabı eş yordamlarla (coroutine) kurar ve yine eşitlik sorusunu sorar: aynı sonucu verecek iki bekleyen iş, birbirine eşit midir?