Sebuah iterator dapat menghasilkan nilai dalam urutan yang sudah memiliki arti: urutan kedatangan, urutan file, urutan database, atau urutan yang dibentuk oleh tahap pipeline sebelumnya. Jika Anda perlu mengurutkan nilai tersebut berdasarkan satu key tanpa mengacak kelompok dengan key yang sama, slices.SortedStableFunc menangani kedua langkah itu sekaligus.

Fungsi ini mengonsumsi sebuah iter.Seq, mengumpulkan nilai yang dihasilkan ke slice baru, lalu mengurutkan slice tersebut dengan comparator. Ketika comparator mengembalikan nol, nilai-nilai itu mempertahankan urutan relatif yang sama seperti di sequence.

Urutkan nilai iterator dengan slices.SortedStableFunc

Misalkan sebuah stream job datang dalam urutan berikut:

package main

import (
    "cmp"
    "fmt"
    "slices"
)

type Job struct {
    Queue    string
    Priority int
    ID       string
}

func main() {
    jobs := []Job{
        {Queue: "api", Priority: 2, ID: "A"},
        {Queue: "batch", Priority: 1, ID: "B"},
        {Queue: "api", Priority: 1, ID: "C"},
        {Queue: "batch", Priority: 1, ID: "D"},
        {Queue: "api", Priority: 2, ID: "E"},
    }

    ordered := slices.SortedStableFunc(
        slices.Values(jobs),
        func(a, b Job) int {
            return cmp.Compare(a.Priority, b.Priority)
        },
    )

    fmt.Println(ordered)
}

Hasilnya:

[{batch 1 B} {api 1 C} {batch 1 D} {api 2 A} {api 2 E}]

Semua job berprioritas 1 berpindah sebelum job berprioritas 2. Di dalam setiap prioritas, urutan sequence asli tetap dipertahankan: B tetap sebelum C, C sebelum D, dan A sebelum E.

Comparator menentukan apa yang dianggap tie. Di sini comparator hanya membandingkan Priority, sehingga job dengan prioritas sama dianggap setara untuk pengurutan meskipun queue dan ID-nya berbeda.

SortedStableFunc mengumpulkan tanpa mengubah sumber

slices.SortedStableFunc berbeda dari slices.SortStableFunc dalam satu hal penting. SortStableFunc menerima slice dan menyusun ulang slice tersebut secara in-place. SortedStableFunc menerima iterator dan mengembalikan slice baru yang telah dikumpulkan.

Pada contoh di atas, jobs mempertahankan urutan aslinya. Hanya ordered yang berisi hasil terurut. Karena itu, SortedStableFunc cocok digunakan pada batas antara pipeline iterator yang lazy dan kode yang memerlukan koleksi terurut yang sudah dimaterialisasi.

Untuk slice yang sudah ada, slices.Values menyediakan adapter:

ordered := slices.SortedStableFunc(
    slices.Values(jobs),
    comparePriority,
)

Jika Anda sudah memiliki iter.Seq[Job], jangan kumpulkan lebih dulu hanya untuk meneruskannya ke fungsi pengurutan. Berikan sequence langsung ke SortedStableFunc:

func orderJobs(seq iter.Seq[Job]) []Job {
    return slices.SortedStableFunc(seq, comparePriority)
}

Ini tetap mematerialisasi seluruh sequence karena pengurutan membutuhkan semua nilai sebelum urutan akhir dapat ditentukan. Keuntungannya adalah Anda menghindari slice perantara yang tidak perlu dan mempertahankan sifat lazy pipeline sampai pengurutan benar-benar membutuhkan penyimpanan.

Tie yang stabil mempertahankan urutan sequence

Stabilitas hanya berpengaruh ketika comparator mengembalikan nol. Perhatikan comparator berikut:

func comparePriority(a, b Job) int {
    return cmp.Compare(a.Priority, b.Priority)
}

Comparator ini sengaja mengabaikan Queue dan ID. Jika dua job memiliki prioritas yang sama, urutan keduanya pada hasil berasal dari urutan yield iterator.

Sekarang tambahkan ID sebagai tie-breaker:

func comparePriorityAndID(a, b Job) int {
    if n := cmp.Compare(a.Priority, b.Priority); n != 0 {
        return n
    }
    return cmp.Compare(a.ID, b.ID)
}

Dengan comparator tersebut, dua job berprioritas sama dengan ID berbeda tidak lagi dianggap setara. Stable sorting tidak dapat mempertahankan urutan kedatangannya karena comparator secara eksplisit menentukan urutannya sendiri.

Perbedaan ini berguna saat memilih aturan perbandingan. Jika urutan kedatangan harus menentukan tie, jangan tambahkan tie-breaker dan gunakan stable sort. Jika aturan domain menyatakan ID harus menentukan tie, masukkan aturan tersebut ke comparator alih-alih bergantung pada urutan yang kebetulan datang dari upstream.

Gunakan stable sorting ketika urutan upstream memiliki arti

Pipeline iterator sering mempertahankan urutan yang berguna sebelum pengurutan akhir. Sebuah sequence mungkin sudah terurut berdasarkan waktu pembuatan, posisi sumber, atau operasi stabil sebelumnya. Mengurutkannya secara stabil berdasarkan key pengelompokan yang lebih luas memungkinkan urutan sebelumnya tetap bertahan di dalam setiap kelompok.

Sebagai contoh, bayangkan job di-yield dari yang paling lama dan perlu dikelompokkan berdasarkan prioritas. Stable sort berdasarkan prioritas menghasilkan kelompok prioritas sambil mempertahankan urutan FIFO di dalam setiap prioritas. Anda tidak perlu menambahkan waktu pembuatan ke comparator hanya untuk membangun ulang urutan yang sudah dimiliki sequence.

Ada trade-off. Urutan akhir kini bergantung pada dua hal: comparator dan urutan sequence yang sudah ada. Jika caller dapat menghasilkan sequence dalam urutan berbeda, hasil untuk key yang sama dapat berbeda antar-caller. Ketika output deterministik harus independen dari urutan input, definisikan comparator lengkap dengan tie-breaker eksplisit.

Stabilitas paling berguna ketika urutan input merupakan bagian dari kontrak, bukan ketika urutan tersebut hanya kebetulan.

Sequence kosong mengembalikan nil slice

Input kosong tidak memerlukan penanganan khusus. slices.SortedStableFunc mengembalikan nil slice ketika sequence tidak menghasilkan nilai.

Contohnya:

var jobs []Job

ordered := slices.SortedStableFunc(
    slices.Values(jobs),
    comparePriority,
)

fmt.Println(ordered == nil) // true
fmt.Println(len(ordered))   // 0

Biasanya kode sebaiknya memperhatikan len(ordered) == 0, bukan apakah slice bernilai nil. Namun perbedaannya dapat penting pada boundary serialisasi atau API, tempat nil slice dan empty slice yang dialokasikan mungkin direpresentasikan berbeda. Jika caller membutuhkan empty slice non-nil, normalisasikan hasil pada boundary tersebut.

Iterator dikonsumsi satu kali

iter.Seq adalah fungsi yang menghasilkan nilai kepada consumer. SortedStableFunc mengonsumsi sequence tersebut saat mengumpulkannya.

Jangan berasumsi setiap sequence dapat diputar ulang dengan aman. Sequence yang ditopang channel, scanner, cursor, atau sumber stateful lain dapat merupakan stream satu kali jalan. Jika bagian program lain juga membutuhkan nilai-nilainya, tentukan dengan sengaja di mana nilai harus dimaterialisasi, alih-alih melakukan range pada sequence sekali lalu berharap data yang sama muncul lagi.

Ini juga berarti mengurutkan iterator tidak bersifat lazy. Fungsi tidak dapat langsung menghasilkan elemen terkecil karena nilai input berikutnya mungkin harus ditempatkan sebelumnya. Fungsi harus mengonsumsi sequence lebih dulu, menyimpan nilainya, lalu mengurutkannya.

Untuk stream yang besar atau tidak terbatas, ini merupakan batasan nyata. Jika input dapat tumbuh tanpa batas praktis, mengumpulkan semuanya dapat menggunakan memori yang tidak dapat diterima atau tidak pernah selesai. Dalam kondisi tersebut, solusi biasanya membutuhkan algoritma berbatas, external sorting, atau pendekatan khusus domain, bukan SortedStableFunc.

Jaga comparator tetap konsisten

Fungsi perbandingan mengikuti konvensi yang sama seperti helper berbasis comparator lainnya di slices: kembalikan nilai negatif ketika elemen pertama harus berada sebelum elemen kedua, nilai positif ketika harus berada setelahnya, dan nol ketika keduanya setara untuk urutan ini.

Menggunakan cmp.Compare untuk field yang dapat diurutkan membuat kontrak tersebut terlihat jelas:

func comparePriority(a, b Job) int {
    return cmp.Compare(a.Priority, b.Priority)
}

Hindari menerapkan perbandingan integer dengan pengurangan:

return a.Priority - b.Priority

Cara itu terlihat ringkas tetapi dapat overflow untuk nilai yang mendekati batas integer, sehingga menghasilkan tanda yang tidak sesuai dengan urutan yang dimaksud. cmp.Compare menghindari failure mode tersebut.

Comparator juga perlu mendeskripsikan strict weak ordering yang konsisten. Jangan membuatnya bergantung pada mutable state yang berubah selama pengurutan, waktu saat ini, nilai acak, atau input lain yang dapat membuat pasangan yang sama dibandingkan secara berbeda dari satu pemanggilan ke pemanggilan berikutnya. Kode pengurutan mengasumsikan aturan ordering tetap koheren sepanjang operasi.

Jika beberapa call site menggunakan urutan domain yang sama, beri nama comparator tersebut. Menggunakan kembali comparePriority lebih mudah diperiksa dan diuji daripada menduplikasi fungsi perbandingan anonim yang dapat menyimpang seiring waktu.

Pilih antara SortedFunc dan SortedStableFunc dengan sengaja

slices.SortedFunc juga mengumpulkan iterator dan mengurutkan slice hasil dengan comparator, tetapi tidak menjanjikan untuk mempertahankan urutan masuk elemen-elemen yang dianggap setara.

Gunakan slices.SortedStableFunc ketika elemen yang setara memiliki urutan sequence yang bermakna. Perilaku FIFO di dalam kelompok prioritas, urutan source file di dalam kategori, dan ranking sebelumnya di dalam bucket adalah contoh umum.

Gunakan slices.SortedFunc ketika elemen yang setara dapat dipertukarkan dan tidak ada caller yang boleh bergantung pada urutan sebelumnya. Jika Anda sebenarnya membutuhkan tie-breaker deterministik seperti ID atau timestamp, nyatakan dalam comparator alih-alih memilih stable sorting dan berharap input datang dalam urutan yang diinginkan.

Untuk kode yang sudah memiliki slice dan diizinkan menyusun ulang slice tersebut, slices.SortStableFunc menghindari langkah pengumpulan dari iterator dan mengurutkan secara in-place. SortedStableFunc lebih cocok ketika sumber secara alami berupa iterator atau ketika Anda menginginkan slice terurut baru sambil membiarkan slice sumber tetap tidak berubah.

Materialisasikan pada titik ketika pengurutan menjadi perlu

Pipeline iterator berguna karena dapat menunda alokasi ketika nilai difilter atau ditransformasikan. Pengurutan adalah boundary alami tempat sifat lazy itu harus berakhir.

Pertahankan sequence tetap lazy melalui operasi yang dapat bekerja satu nilai pada satu waktu, lalu panggil slices.SortedStableFunc ketika Anda membutuhkan hasil terurut lengkap dan nilai dengan key sama harus mempertahankan urutan sequence-nya. Jika urutan input bukan bagian dari kontrak hasil, gunakan SortedFunc atau tambahkan tie-breaker eksplisit. Membuat pilihan tersebut terlihat di kode mencegah caller di kemudian hari bergantung pada jaminan ordering yang sebenarnya tidak pernah Anda maksudkan.

Go Slice Iterator Standard Library Pengurutan