Go'da slices, maps, sort ve cmp Paketleri: Sıralama, Arama, Gruplama ve Iterator'larla Collection İşleri

Sürüm notu: Bu yazıdaki kodlar Go 1.27.4 ile derlenip çalıştırılmıştır; Bookstore module'ünün go satırı 1.26.0'dır ve kod Go 1.26.11 ile de derlenip testlerden geçer. slices, maps ve cmp package'ları Go 1.21, iterator döndüren maps.Keys ve slices.Sorted Go 1.23, strings.SplitSeq Go 1.24 ile gelmiştir. Türkçe sıralama için golang.org/x/text v0.44.0 kullanıldı; json/v2 örneği //go:build go1.27 ile ayrılmıştır.

Önce Tahmin Et

Sitedeki serilerin ortak örnek uygulaması Bookstore'da (bir online kitapçı) raf listesine çok satan kitabı ekleyen küçük bir fonksiyon var. Aynı rafı iki farklı yere genişletiyorsun:

package main

import "fmt"

func withBestseller(shelf []string) []string {
    return append(shelf, "Dune")
}

func main() {
    shelf := make([]string, 2, 4)
    copy(shelf, []string{"Emma", "Persuasion"})
    a := withBestseller(shelf)
    b := append(shelf, "Foundation")
    fmt.Println(a, b)
}

a "Dune" ile, b "Foundation" ile bitmeli. Öyle mi?

$ go run .
[Emma Persuasion Foundation] [Emma Persuasion Foundation]

Değil. shelf'in kapasitesi 4, uzunluğu 2; iki append de yeni bir array açmadan aynı backing array'in üçüncü elemanına yazdı ve ikincisi birincinin üzerine yazdı. 03'te slice header'ı anlatırken gördüğümüz kural, slice alan ve slice dönen her fonksiyonda karşına çıkıyor. Bu yazıda collection işlerini görüyoruz: slices ile sıralama ve arama, çok alanlı sıralama için cmp, maps ve rastgele iterasyon sırası, LINQ (Language Integrated Query; C#'ta collection'ları sorgulama syntax'ı) karşılıkları ve eski sort package'ı. Bookstore'a kategori, ?sort= parametresi ve GET /api/categories geliyor.

slices.SortFunc ve cmp ile Sıralama

Katalogdaki kitaplara bu yazıda bir Category field'ı ve iki bilimkurgu kitabı ekledim (Foundation, The Left Hand of Darkness). Sıralı karşılaştırılabilen tipler (sayılar, string'ler) için slices.Sort yeterli; struct'lar için slices.SortFunc bir karşılaştırma fonksiyonu alıyor. Fonksiyon C#'taki IComparer<T>.Compare gibi negatif, sıfır ya da pozitif dönüyor:

func main() {
    books := catalog.Store{}.All()

    // Önce kategori artan, sonra fiyat azalan, sonra başlık.
    slices.SortFunc(books, func(a, b catalog.Book) int {
        return cmp.Or(
            cmp.Compare(a.Category, b.Category),
            cmp.Compare(b.Price, a.Price), // a'dan önce b: azalan
            cmp.Compare(a.Title, b.Title),
        )
    })
    for _, b := range books {
        fmt.Printf("%-16s %-26s %v\n", b.Category, b.Title, b.Price)
    }

    isbns := make([]string, 0, len(books))
    for _, b := range books {
        isbns = append(isbns, b.ISBN)
    }
    slices.Sort(isbns) // BinarySearch sıralı bir slice ister
    i, found := slices.BinarySearch(isbns, "9780441172719")
    j, missing := slices.BinarySearch(isbns, "9780000000002")
    fmt.Println(i, found, j, missing)

    cheapest := slices.MinFunc(books, func(a, b catalog.Book) int { return cmp.Compare(a.Price, b.Price) })
    k := slices.IndexFunc(books, func(b catalog.Book) bool { return b.Stock == 0 })
    fmt.Println(cheapest.Title, k, books[k].Title)
}

$ go run ./labs/17-sorting
Classics         Middlemarch                310.00 TRY
Classics         Sense and Sensibility      210.00 TRY
Classics         Emma                       199.00 TRY
Classics         Persuasion                 185.00 TRY
Fantasy          The Hobbit                 289.50 TRY
Science Fiction  Dune                       349.90 TRY
Science Fiction  The Left Hand of Darkness  310.00 TRY
Science Fiction  Foundation                 275.00 TRY
4 true 0 false
Persuasion 4 The Hobbit

cmp.Compare iki değeri karşılaştırıp -1, 0 ya da +1 dönüyor; cmp.Or sıfır olmayan ilk argümanı veriyor. İkisi birlikte LINQ'teki OrderBy(...).ThenByDescending(...).ThenBy(...) zincirinin karşılığı oluyor. Azalan sıra için argümanların yerini değiştirmek yeterli. cmp.Or sıradan bir fonksiyon olduğu için bütün argümanları her karşılaştırmada hesaplanıyor; pahalı bir karşılaştırma varsa if c := ...; c != 0 { return c } zinciri daha ucuz.

Arama tarafında slices.BinarySearch sıralı bir slice'ta konumu ve bulunup bulunmadığını dönüyor; bulamadığında ilk değer, elemanın eklenmesi gereken yer. Sırasız slice'ta Index, IndexFunc, Contains var; MinFunc/MaxFunc LINQ'teki MinBy/MaxBy'ın karşılığı ve boş slice'ta panic veriyor.

Stable Sıralama ve ?sort= Parametresi

slices.SortFunc stable değil: eşit çıkan elemanların sırası garanti edilmiyor. Bir API'nin sayfalanmış listesinde bu, aynı fiyattaki iki kitabın sayfalar arasında yer değiştirmesi demek. internal/catalog'a gelen SortBooks, "category,-price" gibi bir tarifi okuyup slices.SortStableFunc ile sıralıyor:

// bookOrders iki kitabı tek bir field'a göre artan sırada karşılaştırır.
var bookOrders = map[string]func(a, b Book) int{
    "title":    func(a, b Book) int { return cmp.Compare(a.Title, b.Title) },
    "author":   func(a, b Book) int { return cmp.Compare(a.Author, b.Author) },
    "category": func(a, b Book) int { return cmp.Compare(a.Category, b.Category) },
    "price":    func(a, b Book) int { return cmp.Compare(a.Price, b.Price) },
    "stock":    func(a, b Book) int { return cmp.Compare(a.Stock, b.Stock) },
}

// SortBooks, list'i "category,-price" gibi bir tarife göre yerinde sıralar: field'lar
// virgülle ayrılır, başta "-" azalan demektir. Sıralama stable olduğu için
// eşit çıkan kitaplar katalogdaki sıralarını korur.
func SortBooks(list []Book, spec string) error {
    var keys []func(a, b Book) int
    for field := range strings.SplitSeq(spec, ",") {
        name, desc := strings.CutPrefix(strings.TrimSpace(field), "-")
        asc, ok := bookOrders[name]
        if !ok {
            return fmt.Errorf("%w: unknown field %q, want one of %s", ErrInvalidSort, name,
                strings.Join(slices.Sorted(maps.Keys(bookOrders)), ", "))
        }
        if desc {
            keys = append(keys, func(a, b Book) int { return asc(b, a) })
        } else {
            keys = append(keys, asc)
        }
    }
    slices.SortStableFunc(list, func(a, b Book) int {
        for _, key := range keys {
            if c := key(a, b); c != 0 {
                return c
            }
        }
        return 0
    })
    return nil
}

Field'lar bir map'te, her biri artan sırada karşılaştıran küçük bir fonksiyon. Azalan sıra için fonksiyonu argümanları ters veren bir closure'la sarıyorum; asc döngü gövdesinde tanımlandığı için her closure kendi asc'ını yakalıyor. Middlemarch ile The Left Hand of Darkness'ın ikisi de 310,00; tablo testinde bu eşitliğin katalog sırasını koruduğunu kontrol eden bir satır var. Handler All()'un döndürdüğü kopyayı sıralıyor, katalogun kendisi değişmiyor:

$ curl -s "http://127.0.0.1:52715/api/books?sort=category,-price&pageSize=2"
{"items":[{"isbn":"9780141439549","title":"Middlemarch","author":"George Eliot","category":"Classics","price":31000,"stock":4},{"isbn":"9780141439662","title":"Sense and Sensibility","author":"Jane Austen","category":"Classics","price":21000,"stock":5}],"page":1,"pageSize":2,"totalItems":8,"totalPages":4}
$ curl -s "http://127.0.0.1:52715/api/books?sort=rating"
invalid sort: unknown field "rating", want one of author, category, price, stock, title

Hata mesajındaki liste de slices.Sorted(maps.Keys(bookOrders)) ile üretiliyor. Map'ten gelen listeyi sıralamasaydım mesaj her istekte başka bir sırayla çıkardı; sebebi bir sonraki bölümde.

maps: Rastgele Sıra, Keys ve Sorted

Go map'lerinin iterasyon sırası tanımsız ve runtime bunu bilerek her seferinde değiştiriyor; böylece sıraya güvenen kod test aşamasında bozuluyor:

func main() {
    stock := map[string]int{"Dune": 12, "Emma": 7, "Foundation": 9, "Middlemarch": 4, "Persuasion": 3}
    for range 3 {
        var order []string
        for title := range stock {
            order = append(order, title)
        }
        fmt.Println(order)
    }

    fmt.Println(slices.Sorted(maps.Keys(stock))) // Keys bir iterator döner, Sorted onu toplar
    fmt.Println(slices.Collect(maps.Values(map[string]int{"Dune": 12})))

    low := maps.Clone(stock)
    maps.DeleteFunc(low, func(_ string, n int) bool { return n >= 5 })
    fmt.Println(low, len(stock))
}

$ go run ./labs/17-maps
[Emma Foundation Middlemarch Persuasion Dune]
[Dune Emma Foundation Middlemarch Persuasion]
[Persuasion Dune Emma Foundation Middlemarch]
[Dune Emma Foundation Middlemarch Persuasion]
[12]
map[Middlemarch:4 Persuasion:3] 5

Aynı map üç kez üç farklı sırayla dolaşıldı. C#'taki Dictionary<K,V> ekleme sırasını genellikle korur ama bunu garanti etmez; Go garanti etmediğini her çalıştırmada gösteriyor. maps.Keys ve maps.Values slice değil iterator dönüyor; slices.Sorted iterator'ı toplayıp sıralıyor, slices.Collect sadece topluyor. fmt ise map'leri key sırasıyla yazıyor, son satırın sıralı görünmesi bu yüzden.

JSON'da da benzer bir ayrıntı var. v1 map key'lerini sıralayarak yazıyor; Go 1.27'nin json/v2'si ise sadece json.Deterministic(true) verilirse sıralıyor:

$ go run ./labs/17-jsonmap
v1 {"Dune":12,"Emma":7,"Foundation":9,"Middlemarch":4,"Persuasion":3}
v2 {"Foundation":9,"Middlemarch":4,"Persuasion":3,"Dune":12,"Emma":7}
v2 deterministic {"Dune":12,"Emma":7,"Foundation":9,"Middlemarch":4,"Persuasion":3}
...

14'teki json/v2'ye geçiş planına bir madde daha: cevabı byte byte karşılaştıran testler ve ETag (cevabın içeriğinden üretilen, değişip değişmediğini anlamaya yarayan header) hesaplayan kod v2'de bu option'ı istiyor. Bookstore'un kategori listesi map'le gruplanıyor ama cevap sıralı bir slice:

// Categories katalogu kategoriye göre gruplar, ada göre sıralı döner.
func (Store) Categories() []CategorySummary {
    byName := make(map[string]*CategorySummary)
    for _, b := range books {
        s, ok := byName[b.Category]
        if !ok {
            s = &CategorySummary{Name: b.Category, Cheapest: b.Price}
            byName[b.Category] = s
        }
        s.Titles++
        s.Stock += b.Stock
        s.Cheapest = min(s.Cheapest, b.Price)
    }
    out := make([]CategorySummary, 0, len(byName))
    for _, name := range slices.Sorted(maps.Keys(byName)) { // map sırası rastgele
        out = append(out, *byName[name])
    }
    return out
}

$ curl -s http://127.0.0.1:52715/api/categories
[{"name":"Classics","titles":4,"stock":19,"cheapest":18500},{"name":"Fantasy","titles":1,"stock":0,"cheapest":28950},{"name":"Science Fiction","titles":3,"stock":23,"cheapest":27500}]

LINQ'ten Gelenler İçin: GroupBy, Sum, Distinct

06'da Go'da zincirleme LINQ kültürünün neden olmadığını konuşmuştuk. Pratikte LINQ ile yazdığın sorguların çoğu bir döngü, bir map ve birkaç if:

// GroupBy, C#'taki ToLookup gibi seq'in değerlerini key'lerinin altında toplar.
func GroupBy[K comparable, V any](seq iter.Seq[V], key func(V) K) map[K][]V {
    groups := make(map[K][]V)
    for v := range seq {
        k := key(v)
        groups[k] = append(groups[k], v)
    }
    return groups
}

func main() {
    store := catalog.Store{}

    // books.GroupBy(b => b.Author).Where(g => g.Count() > 1)
    byAuthor := GroupBy(store.Books(), func(b catalog.Book) string { return b.Author })
    for _, author := range slices.Sorted(maps.Keys(byAuthor)) {
        if n := len(byAuthor[author]); n > 1 {
            fmt.Println(author, n)
        }
    }

    // books.Where(b => b.Stock > 0).Sum(b => b.Price * b.Stock)
    var value catalog.Money
    for b := range store.Books() {
        if b.Stock > 0 {
            value += b.Price * catalog.Money(b.Stock)
        }
    }
    fmt.Println("stock value:", value)

    // books.Select(b => b.Category).Distinct()
    seen := make(map[string]struct{}) // bir set: struct{} bellekte yer kaplamaz
    var categories []string
    for b := range store.Books() {
        if _, ok := seen[b.Category]; !ok {
            seen[b.Category] = struct{}{}
            categories = append(categories, b.Category)
        }
    }
    fmt.Println(categories)
}

$ go run ./labs/17-linq
Jane Austen 3
stock value: 11531.80 TRY
[Science Fiction Fantasy Classics]

Set için ayrı bir tip yok; map[string]struct{} kullanılıyor ve struct{} değeri bellekte yer kaplamıyor. Sık kullandığın birkaç işlem için GroupBy gibi küçük generic yardımcılar yazmak makul; ama bütün LINQ'i yeniden yazmaya kalkma. Karşılıklar:

Slice Paylaşımı: Clip, Delete, Compact

Önce Tahmin Et'e dönelim. slices package'ında slice'ı değiştiren fonksiyonlar da backing array'i paylaşıyor ve bunu bilmen gerekiyor:

c := withBestseller(slices.Clip(shelf)) // cap == len: append kopyalamak zorunda
d := append(slices.Clip(shelf), "Foundation")
fmt.Println(c, d)

titles := []string{"Dune", "Emma", "Middlemarch", "Persuasion"}
rest := slices.Delete(titles, 1, 2) // "Emma"yı çıkarır
fmt.Printf("%q %q\n", rest, titles) // eski kuyruk sıfırlanır (Go 1.22)

tags := []string{"classic", "classic", "romance", "classic"}
fmt.Println(slices.Compact(slices.Clone(tags))) // sadece komşular
slices.Sort(tags)
fmt.Println(slices.Compact(tags)) // önce sıralanınca gerçek distinct
fmt.Println(slices.Insert([]string{"Dune", "Emma"}, 1, "Foundation"))

$ go run ./labs/17-aliasing
[Emma Persuasion Foundation] [Emma Persuasion Foundation]
[Emma Persuasion Dune] [Emma Persuasion Foundation]
["Dune" "Middlemarch" "Persuasion"] ["Dune" "Middlemarch" "Persuasion" ""]
[classic romance classic]
[classic romance]
[Dune Foundation Emma]

slices.Clip kapasiteyi uzunluğa indiriyor; ardından gelen append yeni bir array açmak zorunda kalıyor ve iki sonuç birbirinden ayrılıyor. Bir slice'ı dışarıya verirken ya da dışarıdan alıp saklarken Clip ya da Clone kullanmak bu tür hataları baştan kesiyor. slices.Delete sonucu yeni slice olarak dönüyor ve Go 1.22'den beri eski slice'ın artık kullanılmayan son elemanını sıfırlıyor: titles'ın son elemanı boş string oldu. Eski slice'ı kullanmaya devam eden kod bunu fark etmeden yanlış veri okur; dönen değeri aynı değişkene ata (titles = slices.Delete(titles, 1, 2)). Compact sadece yan yana duran tekrarları siliyor; gerçek bir distinct için önce sırala.

sort Package'ı ve Türkçe Sıralama

Eski kodlarda sort.Slice ve sort.Strings göreceksin. sort package'ının kendi dokümanı yeni kodda slices'ı öneriyor. 10.000 kitabı fiyata göre sıralayan iki benchmark:

func BenchmarkSortSlice(b *testing.B) {
    src := shuffled()
    books := make([]catalog.Book, len(src))
    for b.Loop() {
        copy(books, src)
        sort.Slice(books, func(i, j int) bool { return books[i].Price < books[j].Price })
    }
}

$ go test -run '^$' -bench . -benchmem -cpu 1 -count 3 ./labs/17-sortbench
BenchmarkSortSlice          1315    868117 ns/op    152 B/op    3 allocs/op
BenchmarkSortSlice          1393    865762 ns/op    152 B/op    3 allocs/op
BenchmarkSortSlice          1326    897244 ns/op    152 B/op    3 allocs/op
BenchmarkSlicesSortFunc     1386    849663 ns/op      0 B/op    0 allocs/op
BenchmarkSlicesSortFunc     1431    946248 ns/op      0 B/op    0 allocs/op
BenchmarkSlicesSortFunc     1146    882797 ns/op      0 B/op    0 allocs/op

Bu ölçümde süre farkı gürültünün içinde kaldı; Book 80 byte'lık bir struct ve zamanın çoğu elemanları taşımaya gidiyor. Fark allocation'da: sort.Slice reflection ile bir swap fonksiyonu kurduğu için her çağrıda 3 allocation yapıyor, generic slices.SortFunc hiç yapmıyor. Asıl kazanç okunabilirlik: sort.Slice'ın index alan less fonksiyonu yerine iki elemanı alan bir karşılaştırma var.

String sıralamasında bir tuzak daha var: slices.Sort UTF (Unicode Transformation Format; Unicode karakterlerini byte'lara çeviren kodlama ailesi) ailesinden UTF-8'in byte'larını karşılaştırıyor, Türkçe harfler ise byte olarak İngilizce harflerin hepsinden büyük:

func main() {
    authors := []string{"Zülfü Livaneli", "Şükrü Erbaş", "Sabahattin Ali", "Çetin Altan", "Cemal Süreya", "Ömer Seyfettin", "Orhan Pamuk", "İlhan Berk"}

    byteOrder := slices.Clone(authors)
    slices.Sort(byteOrder) // UTF-8 byte'larını karşılaştırır
    fmt.Println(byteOrder)

    tr := collate.New(language.Turkish)
    trOrder := slices.Clone(authors)
    tr.SortStrings(trOrder)
    fmt.Println(trOrder)

    fmt.Println(tr.CompareString("ılık", "ilik"), tr.CompareString("Çay", "Cay"))
}

$ go run ./labs/17-collate
[Cemal Süreya Orhan Pamuk Sabahattin Ali Zülfü Livaneli Çetin Altan Ömer Seyfettin İlhan Berk Şükrü Erbaş]
[Cemal Süreya Çetin Altan İlhan Berk Orhan Pamuk Ömer Seyfettin Sabahattin Ali Şükrü Erbaş Zülfü Livaneli]
-1 1

Byte sırasında Çetin Altan Zülfü Livaneli'nin arkasına düştü. golang.org/x/text/collate Türkçe alfabe sırasını uyguluyor: C'den sonra Ç, O'dan sonra Ö, ı ile i ayrı harfler. Bu module Go ekibinin standart kütüphane dışında tuttuğu bir module; Bookstore'da şimdiye kadar dolaylı bağımlılıktı, bu lab ile doğrudan bağımlılık oldu ve son sürüme (v0.44.0) yükseltildi. Yazar listesi gibi kullanıcıya gösterilen Türkçe listelerde collator kullan; key, ISBN (kitaplara verilen 13 haneli uluslararası numara), kod gibi makine değerlerinde byte sırası doğru ve çok daha hızlı.

Üretimde Dikkat

Sayfalanan her listede sıralama stable ve tam olsun. Kullanıcının istediği alanların sonuna benzersiz bir alan (ISBN, sipariş numarası) eklemek, eşit kayıtların sayfalar arasında kaymasını kesin olarak engelliyor. Veritabanından gelen listelerde aynı işi ORDER BY ... , Isbn yapıyor.

Dışarıdan gelen sıralama parametresini bir whitelist'e karşı kontrol et. bookOrders map'i hem whitelist hem implementasyon; SQL tarafında sıralama alanını string birleştirerek sorguya koymak 11'deki SQL injection'ın kapısını açar.

Büyük slice'larda allocation'ı ölç. slices.Clone, Collect ve Sorted her seferinde yeni bir slice ayırıyor; hot path'te (en sık çalışan kod yolu) yerinde sıralama ve önceden make([]T, 0, n) ile kapasite vermek GC'nin (garbage collector; kullanılmayan belleği toplayan bileşen) yükünü düşürüyor.

Sık Düşülen Tuzaklar

Kapasitesi dolmamış bir slice'a iki yerden append yapmak. İkisi aynı array'e yazar; dışarı verdiğin slice'ı slices.Clip ya da Clone ile ayır.

Map iterasyon sırasına güvenmek. Test bir çalıştırmada geçip diğerinde düşer; sıra gerekiyorsa slices.Sorted(maps.Keys(m)).

Sayfalanan listede slices.SortFunc kullanmak. Eşit elemanların sırası değişebilir; SortStableFunc ve benzersiz bir son alan kullan.

slices.Delete'ten sonra eski slice'ı kullanmak. Son elemanlar sıfırlanmıştır; dönen değeri ata.

Türkçe listeyi slices.Sort ile sıralamak. Ç, Ö, Ş, İ listenin sonuna gider; x/text/collate kullan.

Küçük Bir Deneme

★☆☆ GET /api/books?sort='a isbn alanını ekle ve SortBooks'un her tarifin sonuna kendiliğinden isbn eklemesini sağla. Tablo testindeki eşitlik satırı hâlâ geçiyor mu, neden?

★★☆ labs/17-linq'e LINQ'teki CountBy'ın karşılığı olan generic CountBy[K comparable, V any](seq iter.Seq[V], key func(V) K) map[K]int fonksiyonunu yaz ve kategori başına kitap sayısını sıralı olarak yazdır.

★★★ GET /api/authors'a ?sort=name ekle ve sıralamayı collate.New(language.Turkish) ile yap. Collator'ı her istekte yeniden oluşturmanın maliyetini bir benchmark ile ölç; collate.Collator'ın birden çok goroutine'den aynı anda kullanılıp kullanılamayacağını dokümanından kontrol et.

Sıraladık, grupladık, aradık; ama veri hep bellekteydi. Bir sonraki yazıda dosyalara geçiyoruz: io.Reader ve io.Writer interface'leri, bufio ile satır satır okumak, encoding/csv ve 11'de söz verdiğim embed.