Kısa kısa geçeceğim, çünkü önemli sonuçlar elde ettim... :nuts:

Önce bellek, çünkü bu hıza da etki ettiği gibi düşük bellekli taşınabilir aygıtlarda tercih nedenimiz olabilir!

DMD 2.060 ile p3 algoritması:
770 MB. (üretilen rasgele dizi işleve dup ile kopyalanarak verildiğinde)
513 MB. (kopyalanmadan, doğrudan verildiğinde)
475 MB. (iç içe işlev iptal edilip referans ile doğrudan diziye eriştiğinde)

Bu testleri'*' 67,1 milyon sayı ile yaptım. Her biri yaklaşık olarak 1 dk. (en fazla 1m16.113s) sürdü. Örneğin:

'real 1m16.113s
user 1m12.209s
sys 0m1.868s
'
Ama bu değerlere dördüncüsünü eklemeliyiz ki o da dizinin üretilme zamanını (~26 sn.) göstersin. Bu durumda sıralama işlemi 1,66 Mhz. ile 67.1 milyon 32 bitlik sayı 50 sn. sürdü diyebiliriz.

Küçük ve çok ilginç bir ayrıntı daha var! O da önceki sürümde (DMD 2.059) dizinin kapladığı alan (son test) 400 MB. bile değil. Tam olarak ifade edersek 475 - 399 = 76 MB.'lık bir fark var. Artık bu son sürümde ne yapmışlarsa...:)

'(Not: Bundan sonraki testler, belleği daha tutumlu kullandığı için önceki sürümde yapılmıştır!)'

DMD 2.059 ile kb algoritması:
1,8 GB. (üretilen rasgele dizi işleve dup ile kopyalanarak verildiğinde)
1,7 GB. (kopyalanmadan, doğrudan verildiğinde)

Bu son testte çok büyük bir veri yok; yavaş olması dışında. Ancak bütün testlerde önemli bir şey daha dikkatimi çekti; o da sadece tek çekirdeğin işlem görmesi. Çünkü diğer üç çekirdekte fazla bir kıbırdanma yoktu. Elbette paralel programlama yapmadığımız için böyle ama hiç mi işletim sistemi (Fedora 17) belleği daha hızlı kullanabilmek için diğer çekirdekleri kullanmaz...:)

'(*)' Atom N450 işlemci ile 1,66 MHz. saat frekansında...

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

Aslında özyinelemeli işlevlerde (recursive function) bunu işlemci belirleyebilmelidir. Sebebi sanırım çok basit; birbirine bakan aynalardaki görüntülerde olan biten her şey, iç içe geçmiş ve ufalarak giden görüntülerdir. Öyleyse aynı görüntü meydana gelecekse diğer çekirdeklerin beklemesi kaynak israfından başka bir şey olmasa gerek.

Sanırım biraz daha gayret edersek, bu sıralama işlevini tüm çekirdeklere yayabiliriz. Bu mümkün görünüyor, düşünelim... :rolleyes:

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

Alıntı (Salih Dinçer):

Büyük olasılıkla mikroişlemcinin iç belleğine sığmamaya başlandığı içindir. Doğru hatırlıyorsam, ana bellek iç belleğin bir kaç on katı kadar yavaş. Ondan sonra ana belleğe de sığmamaya başlayınca bu sefer işletim sistemi diske yazıp okumaya geçtiğinde de yine yanılmıyorsam bir kaç bin kat kadar yavaş oluyor.

Bu arada, bir de std.algorithm.sort'u deneyin. Bu algoritmaların hiçbirisi onun hızına yaklaşamıyor. :)

Ali

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

Dayanamadım şu Python neymiş diye bir bakayım dedim ve aşağıdaki gibi çalışan bir test kodu açığa çıktı...:)

import time
def timestamp():
   return int(time.time())

def hızlıSırala(dizi):
   if len(dizi) <= 1:
       return dizi
   küçük = [x for x in dizi[1:] if x <  dizi[0]]
   büyük = [x for x in dizi[1:] if x >= dizi[0]]
   return hızlıSırala(küçük) + [dizi[0]] + hızlıSırala(büyük)

from math import floor
def rasgeleSayı(sayı):
   sonraki = (sayı * 1103515245) + 12345
   return floor((sonraki/65536)%32768)

#   ana program
if __name__ == '__main__':
   dizi = []
   i = 1
   while (i < 1<<25):
     dizi += [rasgeleSayı(i)]
     i += 1
   ts = timestamp()
   print(len(hızlıSırala(dizi)))
   print(timestamp() - ts)

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

Python örneği şu şekilde:

import random

def hızlıSırala(liste):
   if len(liste) <= 1:
       return liste
   küçük = [x for x in liste[1:] if x < liste[0]]
   büyük = [x for x in liste[1:] if x >= liste[0]]
   return hızlıSırala(küçük) + [liste[0]] + hızlıSırala(büyük)

#  ana program
if __name__ == '__main__':
   liste  = [random.randint(1, 10000) for x in range(100000)]
   print(hızlıSırala(liste))

Tabi Python derlemeli bir dil olmadığı için listeyi oluşturmak bile oldukça zaman alıyor.

'$ time python3 test.py'

Alıntı:

D karşılığı

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

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()
{
   int[] sayılar;
   for (int i = 0; i < 100_000; ++i) {
       sayılar ~= to!int(uniform(0, 10_000));
   }
   hızlıSırala(sayılar);
}

'$ time ./test'

Alıntı:

Ali beyin gösterdiği 'partition3''un hızlı çalışmasının nedeni diziyi nereden böleceğini akıllıca seçmesinden kaynaklanıyor. Küçük diziler için ortadakini, orta boydaki diziler için ilk orta ve son elemanın medyanını (ortalamasını) ve büyük diziler için 9 tane değer seçiyor.

http://cs.fit.edu/~pkc/classes/writing/samples/bentley93engineering.pdf

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

Alıntı (Salih Dinçer):

Benim algoritma diyemeyiz çünkü asıl işi partition3'te bitiyor. Onu özyinelemeli olarak çağırmak bir şey değil. :)

Eğer "-O -release -inline" seçeneklerini kullanmazsam bende de sort daha daha yavaş. Onları kullanınca daha hızlı.

Ali

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

Alıntı (Salih Dinçer):

Onlarca iş parçacığının her birisi kendisi için belirlenen çekirdekle ilişkilendirilir (affinity). O anlamda, diğer çekirdekler tabii ki kullanılıyorlar. Ama tek iş parçacığının hangi noktalarının eş zamanlı olarak işletilebileceğine karar verebilmek ancak insana kalmıştır. Buna derleyiciler bile karar veremiyorlar.

Hızlı sıralama alt parçaları koşut olarak sıralanabilen bir algoritmadır. Bunu biz bilebiliyoruz. Makine koduna bakarak bunu anlayacak işletim sistemi hiç duymadım.

Ali

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

Çok gereksiz olmak ile birlikte, sadece katkı sağlamak için küçük/büyük aralıkları farklı şekilde meydana getirdim. Böylece 'parallel()' işlevinde kullanabileceğimi düşündüm. Henüz tek çekirdekli bir işlemcide denediğim için işlem sonucu hem doğru hem de uzun sürüyor; sanırım iki kat daha fazla iş yaptığından olsa gerek...:)

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

void main() {
   int[] sayılar;
   //sayılar = [5, 3, 25, 6, 10, 17, 1, 2, 18, 8];/*
   foreach(i; 10..1_000_000) sayılar ~= to!int(uniform(0, i));//*/
   "sayılar".writeln;
   quickSort_DR(sayılar);
   "sayılar".writeln;
}
bool yaz = true;
void quickSort_DR(T)(T[] a)
{
   if (a.length < 2) {
       return;
   }

   T p = a[$ / 2];
   //T[] kb[0] = a[0..$];
   //T[] kb[1] = a[0..$];

   auto kb = new T[][2];
        kb[0] = a[0..$];
        kb[1] = a[0..$];
   //*
   if(yaz) {
     yaz = false;
     writefln("%X", &a);
     writefln("%X-%X", &kb[0], &kb[1]);
   }//*/
   bool örtüşüyorlar_mı()
   {
       return (kb[0].length + kb[1].length) > a.length;
   }

   while (örtüşüyorlar_mı) {
       while (!kb[0].empty && (kb[0].back > p)) {
           kb[0].popBack();
       }

       while (!kb[1].empty && (kb[1].front < p)) {
           kb[1].popFront();
       }

       if (!kb[0].empty && !kb[1].empty && örtüşüyorlar_mı) {
           swap(kb[0].back, kb[1].front);
           kb[1].popFront();
           kb[0].popBack();
       }
   }
   foreach (i; parallel(kb)) quickSort_DR(i); /*
   quickSort_DR(kb[0]);
   quickSort_DR(kb[1]);//*/
}

Dip Not: Belki de çok çekirdekli bir işlemcide iki kat hızlı çalışır diye paylaşıyorum; denemedim...:)

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

Alıntı (acehreli):

> foreach (parça; parallel([ küçük, büyük ]))
> ```

>
> Ben de daha hızlı sonuç elde edemedim. Herhalde *context switching*'in bedelini ödüyoruz. (?)
>
> Ali
>
Olabilir ama sonuçlar çok değişken ve tabi 8 saniyede bitmesi gerekirken iki kat sürede bitiyor:

'real	0m12.671s
user	0m23.397s
sys	 0m7.569s
'
'real	0m14.573s
user	0m16.344s
sys	 0m0.996s
'
'real	0m14.353s
user	0m28.921s
sys	 0m16.551s
'
**
Dip Not:** Dayanamadım, atölyedeki 4 çekirdekliğe geçtim de...:)

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

Alıntı (Salih Dinçer):

İşlemciler kendilerine verilen kodu hemen işletme işiyle görevliler. IP (instruction pointer) yazmaçlarına bir adres yerleştirilir ve "çalış" denir. İşlemcinin o adresin ilerisindeki kodları incelemeye zamanı yoktur ve zaten hiçbirimiz bunu istemeyiz.

İşlemcilerin yapabildikleri koşutluk çok alt düzeydeki ve art arda gelen ++i ve ++j gibi bağımsız ifadelerin ikisini aynı anda işletebilmeleridir. (Aslında GPU'lar koşutluk olayını çok ileriye götürüyorlar.)

Alıntı:

Ben bunu dün std.parallelism ile bir kaç saat denedim ama ne yazık ki hızlı işletemedim. Rosetta Code'daki C programını aynen D'ye geçidiğimde o her zaman için en hızlı algoritma oldu. Onun dilimlere dönüştürülmüş biçimi ise hemen hemen her zaman o en hızlının iki katı yavaş kaldı.

Bu en hızlı D işleviydi (ama dediğim gibi, std.algorithm.sort daha hızlı oldu (eğer yanlış hatırlamıyorsam)):

void quick_sort_C_R(int *a, int n) {
   if (n < 2)
       return;
   int p = a[n / 2];
   int *l = a;
   int *r = a + n - 1;
   while (l <= r) {
       while (*l < p)
           l++;
       while (*r > p)
           r--;
       if (l <= r) {
           int t = *l;
           *l++ = *r;
           *r-- = t;
       }
   }
   quick_sort_C_R(a, to!int(r - a + 1));
   quick_sort_C_R(l, to!int(a + n - l));
}

T[] quick_sort_C(T)(T[] asıl_a)
{
   version (partitionKopyalasin) {
       T[] a = asıl_a.dup;

   } else {
       T[] a = asıl_a;
   }

   quick_sort_C_R(a.ptr, to!int(a.length));
   return a;
}

Bu da onun mantığını aralıklarla (yani dilimlerle) uygulayanı (yazması zor oldu ama eğlenceliydi):

void quick_sort_D_R(T)(T[] a)
{
   if (a.length < 2) {
       return;
   }

   T p = a[$ / 2];
   T[] küçük = a;
   T[] büyük = a;

   bool örtüşüyorlar_mı()
   {
       return (küçük.length + büyük.length) > a.length;
   }

   while (örtüşüyorlar_mı) {
       while (!küçük.empty && (küçük.back > p)) {
           küçük.popBack();
       }

       while (!büyük.empty && (büyük.front < p)) {
           büyük.popFront();
       }

       if (!küçük.empty && !büyük.empty && örtüşüyorlar_mı) {
           swap(küçük.back, büyük.front);
           büyük.popFront();
           küçük.popBack();
       }
   }

   quick_sort_D_R(küçük);
   quick_sort_D_R(büyük);
}

T[] quick_sort_D(T)(T[] asıl_a)
{
   version (partitionKopyalasin) {
       T[] a = asıl_a.dup;

   } else {
       T[] a = asıl_a;
   }

   quick_sort_D_R(a);

   return a;
}

Ali

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