Alıntı (erdem):

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.

Alıntı:

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

Alıntı:

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

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Alıntı (Salih Dinçer):

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

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

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...:)

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Son olarak Python'un çözümünü göstereyim.

http://zayifakim.org/resim/resim/pythonekran.png

Sadece 9 satır :)

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

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.

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Alıntı (Salih Dinçer):

>   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.
>
Bu arada önemli bir düzeltme, rakam değil sayı...

Çünkü 10'luk sistem rakamlar 10 tanedir...:)

-- 
[ Bu gönderi, <http://ddili.org/forum>'dan dönüştürülmüştür. ]

Ben hızlarını karşılaştırdım. Algoritmaları partition3 ve küçük_büyük biçiminde farklı adlandırdım.

Notlar:

• Erdem'in algoritmasında bir hata ortaya çıktı: >2 değil, >=2 olacakmış. Onu düzelttim.

• Dizileri ~ işleci yerine Appender ile birleştirmenin daha hızlı olduğu bilinir. Onun etkisini görme olanağı ekledim.

• partition3 kullanan yöntem sonuç üretmek yerine verilen diziyi değiştirir. küçük_büyük algoritmasına haksızlık olmasın diye partition3'lü algoritmanın da yeni bir dizi üretmesine olanak sağladım.

• küçük_büyük algoritması herhalde Python'un benzeri olsun diye mihengi hep ilk eleman olarak seçiyor. Andrei'nin makalesinde bunun zaten biraz sıralı olan girişler için çok kötü bir seçim olduğu yazılıydı. D'de başka bir sayıyı seçmek çok kolay ama Python gibi listeleri öne çıkaran dillerde başka seçenek çok zor. Bu testte sayılar için rasgele seçim olanağı da sundum.

• Hız karşılaştırmalarında dmd en hızlı kodu üretsin diye -O -release -inline kullanmak akıllıca.

• Salih'i mutlu etmek için with kullandım. :)

Aşağıdaki biçimde derlendiğinde version seçeneklerinin üçü de küçük_büyük algoritmasının tarafını tutuyorlar:

'dmd deneme.d -ofdeneme -O -release -inline -w -version=appenderKullan -version=rasgeleSayilar -version=partitionKopyalasin'

Onları teker teker kaldırarak sonuçların nasıl değiştiğine bakılabilir.

Yukarıdaki gibi derlendiğinde partition3 küçük_büyük'ün %15'i kadar zaman tutuyor.

Bütün version'lar kaldırılarak derlendiğinde ise 2048 adet sayı için partition3 diğerinin %3'ü ile %5'i arası gibi bir zaman alıyor:

'dmd deneme.d -ofdeneme -O -release -inline -w'

Kod da bu:

import std.stdio;
import std.datetime;
import std.algorithm;
import std.random;
import std.conv;
import std.array;
import std.range;

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ç;
}

int[] rasgeleSayılar(size_t adet)
{
   int[] sonuç;
   /* Dizide tekrarlı sayı bulunacağını garanti etmek için değer aralığını
    * adet'ten daha az seçelim. (Buna gerek olduğunu sanmıyorum.) */
   immutable değerAralığı = to!size_t(adet * 0.95) + 1;

   foreach (i; 0 .. adet) {
       sonuç ~= to!int(uniform(0, değerAralığı));
   }

   return sonuç;
}

/* Bir kaç tanesi yer değiştirilmiş olan neredeyse sıralı sayılar üretir. */
int[] neredeyseSıralıSayılar(size_t adet)
{
   auto sonuç = array(iota(0, to!int(adet)));
   immutable karıştırmaAdedi = adet / 20 + 1;

   foreach (i; 0 .. karıştırmaAdedi) {
       swap(sonuç[uniform(0, sonuç.length)], sonuç[uniform(0, sonuç.length)]);
   }

   return sonuç;
}

void karşılaştır()
{
   foreach (kat; 1 .. 12) {
       immutable adet = 1 << kat;

       writeln("\nSayı adedi: ", adet);

       version (rasgeleSayilar) {
           immutable int[] sayılar = rasgeleSayılar(adet).idup;

       } else {
           immutable int[] sayılar = neredeyseSıralıSayılar(adet).idup;
       }

       int[] p3Sonucu;
       int[] kbSonucu;

       auto ölçümler =
           benchmark!({ p3Sonucu = hızlıSırala_partition3(sayılar.dup); },
                      { kbSonucu = hızlıSırala_küçük_büyük(sayılar.dup); })
                       (1_000);

       if (p3Sonucu != kbSonucu) {
           with (stderr) {
               writeln("Algoritma sonuçları aynı değil");
               writeln("partition3 sonucu : ", p3Sonucu);
               writeln("küçük-büyük sonucu: ", kbSonucu);
           }

           throw new Exception("Algoritmalarda hata var");
       }

       immutable double p3Süre = ölçümler[0].to!("msecs", long)();
       immutable double kbSüre = ölçümler[1].to!("msecs", long)();

       writefln("partition3 : %5s ms", p3Süre);
       writefln("küçük-büyük: %5s ms", kbSüre);
       writefln("Oran       : %%%.2f", p3Süre / kbSüre * 100);
   }
}

void main()
{
   karşılaştır();
}

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Ali hocam, yine yaptı yapacağını... :-D

Bu arada gecikmeli cevap yazıyorum, çünkü geliştirme yaptığım bilgisayar hantal. O yüzden test sonuçlarını değerlendirmek çok vakit (33,5 milyon sayıda saatler ve 1 GB'dan fazla bellek kullanımı) aldı!

Ben de sıkılıp 1 milyonluk testler yaptım ama uyuya kalmışım... :-O

Alıntı:

Çalışma zamanlarına bakarsanız bir şeylerin ters gittiği belli; en azından kendi makinamda. Ancak bunun nedenini henüz çözemedim. Aslında DMD 2.059 ile derleyememiştim. Çünkü benchmark olayı o sürümde çalışmadı. Sanırım artık sonraki sürüme geçmeliyim yoksa Ali hocamın hızına yetişemeyeceğiz...:)

Bu arada zorunlu olarak, Erdem'den rica ettiğim basit içerikli testi yaptım Sonuçlar aşağıda ama değerlendirme yapmak gerekirse; Ali hocanın iç içe iki işlev ile p3 algoritmasını kb ile eşitlemesi ve idup ile her iki testte de üretilen diziyi kopyalamama rağmen, p3 en fazla 15 kat daha hızlı (runtime: p3 < kb) olduğunu yazabilirim...

p3 algoritması:
'real 0m1.158s
user 0m1.100s
sys 0m0.044s
'

kb algoritması:
'real 0m17.640s
user 0m17.197s
sys 0m0.124s
'
Bu arada kb algoritması, bu 1 milyon küsürlük sayı içeren diziyi işleyebilmesi için 60 küsür MB. hafızaya ihtiyaç duydu. Sanırım özyinelemeli olmayan hızlı sıralamanın kendi yığıtını (stack) şişirmesi gibi bu da system stack'ı şişirmekte. Python'nun ne yaptığını çok merak etmekteyim...:)

Sevgiler, saygılar...

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Alıntı (Salih Dinçer):

Kusura kalmayın evde ufak misafirler olduğu için ben bunları deneyemedim.

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Estağfirullah,

Biz senin yerine deniyoruz Erdem ama Python testi sana bakıyor...:)

Alıntı (acehreli):

Atelyedeki bilgisayara geçtim ve hiç bir sınırlama olmayan şartlarda test yaptım. Örneğin senin algoritma 15 sn.'de bitiriyorsa '
'sort!((a, b) { 'return' a < b; })(dizi);'' şeklinde denediğimde 19-20 sn. sürüyor. Test kodum ise şöyle:

import std.algorithm, std.array, std.stdio;

void hızlıSırala_p3(T)(T[] A) {
 if(A.length >= 2) {
   auto parçalar = partition3(A, A[$ / 2]);
   hızlıSırala_p3(parçalar[0]);
   hızlıSırala_p3(parçalar[2]);
 }
}

T[] hızlıSırala_kb(T)(T[] A) {
 if(A.length >= 2) {
   auto küçük = A[1..$].filter!(x => x  < A[0])();
   auto büyük = A[1..$].filter!(x => x >= A[0])();
   return (hızlıSırala_kb(array(küçük)) ~ A[0] ~
           hızlıSırala_kb(array(büyük)));
 }
 return A;
}

void main() {
 uint[] dizi, sonuç;
 foreach(sayı; 1..1<<26) {
   uint sonraki = sayı * 1103515245;
   sonraki += 12345;
   dizi ~= cast(uint)((sonraki/65536)%32768);
 }
 "-başladı-".writeln();
 //sort!((a, b) { return a < b; })(dizi);/*
 hızlıSırala_p3(dizi);/*/
 //sonuç = hızlıSırala_kb(dizi);//*/
 "-bitti-".writeln();
}

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]