Algoritme Favorit Saya: Menemukan Median dalam Waktu Linear (2018)

 (rcoh.me)
2 poin oleh GN⁺ 2024-07-26 | 1 komentar | Bagikan ke WhatsApp
  • Median mudah didapat dengan mengurutkan data, tetapi karena biaya pengurutan, bahkan untuk masalah pemilihan satu elemen pun kita terikat batas O(n log n)
  • quickselect dapat menemukan elemen ke-k atau median dalam rata-rata O(n) dengan menelusuri secara rekursif hanya sisi yang dibutuhkan
  • Pivot acak bekerja baik dalam praktik, tetapi jika terus memilih pivot buruk, hanya satu elemen yang tereliminasi tiap kali sehingga bisa memburuk hingga O(n²)
  • median-of-medians memilih kembali median dari median grup berisi 5 elemen, sehingga bahkan pada kasus terburuk setidaknya 30% elemen dapat dieliminasi
  • Dalam implementasi nyata, biaya menghitung pivot bisa besar; seperti pustaka standar C++, introselect yang menggabungkan quickselect dan heapselect bisa menjadi pilihan yang lebih praktis

Batasan saat mencari median dengan pengurutan

  • Cara paling sederhana menghitung median adalah mengurutkan daftar lalu memilih nilai pada indeks tengah
  • Untuk daftar dengan panjang ganjil, kembalikan elemen tengah; untuk panjang genap, kembalikan rata-rata dua elemen tengah
  • Kompleksitas waktu tercepat untuk pengurutan berbasis perbandingan adalah O(n log n), sehingga waktu eksekusi cara ini juga didominasi oleh pengurutan
  • Kodenya memang sederhana, tetapi melakukan lebih banyak pekerjaan daripada yang diperlukan jika hanya ingin mencari satu median

quickselect yang menghasilkan rata-rata O(n)

  • quickselect adalah algoritme rekursif yang dibuat oleh Tony Hoare, dan dapat menemukan bukan hanya median tetapi juga elemen ke-k mana pun dalam daftar
  • Alur dasarnya adalah membagi daftar berdasarkan pivot, lalu terus menelusuri hanya sisi yang berisi elemen ke-k
    • Pilih satu pivot dari daftar
    • Bagi daftar menjadi elemen yang kurang dari atau sama dengan pivot dan elemen yang lebih besar dari pivot
    • Tentukan di sisi mana elemen ke-k yang dicari berada, lalu lakukan pemanggilan rekursif hanya pada subdaftar tersebut
    • Saat turun ke subdaftar kanan, sesuaikan nilai k sebesar jumlah elemen kiri yang sudah dikecualikan
  • Pada contoh daftar [9,1,0,2,3,4,6,8,7,10,5], karena panjangnya 11, kita mencari elemen terkecil ke-6, mempersempit rentang sesuai pivot, dan akhirnya mengembalikan 5
  • quickselect_median menggunakan quickselect untuk mencari satu indeks tengah jika panjang daftar ganjil; jika genap, ia mencari dua indeks tengah lalu mengambil rata-ratanya
  • Jika pivot membagi daftar hampir setengah-setengah, jumlah pemrosesan menjadi n + n/2 + n/4 + ... = 2n, yaitu O(n)

Untuk menghindari kasus terburuk, diperlukan pivot yang baik

  • Rata-rata O(n) pada quickselect bergantung pada asumsi bahwa pemilihan pivot cukup baik
  • Jika nasib buruk membuat kita memilih nilai maksimum sebagai pivot di setiap tahap, hanya satu elemen yang tereliminasi di tiap tahap sehingga menjadi O(n²)
  • Untuk menjamin waktu linear bahkan pada kasus terburuk, quickselect harus diberi pivot yang cukup baik dalam waktu linear
  • Algoritme pemilihan pivot ini dikembangkan pada 1973 oleh Blum, Floyd, Pratt, Rivest, dan Tarjan; makalah terkait ditautkan sebagai 1973 paper

Pemilihan pivot median-of-medians

  • median-of-medians adalah prosedur untuk memilih pivot yang baik bagi quickselect
  • Alur implementasinya adalah sebagai berikut
    • Jika jumlah elemen kurang dari 5, gunakan fungsi median berbasis pengurutan yang sudah ada
    • Bagi daftar menjadi kelompok-kelompok berisi 5 elemen
    • Demi penyederhanaan, buang kelompok tidak lengkap yang berisi kurang dari 5 elemen
    • Urutkan tiap kelompok dan kumpulkan median pada indeks 2
    • Dari daftar median yang terkumpul, cari kembali mediannya dan kembalikan sebagai pivot
  • Karena ukuran tiap kelompok tetap 5 elemen, pengurutan per kelompok dianggap memakan waktu konstan, dan secara keseluruhan merupakan pekerjaan O(n)
  • Pemanggilan rekursif untuk mencari median dari para median dimasukkan dalam analisis sebagai submasalah berukuran n/5

Mengapa setidaknya 30% dapat dieliminasi

  • Kualitas pivot dapat dianalisis dengan membayangkan kelompok-kelompok berisi 5 elemen diurutkan dan disusun sebagai kolom, lalu median tiap kolom diurutkan kembali untuk memilih median dari para median
  • Bahkan pada kasus terburuk ketika pivot bergeser sejauh mungkin ke depan, elemen-elemen di kuadran tertentu dijamin lebih kecil atau lebih besar daripada pivot
  • Dengan mengambil 3 elemen dari tiap kolom dan mempertimbangkan separuh kolom, setidaknya 3/5 * 1/2 * n = 3/10 n elemen dapat dieliminasi
  • Rasio eliminasi yang dijamin: {p:30}
  • Total waktu eksekusi dinyatakan dengan relasi rekurensi berikut
T(n) = n + T(n/5) + T(7n/10)
  • Di sini n adalah pekerjaan partisi, T(n/5) adalah perhitungan median-of-medians, dan T(7n/10) adalah penelusuran rekursif quickselect
  • Karena relasi rekurensi ini memiliki dua suku rekursif, teorema master sederhana tidak dapat diterapkan, dan induksi menjadi metode pembuktian yang intuitif

Hasil kombinasi: mencari median dalam waktu linear

  • quickselect dapat menemukan median dalam waktu linear jika diberi pivot yang cukup baik
  • median-of-medians dapat memilih pivot baik yang dibutuhkan quickselect dalam O(n)
  • Dengan menggabungkan kedua algoritme, kita mendapatkan algoritme yang menemukan median atau elemen ke-n dalam daftar dalam waktu linear

Pilihan dalam implementasi nyata

  • Dalam praktik, pemilihan pivot acak hampir selalu sudah cukup
  • median-of-medians juga linear, tetapi dalam praktik bisa lambat karena biaya menghitung pivot besar
  • Pustaka standar C++ menggunakan introselect, yang menggabungkan heapselect dan quickselect serta memiliki batas atas O(n log n)
  • introselect biasanya dimulai dengan algoritme yang cepat tetapi memiliki batas atas buruk, lalu beralih ke algoritme yang lebih lambat tetapi berbatas atas baik ketika gagal memilih pivot yang efektif
  • Dalam perbandingan jumlah elemen yang diperiksa fungsi quickselect, pivot deterministik hampir selalu mempertimbangkan lebih sedikit elemen daripada pivot acak, tetapi perbandingan ini tidak memasukkan biaya perhitungan median-of-medians
  • new paper yang terbit pada 2017 berisi pembahasan yang membuat pendekatan median-of-medians mampu bersaing dengan algoritme pemilihan lain

Bacaan terkait

1 komentar

 
GN⁺ 2024-07-26
Opini Hacker News

  • Sekitar 4 tahun lalu, saya membandingkan beberapa algoritma median, dan tulisannya jadi jauh lebih panjang dari yang saya perkirakan :)
    https://danlark.org/2020/11/11/miniselect-practical-and-generic-selection-algorithms/

    • Di antara ini, adakah algoritma yang bisa dengan mudah diubah menjadi arg-median, yaitu mengembalikan indeks yang memiliki nilai median?

  • 10–15 tahun lalu, saya secara rutin harus mencari median dari miliaran nilai yang diparse dari entri log berukuran beberapa kilobyte. Saat itu kami memakai MapReduce untuk pemrosesan skala besar, dan pada data sebanyak ini kami butuh sesuatu yang bukan hanya waktu linear, tetapi kalau bisa juga satu pass yang terdistribusi ke banyak mesin
    Mengetahui presisi dan rentang datanya sangat membantu. Nilainya adalah timing dalam satuan milidetik bilangan bulat, jadi tidak negatif, dan kami juga tahu bahwa persentil ke-90 jauh lebih kecil dari 1 detik
    Biasanya mencari median menuntut pekerjaan yang mirip sorting, tetapi dengan kondisi seperti ini bucket sort menjadi mungkin. Cukup buat dictionary dengan key berupa timing milidetik bilangan bulat dan value berupa jumlah kemunculan, yakni histogram
    Karena timing maksimum tidak diketahui, agar ukuran dictionary tidak meledak, semua nilai di atas 999 ms dimasukkan ke bucket 999 ms. Dengan begitu jumlahnya dibatasi sekitar 2000 bilangan bulat berupa key dan value 0–999. Bagian ini berbeda dari bucket sort biasa, dan meski didistribusikan dengan MapReduce, bisa diproses sangat mudah dalam satu pass; setelah itu median tinggal diambil dari histogram

    • Apakah benar-benar perlu median persis dari miliaran nilai? Atau nilai di antara 49,9% dan 50,1% sudah cukup? Kalau yang terakhir, jauh lebih mudah. Ambil sampel 10.000 secara acak merata, lalu gunakan mediannya
      Angka 10.000 itu hanya contoh sembarang, tetapi jumlah sampel yang diperlukan untuk tingkat keyakinan yang diinginkan bisa dihitung secara statistik, dan sepertinya tidak akan terlalu besar
    • Saya tidak yakin, tetapi dari luar ini terlihat mirip dengan cara kerja internal Prometheus
      Pada beberapa sistem yang pernah saya tangani, Prometheus berperilaku seolah memberi batas sekitar 10 detik untuk latensi. Jadi request yang melewati batas itu semuanya masuk sebagai 10 detik, meskipun sebenarnya bisa lebih lama. Menarik
    • Apakah ini pekerjaan membuat metrik ketersediaan, dan saat itu kamu intern? Sistem itu terdengar, eh, sangat familier
    • Saya tidak mengerti kenapa memakai dictionary dengan key 0…999. Bukankah cukup memakai array yang diindeks 0…999?

  • Pada 2017 ada makalah baru yang membuat pendekatan median-of-medians bisa bersaing dengan algoritma seleksi lain, dan ada catatan tambahan bahwa penulis makalahnya, Andrei Alexandrescu, yang memberi tahu
    Ia juga pernah memberi presentasi tentang algoritmanya pada 2016. Orangnya menarik saat presentasi, jadi sangat direkomendasikan
    There's Treasure Everywhere - Andrei Alexandrescu
    https://www.youtube.com/watch?v=fd1_Miy1Clg

    • Andrei Alexandrescu luar biasa. Sekitar tahun 2000 ia memberi presentasi tentang algoritma lock-free dan wait-free, dan saya langsung menerapkannya pada proyek jaringan kontrol industri C++ yang sangat besar waktu itu
      Kalau Anda memakai perangkat lunak, saya sarankan menonton dan membaca semua tulisan serta presentasi Andrei yang bisa ditemukan. Presentasi ini juga benar-benar harta karun
    • Mengejutkan juga bahwa ia sosok yang cukup berpengetahuan luas, bahkan menurut standar ilmu komputer. Saya mengenalnya lewat template metaprogramming, tetapi di sini ia beralih dari bahasa pemrograman ke algoritma

  • Saat S1 saya belajar algoritma median-of-medians quickselect dan benar-benar terkesan. Saya mencoba mengimplementasikannya sendiri, tetapi rasanya lambat sekali. Waktu jalannya memang bertambah secara linear, tetapi agar itu bermakna, daftar harus berisi setidaknya puluhan miliar item
    Ketika membicarakan ini dengan teman mahasiswa pascasarjana, saya mendapat komentar semacam, “Memang lambat, tapi yang penting adalah algoritma itu membuktikan bahwa seleksi dari list yang tidak diurutkan bisa dilakukan dalam waktu O(n). Dulu kita bahkan tidak tahu apakah itu mungkin, dan sekarang setelah kita tahu itu mungkin, bisa saja ada algoritma linear yang lebih cepat.”
    Itu pelajaran yang begitu sederhana sekaligus mendalam sampai-sampai saya hampir mendaftar ke program pascasarjana. Saya tidak tahu apakah teman itu mengingat percakapan ini, tetapi bagi pendidikan saya itu momen seperti titik balik

    • Apakah fakta bahwa ada satu algoritma waktu linear menunjukkan adanya algoritma waktu linear yang lebih cepat? Kalau tidak, apa manfaat yang didapat dari pengetahuan itu?
      Bisa juga berpikir, “karena kita sudah tahu ada suatu algoritma, mungkin ada algoritma yang lebih cepat.” Mengapa keberadaan algoritma O(n) menjadi sinyal yang lebih kuat daripada keberadaan algoritma O(n log n)?
    • Sepertinya saya mempelajari algoritma ini di tahun ke-4 ilmu komputer. Seperti yang dikatakan, sisi teoretisnya juga dibahas, tetapi algoritma ini juga dipakai sebagai contoh untuk menunjukkan bahwa dalam kebanyakan kasus nyata, algoritma linear yang lambat tidak lebih cepat daripada algoritma n log n yang cepat
      Kalau tidak salah faktor konstanta algoritma ini sekitar 22, meski mungkin juga algoritma terkait

  • Salah satu hal menarik dari algoritma median-of-medians adalah daftar penulisnya benar-benar bertabur bintang
    Manuel Blum - pemenang Turing Award 1995
    Robert Floyd - pemenang Turing Award 1978
    Ron Rivest - pemenang Turing Award 2002
    Bob Tarjan - pemenang Turing Award 1986 sekaligus penerima pertama Nevanlinna Prize pada 1982
    Vaughan Pratt - satu-satunya dalam daftar yang bukan pemenang Turing Award, tetapi ia profesor emeritus Stanford, memimpin proyek SUN sebelum menjadi Sun Microsystems, berperan penting pada masa awal Sun sebagai kepala riset dan perancang logo Sun, serta meninggalkan banyak hal keren seperti sertifikat primalitas Pratt
    Empat Turing Award independen plus SPARCstation, semuanya ada di makalah ini

    • Pertanyaan wawancara untuk developer frontend pemula: “Dalam 30 menit ke depan, reproduksikan karya empat pemenang Turing Award. Anda punya papan tulis kotor dan spidol kering. Waktunya dimulai sekarang”
    • Tautan langsung bagi yang ingin membaca makalah aslinya: https://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf
      Daftar penulisnya memang mengesankan
    • Karya keren Pratt lainnya adalah Pratt parsing. Diskusi HN: https://news.ycombinator.com/item?id=39066465
      “P” dalam algoritma KMP juga Pratt

  • return l[len(l) / 2]
    Saya bukan ahli Python, tapi bukankah operator / di Python mengembalikan bilangan floating-point? Mengapa tidak memakai pembagian bilangan bulat // alih-alih memakai floating-point sebagai indeks array?
    Mungkin tidak jadi masalah kecuali array-nya sangat besar, tapi tetap saja cukup terasa sebagai code smell. Kalau masih pemula Python dan belum tahu dua operator itu berbeda, mungkin bisa dimaklumi, tetapi di tulisan itu ada kode yang lebih aneh lagi: di satu cabang memakai pembagian bilangan bulat, di cabang lain memakai pembagian floating-point
    def quickselect_median(l, pivot_fn=random.choice):
    if len(l) % 2 == 1:
    return quickselect(l, len(l) // 2, pivot_fn)
    else:
    return 0.5 * (quickselect(l, len(l) / 2 - 1, pivot_fn) +
    quickselect(l, len(l) / 2, pivot_fn))
    Sudah ada 50 komentar dan sepertinya tak ada yang melihat ini, jadi prasangka saya yang sudah ada tentang rata-rata kualitas kode Python malah makin kuat

    • Temuan bagus. Di Python 2 hanya ada satu operator, tetapi di Python 3 keduanya dibedakan
      Saya kira mengindeks array dengan floating-point akan memunculkan exception
    • Saya setuju itu code smell. Namun karena ini tulisan tentang algoritma, menilainya dari kualitas kode rasanya tidak sepenuhnya adil
      Mereka memilih bahasa pemrograman sungguhan yang terlihat seperti pseudocode alih-alih pseudocode, dan untuk tujuan penjelasan mungkin kodenya berjalan baik

  • Saya sangat menikmati membaca artikel aslinya, tetapi bagian “jika pada setiap langkah memilih elemen terbesar sebagai pivot, bisa menjadi O(n²) alih-alih O(n)” terasa mengganjal
    Jika khawatir dengan input adversarial, data bisa di-shuffle dulu dalam O(n) untuk mencegah hal itu dipaksakan. Jika datanya terlalu besar untuk di-shuffle, cukup acak sekali saat bucket sudah mengecil ke ukuran yang bisa di-shuffle
    Jika sudah di-shuffle, probabilitas menjamin kasus terburuk praktis tidak terjadi. Kalau ada yang bilang “secara teknis” itu mungkin, saya akan menjawab bahwa “secara teknis” penyerang juga bisa menebak semua bit private key 256-bit
    Dunia kita dibangun di atas probabilitas. Semua private key dilindungi oleh ketidakmungkinan matematis bahwa seseorang dapat menebaknya dengan tepat
    Dari yang saya baca, setelah shuffle quickselect secara praktis adalah O(n)

    • Pivot-nya sudah dipilih secara acak dengan random sendiri, jadi saya tidak melihat mengapa shuffle akan lebih membantu
      Tetap saja, jika random-nya bisa dipercaya, probabilitas waktu eksekusi melebihi O(n) sangat rendah
    • Pernyataan “jika khawatir dengan input adversarial, shuffle dulu data dalam O(n) akan menjamin ini” bukan menjamin menghindari kasus terburuk, melainkan menghilangkan kemungkinan kasus terburuk dapat dipaksakan

  • Floyd-Rivest juga menyelesaikan pekerjaan itu. Kalau ingatan saya benar, sedikit lebih efisien
    Namun saya tidak pernah benar-benar memahami cara kerjanya
    https://en.m.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm

  • Saat memilih elemen ke-n, jika n sangat kecil atau sangat besar, median-of-medians mungkin bukan pilihan terbaik
    Sebagai gantinya bisa memakai pivot yang bias seperti [1], atau metode yang saya sebut “ke-j dari ke-k”. Floyd-Rivest juga bisa mempercepatnya
    Ada proyek hobi yang throughput-nya 1,2–2,0× dibanding quickselect yang diimplementasikan dengan baik: https://github.com/koskinev/turboselect
    Saya tertarik jika ada referensi tentang algoritma seleksi in-place serbaguna yang cepat
    [1] https://doi.org/10.4230/LIPIcs.SEA.2017.24

  • Bisa juga memakai algoritma streaming yang dapat menghitung perkiraan kuantil arbitrer tanpa menyimpan seluruh data di memori

    • Ini pendekatan yang bagus jika perkiraan dapat diterima. Namun segera muncul pertanyaan-pertanyaan yang tidak nyaman
      Apakah perhitungan aproksimasi dapat diterima? Asumsi apa tentang data yang diperlukan untuk menetapkan batas galat? Bagaimana memverifikasi bahwa asumsi itu tetap valid?
      Secara pribadi, sampai ada situasi yang benar-benar mengharuskan mempertimbangkan pendekatan aproksimasi median streaming, saya cenderung memilih algoritma quickselect yang ada di artikel asli
    • Pasti pernah ada situasi ketika algoritma kuantil streaming akan berguna. Ada referensi yang layak dibaca?