Forum: D Programlama Dili RSS
Hızlı sıralama
Sayfa:  1  2  3  sonraki 
erdem (Moderatör) #1
Üye Tem 2009 tarihinden beri · 978 mesaj · Konum: Eskişehir
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Konu adı: Hızlı sıralama
D ile hızlı sıralama quick sort u en kolay nasıl yazardınız. Buradaki amacım Python'un olanakları ile D olanaklarını karşılaştırmak:

Örneğin Python için:
    sayilar = [1, 2, 3, 4, 5, 6]
    tekSayilar = [x for x in sayilar if x % 2 == 1]
Scheme gibi işlevsel dillerde bulunan lambda (D'de de sanırım isimsiz işlevler var) olanağını kullanabiliyorsunuz. Evet D ile hızlı sıralama algoritmasını (hazır işlevler kullanmadan) nasıl yazardınız.
acehreli (Moderatör) #2
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Python için süzme işlemi gösterdin. Hızlı sıralamaya biraz aşağıda geçeceğim.

Bu konularda kullanışlı olan iki olanak oluyor: Generator kavramı Python'da iç olanak olduğu halde D'deki aralık (range) kavramı kütüphanelerle gerçekleştirilmek durumunda. Ancak, aralıkların bütünüyle kütüphane olanağı olduğunu söylemek de yanlış olur çünkü foreach döngüsü InputRange aralığı kavramını tanır ve foreach ile rahatça kullanma olanağı sunar. O açıdan bakınca biraz da dilin iç olanağı kabul edilebilir.

Gösterdiğin kod D'de neredeyse aynı (Not: tek sayı karşılaştırmasınd ==1 yapılırsa eksi sayılarda yanlış sonuç verir):

import std.algorithm;
// ...
    immutable sayılar = [1, 2, 3, 4, 5, 6];
    auto tekSayılar = sayılar.filter!(x => x % 2)();

(Not: dmd'nin -property seçeneği kullanılmazsa sondaki boş parantezlere de gerek olmuyor. Bu konunun sonu nereye varacak bilmiyorum. Parantezsiz yazıma izin verilmeyeceğı söyleniyor ama bazı durumlarda çok da kullanışlı olduğu için herhalde hiç kalkmayacak.)

Yukarıdaki kod da Python'da olduğu gibi tembeldir. Yani sayılar sonsuz bir aralık bile olsa filter sonsuza kadar devam etmez, sayıları gerçekten kullanıldıklarında üretir.

Hızlı sıralama en iyi özyinelemeli olarak gerçekleştirilir. Ama isimsiz işlevler ve özyineleme bir araya gelemiyor çünkü bir isimsiz işlevin içinden kendisini çağırma olanağı yok (çünkü ismi yok :)).

Erdem hile yaptım diye bana kızacak ama ben hızlı sıralamayı şöyle gerçekleştirirdim: :)

import std.stdio;
import std.algorithm;
 
void hızlıSırala(T)(T[] elemanlar)
{
    if (elemanlar.length >= 2) {
        auto parçalar = partition3(elemanlar, elemanlar[$ / 2]);
        hızlıSırala(parçalar[0]);
        // parçalar[1] pivot'a eşit olanları kapsıyor; zaten doğru yerdeler
        hızlıSırala(parçalar[2]);
    }
}
 
void main()
{
    auto sayılar = [ 10, 40, 0, -3, 7, 8, 11, 100, -5, 1 ];
    hızlıSırala(sayılar);
    writeln(sayılar);
}

Ali
erdem (Moderatör) #3
Üye Tem 2009 tarihinden beri · 978 mesaj · Konum: Eskişehir
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
acehreli:
Gösterdiğin kod D'de neredeyse aynı (Not: tek sayı karşılaştırmasınd ==1 yapılırsa eksi sayılarda yanlış sonuç verir):

Evet Python ile doğru sonuç veriyor. Ancak D'de yanlış sonuç veriyor.

acehreli:
Parantezsiz yazıma izin verilmeyeceğı söyleniyor ama bazı durumlarda çok da kullanışlı olduğu için herhalde hiç kalkmayacak.

Bence de kaldırılsın. Hatta Python'un yazım biçimi çok harikayken D'yi bu konuda çok başarılı bulduğumu söyleyemeyeceğim.

=>!() Bu kadar karakterin yazılması biraz zor oluyor. Ya da artık ben biraz tembelleşmeye başladım.

acehreli:
Erdem hile yaptım diye bana kızacak ama ben hızlı sıralamayı şöyle gerçekleştirirdim: :)

        auto parçalar = partition3(elemanlar, elemanlar[$ / 2]);

O zaman yarısı çözülmüş oluyor tabi  ;-)

Ben o kullanıma bakınca ortadan bölüyor diye düşünmüştüm ama örneğin [5, 3, 25, 6, 10, 17, 1, 2, 18, 8] gibi bir dizide böyle bir sonuç çıktı.

[2, 3, 8, 6, 10, 5, 1], [17], [18, 25]

Bu arada güzel bir örnek olmuş oldu.

acehreli:
        // parçalar[1] pivot'a eşit olanları kapsıyor; zaten doğru yerdeler 

Katılır mısınız bilmiyorum ama pivot için mihenk demişler. Ölçü, ölçüt, kriter anlamında.

Bir de mihenk taşı var.Altın veya gümüş üzerine sürüldüğü takdirde, bıraktığı çizgilerden bu madenlerin saflık dereceleri anlaşılıyormuş.
erdem (Moderatör) #4
Üye Tem 2009 tarihinden beri · 978 mesaj · Konum: Eskişehir
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
    auto küçük = sayılar[1..$].filter!(x => x < sayılar[0])();
Benim düşündüğüm çözüm de bu şekilde. Ancak bunu bir int[]'e nasıl çevireceğimi bilmiyorum.
acehreli (Moderatör) #5
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Yani 'küçük' filter'ın sonucunu tutan (veya "üreten") tembel bir aralıktır. Onu hevesli bir biçimde diziye dönüştürmek istiyoruz:

import std.array;
// ...
    küçük.array();
    // veya: array(küçük); 

Ali
erdem (Moderatör) #6
Üye Tem 2009 tarihinden beri · 978 mesaj · Konum: Eskişehir
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Benim bulduğum çözüm de bu şekilde:
import std.stdio;
import std.algorithm;
import std.array;
 
T[] hızlıSırala(T)(T[] dizi)
{
    if (dizi.length > 2) {
        auto küçük = dizi[1..$].filter!(x => x < dizi[0])();
        auto büyük = dizi[1..$].filter!(x => x >= dizi[0])();
        return (hızlıSırala(array(küçük)) ~ dizi[0] ~ hızlıSırala(array(büyük)));
    }
    return dizi;
}
 
void main()
{
    auto sayılar = [5, 3, 25, 6, 10, 17, 1, 2, 18, 8];
    writeln(hızlıSırala(sayılar));
}
Ama çalışmasına şaşırdım aslında. Sabah dmd'nin eski bir sürümü ile derlediğimde sonsuz bir döngüye girmişti.
Avatar
Salih Dinçer #7
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Temel bir tartışma konusu olmuş; Ali hocamın cevabı da çok leziz...:)

Çünkü parametre olarak verilen dizinin içeriğini küçükten büyüğe sıralayarak değiştiriyor. Sanırım bunu yaparken dilimlerden de faydalanıyor olmalı; belki de değil?

Öyle ya, bölümlendirme işlevini hayal edersek, dilimlerin boyutları değişeceğinden hız açısından zararı bile olabilir. Çünkü oluşturulan dilimlerden soldaki (ilk yarı), sağdaki (son yarı) dilimden ister istemez eleman alabilir. Yani sağdaki dilimin elemanları mihenkten (pivot) küçük olması durumunda ikili sıralama (binary sort) gereği sola geçmeli. Bu durumda sağdaki dilimin ortasından bir eleman eksilebileceğinden onun da bir dilim olması anlamsız olacaktır.

Özetle, bu değerlendirmenin ışığında dilim kullanılmasa gerek. Ne dersiniz?
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #8
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Salih, gerçekten "dilim" mi demek istedin yoksa aralık mı? Çünkü zaten hem benimki hem de Erdem'inki dilim alıyor.

Erdem'inkinin daha yavaş olacağını beklerim çünkü her array() çağrısı hevesli bir biçimde yeni bir dizi oluşturuyor. Dizilerin uç uca eklenmelerinden bazıları da elemanların yeni yere taşınmasını gerektirebilir.

Benimkinde ise hiç dizi kopyalama yok. Elemanlar aynı dizi içinde değiş tokuş ediliyorlar. O yüzden ona in-place algoritma denir.

Ali
erdem (Moderatör) #9
Üye Tem 2009 tarihinden beri · 978 mesaj · Konum: Eskişehir
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
acehreli:
Erdem'inkinin daha yavaş olacağını beklerim çünkü her array() çağrısı hevesli bir biçimde yeni bir dizi oluşturuyor. Dizilerin uç uca eklenmelerinden bazıları da elemanların yeni yere taşınmasını gerektirebilir.

Ali bey ben de tam onu soracaktım. Burada bahsettiğiniz hız farkı mihenk olarak seçilen değer ile ilgili değil sanırım. Çünkü baştan, sondan, rastgele seçmenin performansı düşüreceğini söylemişler. En uygun yöntem bir baştan bir ortadan bir sondan değer alıp bunların ortalamasını (medyan) bulmakmış.

Benim hatırladığım kadarıyla dilimler bir referans gerçekleşmesi değil miydi. array() işlevini kullanmadan sadece dilimlerle yapsaydık nasıl olurdu.

Aynı durum Rosetta Code'daki D uygulamasında da da vardı sanırım. Ama ben hala D'deki dilimler referans olduğuna göre neden yavaş çalışıyor tam olarak anlamış değilim.
acehreli (Moderatör) #10
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
erdem:
Burada bahsettiğiniz hız farkı mihenk olarak seçilen değer ile ilgili değil sanırım.

Onunla ilgili değil. Ama mihenk olarak ilk elemanın seçilmesinin uygun olmadığı da bilinir. Ben de bir çok qsort gerçekleştirmesi gibi ortadaki elemanı seçiyordum.

Benim hatırladığım kadarıyla dilimler bir referans gerçekleşmesi değil miydi.

Evet, var olan ve çoğunlukla çalışma ortamının (D runtime) sahip olduğu elemanlara erişim sağlayan araçlardır.

array() işlevini kullanmadan sadece dilimlerle yapsaydık nasıl olurdu.

Sadece dilimlerle yapabilmek için yine de elemanların bir yerde bulunmaları gerekirdi. Dilimler de onlara erişim sağlıyor olurlardı. O elemanlar nerede olsa? En iyisi baştan verilen elemanlardır. Sıralamayı onun üzerinde yapsak hiç yeni bellek ayırmak gerekmez.

array() heveslidir. Bunu çok daha basit bir örnekte görelim:

import std.stdio;
import std.algorithm;
 
void main()
{
    auto sayılar = [ 1, 2, 3, 4, 5 ];
    auto tekler = sayılar.filter!(x => x % 2)();
    writeln(tekler);
}

O koddaki tekler'in bir dizi veya dilim olmadığını görüyor muyuz? filter süzme işini hevesli bir biçimde hemen yapmaz. O, yalnızca süzme işini gerçekleştirecek olan bir aralık döndürür. sayılar'ın uzunluğu sonsuz bile olsa filter hemen o arılığı üretir ve döner.

writeln de InputRange'lerle işlemeyi bildiği için filter'ın döndürdüğü aralığı popFront() yapa yapa ilerletir ve eline geçen tek sayıları yazdırır.

Buraya kadar güzel: Tembellik harika! :)

Sen ise o tembel aralığın ürettiği elemanlardan array() ile bir dizi oluşturuyorsun. array, InputRange'i tüketene kadar eleman çeker ve bir dizinin sonuna ekler.

Birinci sorun o: elemanlar teker teker bir dizinin sonuna eklenecekler. Bu işlem sırasında kapasite yetmedikçe daha büyük yer ayrılacak ve eklemeler orada devam edecek, vs.

Ondan sonra küçük ve büyük dizilerini de ayrıca birleştiriyorsun. Eğer yine kapasite yeterli değilse yine yeni bir yere kopyalanacaklar demektir.

(Elemanların nerede durduklarını dilimlerin .ptr niteliği ile görebiliriz.)

Phobos'un partition3 işlevi ise hiç yer ayırmadan kendisine verilen elemanları değiş tokuş ederek gittikçe doğru sırayı buluyor. Döndürdüğü şey üç dilimden oluşan bir çokuzludur: mihenkten küçük olanlar, mihenge eşit olanlar, ve mihenkten büyük olanlar.

Dilimlerin referanslıklarının yararı partition3'te görülüyor: Eleman kopyalama yok; yalnızca o bölümlere eriştiren dilimler döndürüyor.

Ali
Avatar
Salih Dinçer #11
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Yanıtlanan mesaj #8
acehreli:
Salih, gerçekten "dilim" mi demek istedin yoksa aralık mı? Çünkü zaten hem benimki hem de Erdem'inki dilim alıyor.

Yazdığım gibi aralık demek istememiştim...

acehreli:
Elemanlar aynı dizi içinde değiş tokuş ediliyorlar. O yüzden ona in-place algoritma denir.

Hmm, bu durumda çok işlemci gücü harcıyor olmalı!
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Bu mesaj Salih Dinçer tarafından değiştirildi; zaman: 2012-09-13, 13:40.
acehreli (Moderatör) #12
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Salih Dinçer:
acehreli:
Elemanlar aynı dizi içinde değiş tokuş ediliyorlar. O yüzden ona in-place algoritma denir.

Hmm, bu durumda çok işlemci gücü harcıyor olmalı!

Neden öyle diyorsun? Elemanlar eninde sonunda bir biçimde sıraya sokulacaklar. Bu işi hiç ek bellek ayırmadan yapmak daha çabuk olmaz mı?

Yalnızca sonuç için ek yer ayırsak bile asıl elemanların onun içine kopyalanması gerekecektir. O iş de tek adımda olamaz çünkü elemanların sonuçtaki yerlerini bilmiyoruz.

Ali
Avatar
Salih Dinçer #13
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Bilemiyorum, belki de denemek lazım. Tabi bu bir tercih meselesi. Eğer belleğin sıralanacak veri için yeterli olmadığı ama işlemci gücünün önemsiz olduğu durumda bu yöntem tercih edilebilir. Sanırım ilk algoritmada şu aşağıda sıraladığım işlemler 3 defa gerçekleşmekte:
import std.algorithm, std.stdio;
 
void main() {
  auto dizi = [5, 3, 25, 6, 17, 1, 2, 18, 8];
  dizi.writeln;
 
  foreach(i; 0..4) {
    partition3(dizi, dizi[$/2]);
    dizi.writeln;
   
    auto sol0 = dizi[0..$/2];
    sol0.write;
    auto sağ0 = dizi[$/2..$];
    sağ0.writeln;
   
    partition3(sol0, sol0[$/2]);
    partition3(sağ0, sağ0[$/2]);
    dizi.writeln;
 
    auto sol1 = sol0[0..$/2];
    auto sol2 = sol0[$/2..$];
    auto sağ1 = sağ0[0..$/2];
    auto sağ2 = sağ0[$/2..$];
 
    partition3(sol1, sol1[$/2]);
    partition3(sol2, sol2[$/2]);
    partition3(sağ1, sağ1[$/2]);
    partition3(sağ2, sağ2[$/2]);
    dizi.writeln;
  }
}
Çıktısı:
[5, 3, 25, 6, 17, 1, 2, 18, 8]
[2, 3, 8, 6, 5, 1, 17, 18, 25]
[2, 3, 8, 6][5, 1, 17, 18, 25]
[6, 3, 2, 8, 5, 1, 17, 18, 25]
[3, 6, 2, 8, 1, 5, 17, 18, 25]
[1, 6, 2, 8, 25, 5, 17, 18, 3]
[1, 6, 2, 8][25, 5, 17, 18, 3]
[1, 2, 8, 6, 3, 5, 17, 18, 25]
[1, 2, 6, 8, 3, 5, 17, 18, 25]
[1, 2, 3, 8, 25, 5, 17, 18, 6]
[1, 2, 3, 8][25, 5, 17, 18, 6]
[1, 2, 3, 8, 6, 5, 17, 18, 25]
[1, 2, 3, 8, 5, 6, 17, 18, 25]
[1, 2, 3, 5, 25, 6, 17, 18, 8]
[1, 2, 3, 5][25, 6, 17, 18, 8]
[1, 2, 3, 5, 8, 6, 17, 18, 25]
[1, 2, 3, 5, 6, 8, 17, 18, 25]

Tabi bir de partition3() işlevi içindeki işlemler var...:)
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
erdem (Moderatör) #14
Üye Tem 2009 tarihinden beri · 978 mesaj · Konum: Eskişehir
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Son olarak Python'un çözümünü göstereyim.

[Resim: http://zayifakim.org/resim/resim/pythonekran.png]

Sadece 9 satır :)
Bu mesaj erdem tarafından değiştirildi; zaman: 2016-03-02, 03:36.
Avatar
Salih Dinçer #15
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Rica etsem bir de hız testi yapar mısın? Örneğin şu kodun ürettiği kümeyi Ali hocamın hızlıSırala() işlevi ile sıraladığımda, 1,66 Mhz. tek çekirdekli Atom işlemcide yaklaşık 30 sn. sürüyor:
  uint[] dizi;
  foreach(sayı; 1..1<<25) {
    uint sonraki = sayı * 1103515245;
    sonraki += 12345;
    dizi ~= cast(uint)((sonraki/65536)%32768);
  }
  "-başladı-".writeln();
  hızlıSırala(dizi);
  "-bitti-".writeln();
Eğer senin bilgisayarda çok hızlı olursa 33 buçuk milyonluk döngü değerini (1<<25 == 33554431) 26, 27 vb. bir şekilde arttırabilirsin. Ürettiği rakamlar küçük (16838, 908, 17747, 1817, 18655, 2726, 19564 ...) ve her seferinde aynı. Hatta değişken türünü double yaparsan iki kat daha geç sürüyor. Belki Python'da ondalıklı sayı daha kolay olur.
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Doğrulama Kodu: VeriCode Lütfen resimde gördüğünüz doğrulama kodunu girin:
İfadeler: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Özel Karakterler:
Sayfa:  1  2  3  sonraki 
Bağlı değilsiniz. · Şifremi unuttum · ÜYELİK
This board is powered by the Unclassified NewsBoard software, 20100516-dev, © 2003-10 by Yves Goergen
Şu an: 2017-11-19, 19:45:34 (UTC -08:00)