En Sevdiğim Algoritma: Doğrusal Zamanda Medyan Bulma (2018)

 (rcoh.me)
2 puan yazan GN⁺ 2024-07-26 | 1 yorum | WhatsApp'ta paylaş
  • Medyan, sıralama yapıldığında kolayca bulunabilir; ancak sıralama maliyeti nedeniyle tek bir eleman seçme probleminde bile O(n log n) sınırına takılır
  • quickselect, yalnızca gerekli tarafı özyinelemeli olarak arayarak kth elemanı ya da medyanı ortalama O(n) sürede bulabilir
  • Rastgele pivot pratikte iyi çalışır; ancak sürekli kötü pivot seçilirse her seferinde yalnızca bir eleman elenir ve süre O(n²) seviyesine kadar kötüleşir
  • median-of-medians, 5'li grupların medyanlarından yeniden bir medyan seçerek en kötü durumda bile elemanların en az %30'unun elenmesini sağlar
  • Gerçek uygulamalarda pivot hesaplama maliyeti yüksek olabilir; bu yüzden C++ standart kütüphanesindeki gibi quickselect ile heapselect'i birleştiren introselect daha pratik bir tercih olabilir

Sıralamayla medyan bulmanın sınırları

  • En basit medyan hesaplama yöntemi, listeyi sıraladıktan sonra orta indeksteki değeri seçmektir
  • Tek uzunluklu listede ortadaki eleman döndürülür, çift uzunluklu listede ise ortadaki iki elemanın ortalaması alınır
  • Karşılaştırma tabanlı sıralamanın en iyi zaman karmaşıklığı O(n log n) olduğundan, bu yöntemin çalışma süresine de sıralama hâkim olur
  • Kodunun basit olması avantajdır, ancak yalnızca tek bir medyan bulmak için gerekenden fazla iş yapar

Ortalama O(n) sağlayan quickselect

  • quickselect, Tony Hoare tarafından geliştirilen özyinelemeli bir algoritmadır; yalnızca medyanı değil, listenin herhangi bir kth elemanını da bulabilir
  • Temel akış, listeyi bir pivot etrafında böldükten sonra yalnızca kth elemanın bulunduğu tarafı aramaya devam etmektir
    • Listeden bir pivot seçilir
    • Liste, pivottan küçük veya eşit elemanlar ile pivottan büyük elemanlar olarak ayrılır
    • Aranan kth elemanın hangi tarafta olduğuna karar verilip yalnızca o alt listede özyinelemeli çağrı yapılır
    • Sağ alt listeye inilirse, dışarıda bırakılan sol taraftaki eleman sayısı kadar k değeri ayarlanır
  • Örnek liste [9,1,0,2,3,4,6,8,7,10,5] için uzunluk 11 olduğundan 6. en küçük eleman aranır; pivotlara göre aralık daraltılarak sonunda 5 döndürülür
  • quickselect_median, listenin uzunluğu tekse tek bir orta indeksi quickselect ile bulur; çiftse ortadaki iki indeksi bulup ortalamalarını alır
  • Pivot listeyi yaklaşık iki eşit parçaya bölerse toplam iş miktarı n + n/2 + n/4 + ... = 2n olur ve süre O(n) olur

En kötü durumdan kaçınmak için iyi bir pivot gerekir

  • quickselect'in ortalama O(n) olması, pivot seçiminin yeterince iyi olmasına bağlıdır
  • Her adımda maksimum değeri pivot seçmek gibi kötü şanslı bir durumda, her aşamada yalnızca bir eleman elenir ve süre O(n²) olur
  • En kötü durumda bile doğrusal zamanı garanti etmek için, quickselect'e doğrusal zamanda yeterince iyi bir pivot vermek gerekir
  • Bu pivot seçme algoritması 1973'te Blum, Floyd, Pratt, Rivest ve Tarjan tarafından geliştirildi; ilgili makale 1973 paper bağlantısında yer alıyor

median-of-medians ile pivot seçimi

  • median-of-medians, quickselect'in kullanacağı iyi bir pivot seçme prosedürüdür
  • Uygulama akışı şöyledir
    • Eleman sayısı 5'ten azsa mevcut sıralama tabanlı medyan fonksiyonu kullanılır
    • Liste 5'erli gruplara ayrılır
    • 5 elemana ulaşmayan eksik grup, basitleştirme amacıyla atılır
    • Her grup sıralanır ve indeks 2'deki medyanlar toplanır
    • Toplanan medyanlar listesinin medyanı yeniden bulunup pivot olarak döndürülür
  • Her grubun boyutu sabit 5 olduğundan, grup başına sıralama sabit zaman sayılır ve toplamda işlem O(n) olur
  • Medyanların medyanını bulmak için yapılan özyinelemeli çağrı, boyutu n/5 olan bir alt problem olarak analize dahil edilir

Neden en az %30 elenebilir?

  • 5'li grupları sıralayıp sütunlar halinde düşündüğümüzde ve bu sütunların medyanlarını tekrar sıralayıp medyanların medyanını seçtiğimizde, pivotun kalitesi analiz edilebilir
  • Pivot mümkün olduğunca öne kaymış en kötü durumda bile, belirli bir bölgedeki elemanların pivottan küçük ya da büyük olduğu garanti edilir
  • Her sütundan 3 eleman alıp sütunların yarısını dikkate aldığımızda, en az 3/5 * 1/2 * n = 3/10 n eleman elenebilir
  • Eleme garanti oranı: {p:30}
  • Toplam çalışma süresi şu özyineleme bağıntısıyla ifade edilir
T(n) = n + T(n/5) + T(7n/10)
  • Burada n bölme işlemini, T(n/5) median-of-medians hesaplamasını, T(7n/10) ise quickselect'in özyinelemeli aramasını temsil eder
  • Bu bağıntıda iki özyineleme terimi olduğundan basit Master teoremi doğrudan uygulanamaz; tümevarım daha sezgisel bir ispat yöntemidir

Birleşimin sonucu: doğrusal zamanda medyan bulma

  • quickselect, yeterince iyi bir pivot verildiğinde medyanı doğrusal zamanda bulabilir
  • median-of-medians, quickselect'in ihtiyaç duyduğu iyi pivotu O(n) sürede seçebilir
  • İki algoritma birleştirildiğinde, medyanı veya listenin n'inci elemanını doğrusal zamanda bulan bir algoritma elde edilir

Gerçek uygulamalardaki tercih

  • Pratikte rastgele pivot seçimi neredeyse her zaman yeterince iyidir
  • median-of-medians da doğrusal zamanlıdır, ancak pratikte pivot hesaplama maliyeti yüksek olduğu için yavaş olabilir
  • C++ standart kütüphanesi introselect kullanır; bu yaklaşım heapselect ile quickselect'i birleştirir ve O(n log n) üst sınıra sahiptir
  • introselect genellikle hızlıdır; ancak üst sınırı kötü bir algoritmayla başlayıp etkili bir pivot seçemediğinde daha yavaş ama üst sınırı daha iyi olan bir algoritmaya geçer
  • quickselect fonksiyonunun incelediği eleman sayısına dair karşılaştırmada, deterministik pivot neredeyse her zaman rastgele pivottan daha az elemanı dikkate aldı; ancak bu karşılaştırmaya median-of-medians hesaplama maliyeti dahil değil
  • 2017 tarihli new paper, median-of-medians yaklaşımını diğer seçim algoritmalarıyla rekabet edebilir hâle getiren bir çalışmayı anlatıyor

İlgili okumalar

1 yorum

 
GN⁺ 2024-07-26
Hacker News yorumları

  • Yaklaşık 4 yıl önce birkaç medyan algoritmasını karşılaştırmıştım; yazı beklediğimden çok daha uzun olmuştu :)
    https://danlark.org/2020/11/11/miniselect-practical-and-generic-selection-algorithms/

    • Bunların arasında arg-median, yani medyana sahip indeksi döndürecek şekilde kolayca değiştirilebilecek bir algoritma var mı?

  • 10–15 yıl önce, çok kilobaytlık günlük girdilerinden ayrıştırılan milyarlarca değerin medyanını düzenli olarak bulmam gerekiyordu. O dönemde büyük ölçekli işleme için MapReduce kullanıyorduk ve bu hacimde veri için yalnızca doğrusal zaman değil, mümkünse tek geçişte birden fazla makineye dağıtılabilen bir yöntem gerekiyordu
    Verinin hassasiyetini ve aralığını bilmek işe yarıyordu. Değerler tam sayı milisaniye cinsinden sürelerdi, bu yüzden negatif değillerdi; ayrıca 90. yüzdeliğin 1 saniyeden çok daha küçük olduğunu da biliyorduk
    Normalde medyan bulmak sıralamaya benzer bir iş gerektirir, ama bu koşullarda bucket sort mümkün hale geliyor. Anahtarı tam sayı milisaniye süresi, değeri de görülme sayısı olan bir sözlük, yani histogram oluşturmak yeterli
    Maksimum süreyi bilmediğimiz için sözlük boyutunun patlamasını önlemek adına 999 ms’yi aşan tüm değerleri 999 ms kovasına koyduk; böylece 0–999 anahtarları ve değerleriyle toplamda yaklaşık 2000 tam sayıyla sınırlı kaldı. Bu kısım klasik bucket sort’tan farklıydı; MapReduce ile dağıtılsa bile tek geçişte çok kolay işlenebiliyordu, ardından medyanı histogramdan çıkarmak yeterliydi

    • Gerçekten milyarlarca değerin tam medyanına mı ihtiyacınız vardı? Yoksa %49,9 ile %50,1 arasındaki bir değer yeterli miydi? İkincisiyse çok daha kolay. Rastgele ve eşit dağıtılmış biçimde 10.000 örnek alıp onların medyanını kullanabilirsiniz
      10.000 sayısını gelişigüzel verdim, ama istenen güven düzeyi için gereken örnek sayısı istatistiksel olarak hesaplanabilir ve sanırım o kadar da büyük olmaz
    • Emin değilim ama dışarıdan bakınca Prometheus’un içeride yaptığı şeye benziyor
      Uğraştığım bazı sistemlerde Prometheus gecikme için yaklaşık 10 saniyelik bir sınır koyuyormuş gibi davranıyordu. Bu yüzden o sınırı aşan istekler gerçekte daha uzun sürse bile hepsi 10 saniye olarak kaydediliyordu. İlginç
    • Acaba kullanılabilirlik metriği oluşturduğun bir iş miydi ve o sırada stajyer miydin? O sistem kulağa, şey, çok tanıdık geliyor
    • Neden 0…999 anahtarlı bir sözlük kullandığını anlamadım. 0…999 ile indekslenen bir dizi kullansana?

  • 2017’de median-of-medians yaklaşımını diğer seçim algoritmalarıyla rekabet edebilir hale getiren yeni bir makale çıktığına ve bunu makalenin yazarı Andrei Alexandrescu’nun bildirdiğine dair bir not var
    Kendisi 2016’da kendi algoritması hakkında bir sunum da yapmıştı. Sunumları eğlenceli biri, şiddetle tavsiye ederim
    There's Treasure Everywhere - Andrei Alexandrescu
    https://www.youtube.com/watch?v=fd1_Miy1Clg

    • Andrei Alexandrescu harika biri. 2000 civarında lock-free, wait-free algoritmalar üzerine bir sunum yapmıştı; o dönem devasa bir C++ endüstriyel kontrol ağ projesinde bunu hemen uygulamıştım
      Yazılım kullanan biriyseniz Andrei’nin bulabildiğiniz tüm yazılarını ve sunumlarını dinleyip okumanızı öneririm. Bu sunum da gerçekten bir hazine
    • Bilgisayar bilimi ölçütlerine göre bile oldukça çok yönlü bilgili biri olması şaşırtıcı. Onu template metaprogramming ile tanıyordum; burada ise programlama dillerinden algoritmalara doğru kayıyor

  • Lisans döneminde median-of-medians quickselect algoritmasını öğrenmiştim ve gerçekten çok etkilenmiştim. Kendim uyguladım ama korkunç derecede yavaştı. Çalışma süresi doğrusal artıyordu, ama bunun anlamlı olması için listede en az milyarlarca öğe olması gerekiyordu
    Bunu yüksek lisans öğrencisi bir arkadaşımla konuşurken bana şöyle bir şey demişti: “Yavaş olabilir, ama önemli olan sıralanmamış bir listede seçimin O(n) zamanda yapılabildiğini kanıtlaması. Bir zamanlar bunun mümkün olup olmadığını bile bilmiyorduk; artık mümkün olduğunu bildiğimize göre daha hızlı doğrusal algoritmalar da olabilir.”
    O kadar basit ama derin bir dersti ki neredeyse yüksek lisansa başvuracaktım. O arkadaşım bu konuşmayı hatırlıyor mu bilmiyorum, ama benim eğitimimde dönüm noktası gibi bir andı

    • Bir doğrusal zaman algoritmasının var olması, daha hızlı bir doğrusal zaman algoritmasının varlığına işaret eder mi? Etmiyorsa, bu bilgiden elde edilen kazanç nedir?
      “Zaten bir algoritmanın var olduğunu bildiğimize göre daha hızlı bir algoritma da olabilir” diye de düşünülebilir. O(n) bir algoritmanın varlığı neden O(n log n) bir algoritmanın varlığından daha güçlü bir sinyal olsun?
    • Sanırım bu algoritmayı bilgisayar biliminin 4. yılında öğrenmiştim. Söylediğin gibi teorik yönü de ele alınmıştı, ama gerçek dünyanın çoğu durumunda yavaş bir doğrusal algoritmanın hızlı bir n log n algoritmasından hızlı olmadığını gösteren bir örnek olarak da kullanılmıştı
      Bu algoritmanın sabit katsayısı 22 civarındaydı diye hatırlıyorum; gerçi ilgili başka bir algoritma da olabilir

  • median-of-medians algoritmasının ilginç yanlarından biri, yazar listesinin tamamen yıldızlar geçidi olması
    Manuel Blum - 1995 Turing Ödülü sahibi
    Robert Floyd - 1978 Turing Ödülü sahibi
    Ron Rivest - 2002 Turing Ödülü sahibi
    Bob Tarjan - 1986 Turing Ödülü sahibi ve 1982'de ilk Nevanlinna Ödülü sahibi
    Vaughan Pratt - listedeki Turing Ödülü sahibi olmayan tek kişi; ama Stanford'da emeritus profesör, Sun Microsystems olmadan önce SUN projesine liderlik etti, Sun'ın ilk dönemlerinde araştırma direktörü ve Sun logosunun tasarımcısı olarak önemli rol oynadı; Pratt asallık sertifikaları gibi pek çok havalı şey de bıraktı
    Dört bağımsız Turing Ödülü ve üstüne bir de SPARCstation; bu makalede hepsi var

    • Yeni mezun frontend geliştirici mülakat sorusu: “Önümüzdeki 30 dakika içinde dört Turing Ödülü sahibinin çalışmasını yeniden üretin. Kirli bir beyaz tahtanız ve kurumuş bir kaleminiz var. Süreniz şimdi başlıyor”
    • Orijinal makaleyi okumak isteyenler için doğrudan bağlantı: https://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf
      Yazar listesi kesinlikle etkileyici
    • Pratt'in diğer havalı çalışmalarından biri de Pratt parsing. HN tartışması: https://news.ycombinator.com/item?id=39066465
      KMP algoritmasındaki “P” de Pratt

  • return l[len(l) / 2]
    Python uzmanı değilim ama Python'da / operatörü kayan noktalı sayı döndürmüyor mu? Dizi indeksi olarak kayan noktalı sayı kullanmak yerine tamsayı bölmesi olan // neden kullanılmıyor?
    Çok büyük bir dizi değilse sorun olmayabilir, ama yine de ciddi bir kod kokusu var. Python'da yeniysen ve iki operatörün ayrı olduğunu bilmiyorsan geçilebilir; ama yazıda bir dalda tamsayı bölmesi, diğer dalda kayan noktalı bölme kullanan daha da tuhaf kod da var
    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))
    50 yorum olmuş ve kimse bunu görmemiş gibi; bu da ortalama Python kod kalitesi hakkındaki mevcut önyargılarımı sadece güçlendiriyor

    • İyi yakalamışsın. Python 2'de tek bir operatör vardı, ama Python 3'te ikisi ayrıldı
      Bir diziyi kayan noktalı sayıyla indekslemenin istisna fırlatacağını düşünüyorum
    • Kod kokusu olduğuna katılıyorum. Yine de bu bir algoritma yazısı olduğu için kod kalitesiyle yargılamak tam olarak adil değil bence
      Sözde kod yerine sözde kod gibi görünen gerçek bir programlama dili seçilmiş; açıklama amacı için de muhtemelen iyi çalışan bir kod

  • Orijinal yazıyı gerçekten keyifle okudum ama “her adımda en büyük elemanı pivot seçerseniz O(n) yerine O(n²) olabilir” kısmı takıldı
    Kötücül girdiden endişe ediyorsanız veriyi önce O(n)'de shuffle etmek bunun zorla gerçekleşmesini engelleyebilir. Veri shuffle etmek için çok büyükse, bucket'lar shuffle edilebilir boyuta indiğinde bir kez karıştırmak yeterli olur
    Shuffle yaptıysanız olasılık, en kötü durumun pratikte gerçekleşmeyeceğini garanti eder. Biri “teknik olarak” mümkün derse, ben de “teknik olarak” bir saldırgan 256 bitlik özel anahtarın tüm bitlerini doğru tahmin edebilir diye cevap veririm
    Dünyamız olasılıklar üzerine kurulu. Tüm özel anahtarlar, birinin onları tam olarak tahmin edemeyeceğine dair matematiksel imkânsızlık tarafından korunuyor
    Benim okuduğum kadarıyla, shuffle sonrası quickselect pratikte O(n)

    • Pivotu zaten kendi rastgeleliğiyle rastgele seçiyor; bu yüzden shuffle'ın neden daha fazla yardımcı olduğunu bilmiyorum
      Yine de rastgeleliğe güvenebiliyorsak O(n)'yi aşan çalışma süresi görme olasılığı çok düşük
    • “Kötücül girdiden endişe ediyorsanız veriyi önce O(n)'de shuffle etmek bunu garanti eder” demek, en kötü durumdan kaçınmayı garanti etmek değil; en kötü durumu zorla oluşturma olasılığını ortadan kaldırmak demek

  • Floyd-Rivest de aynı işi başarıyor. Yanlış hatırlamıyorsam biraz daha verimli
    Ama ben nasıl çalıştığını bir türlü anlayamadım
    https://en.m.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm

  • n'inci elemanı seçerken n çok küçük ya da çok büyükse median-of-medians en iyi seçenek olmayabilir
    Bunun yerine [1]'deki gibi yanlı bir pivot kullanabilir ya da benim “k içinden j'inci” dediğim yöntemi uygulayabilirsiniz. Floyd-Rivest de hızı artırabilir
    İyi uygulanmış quickselect'e kıyasla 1,2~2,0 kat throughput veren bir hobi projem var: https://github.com/koskinev/turboselect
    Hızlı, genel amaçlı, in-place seçim algoritmaları hakkında kaynak varsa ilgilenirim
    [1] https://doi.org/10.4230/LIPIcs.SEA.2017.24

  • Tüm veriyi bellekte tutmadan da rastgele bir quantile'ın yaklaşık değerini hesaplayabilen streaming algoritmalar kullanabilirsiniz

    • Yaklaşık değere izin verebiliyorsanız harika bir yöntem. Ama kısa süre sonra rahatsız edici sorular ortaya çıkar
      Yaklaşık hesaplamaya izin verebilir misiniz? Hata sınırını belirlemek için veri hakkında hangi varsayımlar gerekir? Bu varsayımların geçerliliğini sürdürdüğünü nasıl doğrulayacaksınız?
      Şahsen streaming median yaklaşımı düşünmek zorunda kalacağım bir durum gelene kadar, orijinal yazıdaki quickselect algoritmasına yönelirim
    • Streaming quantile algoritmasının yararlı olacağı durumlar kesinlikle oldu. Önerebileceğiniz bir kaynak var mı?