O zaman neden trisect()'in süresi pek değişmezken lowerBound()'ın tıpkı find() gibi logoritmik bir artış sergiliyor? Aşağıdaki sütunlardan, ll() ile aa() işlevleri arasında büyük bir benzerlik görülüyor:

/*
  E    ll     l2     aa
  1    232    79     53
  2    227    115    53
  3    231    139    65
  4    221    181    56
  5    218    212    56
  6    220    242    52
  7    221    281    50
*/

Ya benchmark yöntemini değiştirmek gerekiyor ya da bu yöntemlerin, veri boyutu ne olursa olsun "şak" diye bulduğu neticesi ortaya çıkıyor :)

Dip Not: E7 demek, 10 milyon elemanlı dizi demektir.

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

lowerBound() ve trisect() 'O(log N)' karmaşıklığına sahipler; yani, N büyüdükçe log(N) olarak büyüyorlar. find 'O(N)' karmaşıklığına sahip; yani, N ile doğru orantılı olarak büyüyor. Eşleme tablosu 'O(1)' karmaşıklığına sahip; yani, N'den bağımsız. :)

Ali

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

trisect şu üçünün birleşiminden başka bir şey değil: lowerBound, equalRange, ve upperBound:

http://dlang.org/phobos/std_range.html#.trisect

Eşleme tablosu karmaşıklığında olamaz çünkü elimizdeki topluluk bir dizi. Dizide arama yaparken eşleme tablolarının hash yöntemiyle sundukları performans kazancı yok. Ya find() gibi sırayla arayacağız ya da lowerBound() ve arkadaşları gibi ikili aramadan yararlanacağız.

Ali

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

Kendimi çok salak hissettim. Hayır hiç de kıllanmadım defalarca çalıştırmama rağmen aynı sonucu vermesinden :)

Ve evet Ali hocam noktayı koydunuz vallahi :) 7 saniye sürdü benim bilgisayarımda ama upperBound 196 ms

Alıntı:

Hocam aslında index istememin sebebi dizi[index-1..$] şeklinde dilimleme yapmak istemem. Şu an için bunu yapamadığımdan dizi.ptr-- dizi.length++ yapıyorum (kod sadece temsili) bu sayede bir önceki elemanı da diziye dahil ediyorum.

Bu arada fonksiyonlara verdiğim saçma sapan isimlerden dolayı da özür diliyorum :) Hem sizin için hem de benim için okumakta sıkıntı yaratıyor. İsim konusunda çok yaratıcıyım :P

Salih hocam eşleme tablosundaki sıkıntı yakın değer üzerinden ana değeri bulmama izin vermemesi o yüzden burada pekte işimize yarayamayacak fakat hız testleri aslında kendilerinin o kadarda yavaş olmadığını gösteriyor. Genellikle onu kullanmaktan kaçardım.

Zekeriya

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

Alıntı (zekeriyadurmus):

struct ADizi (i, d) {               /* arama özelliği olan dizi */
 i[d] eşleme; /* verilerden oluşturulan dizinli eşleme tablosu */
 d[] dizin;                           /* verilerin bir kopyası */

 this(d[] dizi) {
   dizin = dizi;
   foreach(i sıra, veri; dizi) {
     eşleme[veri] = sıra;
   }
 }

 i get(d aranan) {
   return eşleme.get(aranan, -1);  /* veriye göre dizini verir */
 }

 d opIndex(i sıra) {
   return dizin[sıra];          /* dizini bilinen veriyi verir */
 }
}/* Kullanımı:
double[] arr = iota(10).map!(a => a * 10).array;

auto test = ADizi!(size_t, double)(arr);
auto bulduğuDizin = test.get(20);

test[bulduğuDizin].writeln(); // 20
*/

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

32 bit derlememe rağmen bende sonuçlar aşağıdaki gibi garip çıkıyor:

/*
[atelyeweb@db dp]$ dmd arrfindbench.d -m32
[atelyeweb@db dp]$ ./arrfindbench
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536
    uzunluk  lowerBound  equalRange  upperBound     trisect
          1          35 -9147885092       34494 -9148245980 (-9147850562 değil)
          2          42 -9147885132       34494 -9148245980 (-9147850596 değil)
          4          51 -9147885136       34494 -9148245980 (-9147850589 değil)
          8          60 -9147885123       34494 -9148245980 (-9147850568 değil)
         16          70 -9147885112       34494 -9148245980 (-9147850547 değil)
         32          85 -9147885101       34494 -9148245980 (-9147850521 değil)
         64          96 -9147885096       34494 -9148245980 (-9147850504 değil)
         :          :           :
*/

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

Ali hocam rica etsem şu kodun sonucu sen de nasıl gözüküyor, nakleder misin?

Veee tabi diğer arkadaşlar da denerse ne güzel olur...

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

void main(string[] argv){
 writeln("tS\tlB\tuB\taa");
 foreach(double katı; 1..20) {
   auto adet = 10.0 * katı;
   auto aranan = adet * 10 / 2;
   double[] arr = iota(adet).
                  map!(a => ((a * 10) +
                  uniform(1, 10))).array;
   arr[] *= 1.123;

   size_t[double] aal; foreach(i, v; arr) aal[v] = i;

   auto aa(){ return aal.get(aranan, -1); }
   auto tS(){ return arr.assumeSorted.trisect(aranan)[2]; }
   auto lB(){ return arr.assumeSorted.lowerBound(aranan); }
   auto uB(){ return arr.assumeSorted.upperBound(aranan); }

   auto t = benchmark!(tS, lB, uB, aa)(1_000_000);
   foreach(b; t) write(b.msecs,"\t");
   writeln;
 }
}/* Bende ki çıktısı şöyle (maalesef yavaş bir PC):
tS	lB	uB	aa
123	77	84	63
142	95	99	65
156	110	113	63
156	114	118	68
156	112	113	66
170	128	134	66
170	130	130	63
196	159	137	62
174	129	136	69
195	159	142	69
198	160	145	72
193	163	140	77
196	164	145	64
209	163	174	60
216	186	159	61
224	201	183	62
203	161	167	62
224	184	167	63
*/

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

Alıntı (acehreli):

Buradaki reduce denklemini anlayamadım; alt çizgi neyi temsil ediyor?

   int[1] seed;
   int[] result = reduce!((sum, _) => sum[])(seed, arr);

Genelde a ve b diye yazıyorduk ve eğer toplama yapmak istiyorsak devamında a+b yapıyorduk

   int[] arr = [ 1, 2, 3, 4, 5 ];
   auto result = reduce!((a, b) => a + b)(0, arr);

   arr.writeln(": ", result); // sum = 15

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

Alıntı (Salih Dinçer):

Bende öyle olmuyor.

Alıntı:

Yanlış yazdın: find() logaritmik değildir. :) Baştan sona doğur sırayla arar.

Şu dört algoritmayı tekrarlayalım:

• lowerBound: Aranandan küçük değerler

• equalRange: Aranana eşit değerler

• upperBound: Aranandan büyük değerler

• trisect: Yukarıdakilerin hepsi ama üçünü ayrı ayrı çağırmaktan daha hızlı olarak.

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

TickDuration[4] rasgeleÖlçüm(R)(R sayılar)
{
   /* Aramanın başarısız olacağı durumlara da düşmek için uzunluktan büyük
    * bir değer aralığından seçiyoruz. */
   const sınır = sayılar.length * 10 / 9;
   const aranan = uniform(0, sınır);

   return benchmark!(() => sayılar.lowerBound(aranan),
                     () => sayılar.equalRange(aranan),
                     () => sayılar.upperBound(aranan),
                     () => sayılar.trisect(aranan))
       (1_000);
}

struct Rapor
{
   size_t uzunluk;
   TickDuration[4] ölçüm;
}

void main()
{
   enum sınırUzunluk = 100_000;
   enum rasgeleAramaAdedi = 1000;

   Rapor[] raporlar;

   /* Farklı uzunlukta dizilerle deneyler. */
   for (size_t N = 1; N <= sınırUzunluk; N *= 2) {
       writef("%s ", N);
       stdout.flush();

       /* N uzunlukta sıralı bir dizi oluştur. (Bazı sayılar tekrarlansın ve
        * aralarda boşluklar bulunsun diye garip bir hesap sonucu.) */
       auto sayılar = iota(N)
                      .map!(a => a / 3 * 4)
                      .array.assumeSorted;

       /* Bu dizi üzerinde rasgele aramalar yap. (Bazı aramalar dizide
        * bulunacak, bazıları bulunmayacak.) */
       auto ölçümler = iota(rasgeleAramaAdedi)
                       .map!(_ => rasgeleÖlçüm(sayılar));

       /* Rasgele ölçümlerin değerlerini topla. */
       TickDuration[4] sonuç;
       sonuç = reduce!((toplam, a) => toplam[] += a[])(sonuç, ölçümler);

       raporlar ~= Rapor(N, sonuç);
   }

   writeln();

   /* Sonuçları bildir. */

   writefln("%12s%12s%12s%12s%12s",
            "uzunluk", "lowerBound", "equalRange", "upperBound", "trisect");

   foreach (rapor; raporlar) {
       /* trisect'in lowerBound, equalRange, ve upperBound'ın toplamından az
        * olmasını bekliyoruz. Karşılaştırmak için ilk üçünün zamanlarını
        * toplayalım. */
       const ilkÜçününToplamı = rapor.ölçüm[0..3]
                                .reduce!((toplam, a) => toplam += a).msecs;

       writefln("%12s%(%12s%) (%s değil)",
                rapor.uzunluk,
                rapor.ölçüm[].map!(a => a.msecs),
                ilkÜçününToplamı);
   }
}

Bir çıktısı:
'
uzunluk lowerBound equalRange upperBound trisect
1 11 30 16 53 (58 değil)
2 12 21 19 45 (53 değil)
4 13 20 13 45 (47 değil)
8 16 24 16 48 (57 değil)
16 18 27 19 52 (65 değil)
32 21 29 22 54 (73 değil)
64 24 33 24 58 (82 değil)
128 26 38 27 62 (92 değil)
256 29 40 31 64 (101 değil)
512 32 44 33 68 (111 değil)
1024 35 49 37 73 (122 değil)
2048 38 53 39 77 (131 değil)
4096 41 58 43 82 (143 değil)
8192 46 63 46 87 (156 değil)
16384 50 68 51 92 (171 değil)
32768 53 73 54 98 (180 değil)
65536 58 81 58 104 (198 değil)
'
Görüldüğü gibi, dört algoritma da logaritmik olarak gidiyor. (Yani, uzunluk iki katına çıktığında süre iki katına çıkmıyor; çok daha yavaş büyüyor.) Ek olarak, trisect ilk üçünün parantez içinde bildirdiğim toplamındaha daha hızlı işliyor.

Ali

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

İlginç. Aynı hatayı -inline seçeneğini kullanmadığım zaman ben de görüyorum. Bildirmek gerek...

Ali

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