Dün D.learn haber grubuna sayarak sıralama[1] yöntemini aralıklarla gerçekleştirmeyle ilgili bir soru gelmişti.

Sayarak sıralama çok akıllıca bir yöntem ama özellikle elemanların alabildikleri değer aralığı küçük olduğu durumlara uygun. Örneğin, bir milyon değerimiz var ama bunların hepsinin 0 ve 10 arasında olduğunu biliyoruz.

Normal sıralama uyguladığımızda 'N log(N)' adet işlem gerekir. Örneğin, N'nin bir milyon olduğun durumda kabaca 20 milyon adım gerekir. (Logaritmayı 2 tabanında alınca log(1_000_000) kabaca 20'dir.)

Sayarak sıralama şöyle işliyor:

• Farklı eleman değerleri uzunlukta bir dizi oluştur. (0-10 aralığı için 11 elemanlı dizi.)

• Diziyi baştan sona ilerleyerek her değerden kaç adet olduğunu o diziye yerleştir. (Örneğin, adetler[0] elemanı 0 değerinden kaç adet bulunduğunun tutsun.)

• Şimdi o dizi üzerinde ilerleyerek her değerden o kadar adet üret. (Bunu tembel aralık olarak yapabiliriz, aynı dizi üzerine yazarak yapabiliriz, vs.)

Bu algoritmanın karmaşıklığı ise 'N + M' kadar küçük oluyor. Yani bir milyon + 11. Yirmi kere daha az işlem yapmış olduk! :)

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

enum toplamEleman = 1_000_000;
enum toplamDeğer = 100;

/* Bu 'version', sayarak sıralama işlevinde aralık mı yoksa foreach mi
* kullanılacağını belirler. Bu satırı çıkartırsanız sayarak sıralama daha
* hızlı işliyor.  */
version = aralıkKullanarak;

void main() {
   // Rasgele elemanlarla dolu bir dizi
   auto dizi = generate(() => uniform(0, toplamDeğer))
               .take(toplamEleman)
               .array;

   // Haksızlık olmasın diye iki algoritmaya farklı dizi veriyoruz
   auto diziNormal = dizi.dup;     // Normal sort'un kullanacağı dizi
   auto diziSayarak = dizi.dup;    // Sayarak sıralamanın kullanacağı dizi

   // İşlem sürelerini ölçüyoruz
   const ölçümler = benchmark!(() => normalSortİle(diziNormal),
                               () => sayarakSıralamaİle(diziSayarak))(100);

   writeln("algorithm.sort ile  : ", to!Duration(ölçümler[0]));
   writeln("Sayarak sıralama ile: ", to!Duration(ölçümler[1]));
}

auto normalSortİle(int[] dizi) {
   dizi.sort();

   /* Ölçümler anlamlı olsun diye bütün elemanları kullanalım. */
   return dizi.sum;
}

auto sayarakSıralamaİle(int[] dizi) {
   // Her değerden kaç adet bulunduğunu tutan dizi
   auto adetler = new uint[toplamDeğer];

   /* adetler dizisini dolduruyoruz. Bunun sonucunda örneğin adetler[0]
    * elemanı, dizide kaç adet 0 değeri bulunduğunu gösterecek. */
   dizi.each!(e => ++adetler[e]);

   version (aralıkKullanarak) {

       /* Her değerden kaç adet varsa o değeri o kadar kere tekrarlıyoruz.
        * Her ne kadar şık olsa da, bu yöntem dmd ile derlendiğinde aşağıdaki
        * 'foreach'li yöntemden daha yavaş kalıyor. */
       auto sonuç = adetler
                    .enumerate
                    .map!(ç => ç[0].repeat(ç[1]))
                    .joiner;

       /* Ölçümler anlamlı olsun diye bütün elemanları kullanalım. (Yoksa bu
        * tembel aralığın işlemleri hiç işletilmezdi.) */
       return sonuç.sum;

   } else {

       /* Yukarıdaki 'enumerate'in ne işe yaradığını gösterebilmek için
        * tembel aralık yöntemi yerine aşağıdaki gibi bir foreach de
        * kullanabiliriz. Bu yöntemde dizinin kendisini sıralayacağız. */

       size_t i = 0;    // Asıl dizi üzerindeki indeks

       /* Dikkat ederseniz, aşağıdaki 'değer' aslında 'adetler' üzerindeki
        * sayaçtır. */
       foreach (int değer, adet; adetler) {
           // O değerden 'adet' kadar yerleştiriyoruz
           foreach (_; 0 .. adet) {
               dizi[i] = değer;
               ++i;
           }
       }

       return dizi.sum;

   }  /* version (aralıkKullanarak) else */
}

dmd'ye '-O -inline -noboundscheck' seçeneklerini verince oluşan programın benim ortamımdaki bir çıktısı:

'algorithm.sort ile : 7 secs, 37 ms, 491 μs, and 3 hnsecs
Sayarak sıralama ile: 1 sec, 703 ms, 90 μs, and 6 hnsecs
'
Bir milyon eleman ve 100 farklı değer için yedi kat daha hızlı. Hiç fena değil! :)

Ali

[1] https://tr.wikipedia.org/wiki/Sayarak_s%C4%B1ralama

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