Daha önce burada (http://ddili.org/forum/thread/966) konuştuğumuz hızlı sıralama algoritmasının java sürümünü (https://github.com/erdemoncel/java/blob/master/Hızlı.java) yazdım.

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

Alıntı:

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.

Alıntı:

İ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.

Alıntı:

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

Alıntı:

Gene D örneği daha hızlı çalışıyor :)

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

Alıntı (erdem):

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

Alıntı:

>             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>

Alıntı:
>
>

        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

Alıntı:

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

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