Permalink
Reply
Merhaba,
Bir proje için bu gerçeğin altını çizmem gerekiyordu. Başvuru noktası tabii ki çok gözde (popularity) olan şu konuydu:
http://ddili.org/forum/thread/724
Özet olarak burada vector (vs) linked list kapışması yapmıştık ve sebep olan ise bir sunumdu. Bilgi orada duruyordu ve Ali hocam ağzımıza bu yemi verene kadar haberimiz bile yoktu...:)
Ancak kodu derleyemedim! Çünkü tartışmanın son sayfası (http://ddili.org/forum/thread/724,5)nda türler arasındaki hız farkına yoğunlaşmıştım ve de tüm testi 64 bit ortamda yapmıştım. Neyse ki her şeyi, çevik bir hareket ile int'e çevirince derleme sorunu giderildi. İşte bu durumu düzeltmek ve konuyu ön plana çıkarmak için bu başlığı kaldığı yerden canlandırıyorum...
Test sonuçları şöyle: '(Yaklaşık 6 kat fark var!)'
'C:\DMD\derle\DProjeleri>dmd linkedListTest -version=test
C:\DMD\derle\DProjeleri>linkedListTest 100000
Rakamlar üretiliyor: %99.999
TEST BAŞLADI...
TickDuration(274784)
C:\DMD\derle\DProjeleri>dmd linkedListTest
C:\DMD\derle\DProjeleri>linkedListTest 100000
Rakamlar üretiliyor: %99.999
TEST BAŞLADI...
TickDuration(47538)'
Test kodu ise böyle: '(An itibariyle düzenlenmiş hali...)'
/*
linkedListTest.d (27.09.2012)
*/
import std.array, std.conv;
import std.random, std.stdio;
struct DÜĞÜM {
int veri;
DÜĞÜM *bağı;
this(int data, DÜĞÜM *node) { veri = data; bağı = node; }
string toString() const {
string result = to!string(veri);
if(bağı) result ~= ", " ~ to!string(*bağı);
return result;
}
}
void sıralıEkle(int veri, ref DÜĞÜM *bağı) {
DÜĞÜM *önceki, şimdiki = bağı;
DÜĞÜM *sonraki = new DÜĞÜM(veri, null);
while(şimdiki != null && şimdiki.veri < veri) {
önceki = şimdiki;
şimdiki = şimdiki.bağı;
}
if(önceki == null) bağı = sonraki;
else önceki.bağı = sonraki;
sonraki.bağı = şimdiki;
}
void sıralıEkle(int veri, ref int[] liste) {
int k = ikiliArama(veri, liste);
with( appender!(int[]) ) {
put(liste[0..k]);
put(veri);
put(liste[k..$]);
liste = data;
}
}
int ikiliArama(int veri, ref int[] liste) {
int test, low;
int high = liste.length;
while(low + 1 < high) {
test = (low + high) / 2;
if(liste[test] > veri) {
high = test;
} else {
low = test;
}
}
return high;
}
import std.datetime;
void main(string[] args) { // 100000 (yüz bin)
int tekrar = args.length > 1 ? to!int(args[1]) : 10;
version(test) DÜĞÜM* testList;
else int[] testArray;
int[] rakamlar;
for(; rakamlar.length < tekrar; rakamlar ~= cast(int)uniform(0, 100)) {
auto yüzde = cast(real)rakamlar.length / cast(real)tekrar;
"\r".write("Rakamlar üretiliyor: %", yüzde * 100);
}
"\n".writeln("TEST BAŞLADI...");
auto ts = Clock.currAppTick();
foreach(rakam; rakamlar) {
version(test) sıralıEkle(rakam, testList);
else sıralıEkle(rakam, testArray);
}
debug (on) {
version(test) writefln("Bağlı Liste:\n[%s]", to!string(*testList));
else writefln("Normal Dizi:\n%s", testArray);
}
writeln((Clock.currAppTick() - ts)/1000.0);
}/*
* Eğer derlerken -version=test parametresini vermezseniz normal bir dizi oluşturur.
* Hata ayıklamak ve geliştirmek için -debug=on ile ekrana listeleri yansıtabilirsiniz.
* İşlemci hızınız çok fazlaysa ./linkedListTest 100000 parametresini büyütebilirsiniz.
* Hesabı, basitçe iki derleme (test) arasındaki değeri oranayalarak yapabilirsiniz.
* En hızlı denemeyi, 100 bin sayı ve int ile yaptığımda, tam 70 kat hızlı olduğunu gördüm...:)
*/
Kolay gelsin...
--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]