Forum: D Programlama Dili RSS
Hızlı sıralama
erdem (Moderatör) #1
Üye Tem 2009 tarihinden beri · 981 mesaj · Konum: Eskişehir
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Konu adı: Hızlı sıralama
Daha önce burada konuştuğumuz hızlı sıralama algoritmasının java sürümünü yazdım.

Bu algoritmanın ilk elemanı mihenk olarak kullanan sürümü.

$ time java-algs4 -ea Hızlı < test.txt
real    0m7.563s
user    0m10.905s
sys    0m0.296s
import std.stdio;
import std.datetime;
import std.algorithm;
import std.random;
import std.conv;
import std.array;
import std.range;
import std.string;
 
T[] hızlıSırala_küçük_büyük(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])();
 
        /* std.array.Appender normal ~ işlecinden daha hızlı olabilir. */
        version (appenderKullan) {
            auto app = appender!(int[])();
            app.put(hızlıSırala_küçük_büyük(array(küçük)));
            app.put(dizi[0]);
            app.put(hızlıSırala_küçük_büyük(array(büyük)));
 
            return app.data;
 
        } else {
            return (hızlıSırala_küçük_büyük(array(küçük)) ~
                    dizi[0] ~
                    hızlıSırala_küçük_büyük(array(büyük)));
        }
    }
    return dizi;
}
 
T[] hızlıSırala_partition3(T)(T[] asılElemanlar)
{
    /* Asıl algoritma bu. Dışındakini küçük_büyük'e haksızlık olmasın diye
     * yazdık. Böylece bu da yeni bir dizi döndürebilecek. */
    void hızlıSırala_partition3_iç(T)(T[] elemanlar)
    {
        if (elemanlar.length >= 2) {
            auto parçalar = partition3(elemanlar, elemanlar[$ / 2]);
            hızlıSırala_partition3_iç(parçalar[0]);
            hızlıSırala_partition3_iç(parçalar[2]);
        }
    }
 
    version (partitionKopyalasin) {
        T[] sonuç = asılElemanlar.dup;
 
    } else {
        T[] sonuç = asılElemanlar;
    }
 
    hızlıSırala_partition3_iç(sonuç);
 
    return sonuç;
}
 
void main()
{
    int[] sayılar;
    auto dosya = File("test.txt");
 
    while (!dosya.eof) {
        int i;
        dosya.readf(" %s", &i);
        sayılar ~= i;
    }
 
    int[] sonuç = hızlıSırala_küçük_büyük(sayılar.dup);
}

Bir de Ali beyin daha önce yazdığı D örneğini dosyadan 1000000 sayı okuyacak şekilde değiştirdim.

En iyilemeler açıkken dmd deneme.d -ofdeneme -O -release -inline -w seçenekleri ile derleyince yaklaşık 1 saniye kadar D sürümü hızlı çalışıyor.

$ time ./deneme
real    0m6.681s
user    0m6.636s
sys    0m0.032s

İkinci denemede 3 taraflı parçalama ve Tukey'in 9'lusu denilen yöntemle karma yapmadan arama yapan en iyileştirilmiş sürümünü ölçtüm. Bu sefer kütükten okumak yerine rastgele 1 milyon sayı ürettim.


$ time java-algs4 QuickX
real    0m2.058s
user    0m2.612s
sys    0m0.084s


Bu sefer D örneğinin de hızlı çalışan sürümünü kullandım ve en iyileştirmeleri açtım.

$ time ./deneme
real    0m0.586s
user    0m0.572s
sys    0m0.012s

Gene D örneği daha hızlı çalışıyor :)
Bu mesaj erdem tarafından değiştirildi; zaman: 2016-03-02, 06:43.
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ı
erdem:
Bu algoritmanın ilk elemanı mihenk olarak kullanan sürümü.

Tabii, veri zaten ters veya düz sıralanmışsa ilk elemanı seçmek çok kötü sonuç verir.

            app.put(hızlıSırala_küçük_büyük(array(küçük)));

O algoritmanın yavaş olmasının asıl nedeni o array() çağrıları çünkü her birisi bir dizi oluşturur.

Haskell gibi dillerin ne kadar hoş oldukları gösterilirken bu qsort algoritması kullanılır. Andrei de zamanında "dalga mı geçiyorsunuz; ilk eleman mihenk olarak alınır mı hiç; hem o dizilerin bedavaya mı oluşturulduğunu sanıyorsunuz" havasında eleştirirdi. Örneğin, şurada "İlerlemek Yetmez" bölümünde:

  http://ddili.org/makale/eleman_erisimi_uzerine.html

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

Orada mihenk olarak dizinin ortasındaki elemanı seçiyoruz. Oysa "Median of Medians" gibi başka algoritmalar daha hızlı olabilir. (Aşağıda "Tukey'in 9'lusu denilen yöntem" demişsin; onun "median of median" oldğunu şimdi öğrendim.) Andrei de hararetle bu konu üzerinde çalışmaya devam ediyor:

  http://forum.dlang.org/post/n8gq6g$1sfh$1@digitalmars.com

En iyilemeler açıkken dmd deneme.d -ofdeneme -O -release -inline -w seçenekleri ile derleyince yaklaşık 1 saniye kadar D sürümü hızlı çalışıyor.

Hatırlatmak için, en hızlı program üreten D derleyicisi ldc'dir. gdc ondan yüzde bir kaç birim geri kalır. dmd ise bazı işlemlerde iki kat bile yavaş olabiliyor. Öte yandan, dmd de en hızlı derleyen derleyici. (Bunları kendim hiç denemedim; ben yalnızca dmd kullanıyorum.)

Ali
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:
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-21, 19:50:13 (UTC -08:00)