Forum: D Programlama Dili RSS
Sayı aralıklı dizi
Sayfa:  önceki  1  2 
acehreli (Moderatör) #16
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Yanıtlanan mesaj ID 10687
Salih Dinçer:
neden trisect()'in süresi pek değişmezken

Bende öyle olmuyor.

lowerBound()'ın tıpkı find() gibi logoritmik bir artış sergiliyor?

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
Avatar
Salih Dinçer #17
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
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)
          :          :           :
*/
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #18
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
İlginç. Aynı hatayı -inline seçeneğini kullanmadığım zaman ben de görüyorum. Bildirmek gerek...

Ali
Avatar
Salih Dinçer #19
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
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    
*/
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #20
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Hatayı bildirdim:

  https://issues.dlang.org/show_bug.cgi?id=12610

Ali
acehreli (Moderatör) #21
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Bende şöyle görünüyor:

tS    lB    uB    aa
76    41    42    47   
74    43    41    37   
79    46    47    39   
79    46    46    37   
79    48    46    39   
82    59    61    39   
86    52    70    43   
82    58    60    40   
82    60    61    49   
96    60    82    44   
96    64    82    47   
98    75    72    40   
100    75    73    37   
99    72    73    42   
99    77    75    39   
111    76    94    37   
99    77    73    41   
102    75    88    38   
101    76    88    38   

O  çıktıdan ne anlıyoruz: İlk satır 10 adet için deneme ve son satır 190 adet için deneme. Demek ki 190 / 10 == 19 katına çıkartmışız. Sonuç örneğin lB için kaç kat artmış? 76 / 41 = 1.8 kat artmış. Yani 19 kat değil, çok daha az artmış. Sabit de değil...

Ali
Avatar
Salih Dinçer #22
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Yanıtlanan mesaj #20
acehreli:
Hatayı bildirdim:

  https://issues.dlang.org/show_bug.cgi?id=12610

Ali
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 
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #23
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Tek alt çizgi, programda bulunması gerektiği halde gerçekte bir daha kullanılmayacak olan değişkenlere verilen isimdir. Örneğin, bir sayı aralığında sayılar üreten bir foreach'teki döngü değişkeni kullanılmayabilir:
foreach (_; 0 .. 3) {
    dene();
}
Ben de program olabildiğince kısa olsun diye öyle yaptım çünkü amacım işe yarar bir program değil, hata olduğunu düşündüğüm bir davranışı göstermekti.

Ama evet, normalde _ yerine a gibi bir isim yazarız ve o a'yı kullanırız. :)

Ali
Avatar
zekeriyadurmus #24
Kullanıcı başlığı: Talha Zekeriya Durmuş
Üye Eki 2012 tarihinden beri · 701 mesaj · Konum: Samsun/Türkiye
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Yanıtlanan mesaj #19
tS      lB      uB      aa
224     137     134     86
202     135     132     91
227     177     153     81
216     160     152     76
216     159     151     83
250     186     174     85
235     185     175     83
283     210     196     90
235     186     174     83
282     208     196     93
283     209     196     87
282     209     195     88
282     208     197     76
282     208     195     77
253     210     197     78
314     234     217     76
314     234     218     76
314     234     218     78
314     233     218     76
Bilgi meraktan gelir...
Avatar
zekeriyadurmus #25
Kullanıcı başlığı: Talha Zekeriya Durmuş
Üye Eki 2012 tarihinden beri · 701 mesaj · Konum: Samsun/Türkiye
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Ali hocam benim dizim bir struct dizisiydi ve struct üzerindeki bir değişken ile aynı işlemi nasıl yapacağız?

auto f = find!("a.start > b")(files, pos);
find de böyle yapıyordum aynısını denedim ama hata verdi bende alias kullandım :)

Zekeriya
Bilgi meraktan gelir...
acehreli (Moderatör) #26
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Bu durumda sıralama kıstası (predicate) SortedRange'e (tabii aslında onu oluşturna  assumeSorted'a) veriliyor. Böylece "şu sıralama kıstasına göre sıralı olduğunu kabul et" denmiş oluyor:
    auto result = arr.assumeSorted!((a, b) => a < b).trisect(3);
Bu arada, senin kıstasında aslında >= olmayacak mı? Hiç tam elindeki değer aranmıyor mu?

Ali
Avatar
zekeriyadurmus #27
Kullanıcı başlığı: Talha Zekeriya Durmuş
Üye Eki 2012 tarihinden beri · 701 mesaj · Konum: Samsun/Türkiye
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
= olmayacak çünkü sonrasında diziyi 1 sola genişletiyorum. Eğer eşitlik olursa bu sefer şöyle bir sorun ortaya çıkacak

0, 10, 20, 30, 40, 50, 60 ..

Girilen değer 20
Çıkış dizisi 10, 20, 30 ...

ama eşitlik olmazsa

Çıkış dizisi 20, 30, 40, 50

şeklinde olur ki bu bana lazım olan çıktı.

Kütüphaneyi paylaşmayı düşünüyorum fakat arka planda veritabanı bağlantıları da var ve biraz sistem birbirine girmiş durumda bunları çözdükten sonra önce githuba sonrada dub da paylaşmayı planlıyorum.

Zekeriya
Bilgi meraktan gelir...
acehreli (Moderatör) #28
Kullanıcı başlığı: Ali Çehreli
Üye Haz 2009 tarihinden beri · 4527 mesaj
Grup üyelikleri: Genel Moderatörler, Üyeler
Profili göster · Bu konuya bağlantı
Yanıtlanan mesaj #20
acehreli on 2014-04-21, 16:59:
Hatayı bildirdim:

  https://issues.dlang.org/show_bug.cgi?id=12610

Ve kullanıcı hatası olduğu için bugün kapattım. Tartışması şurada:

  http://forum.dlang.org/thread/lj691a$2qd1$1@digitalmars.com

reduce, toplam olarak kullanacağı değerin (seed) bir kopyasını alıyor ve aralık üzerinde ilerlerken o bizim işleve hep kopyayı gönderiyor. Dikkat ederseniz, bu örnekte sabit uzunluklu dizi olan seed bir değer türü:
    int[1] seed;
    int[] result = reduce!((sum, _) => sum[])(seed, arr);
O yüzden, bizim işlevin sum[] diye referans döndürmesi yanlış çünkü reduce sonlandığında içerideke kopyanın yaşamı sona ermiştir.

İşin iyi tarafı, bu konu başka bir hatayı ortaya çıkarttı. reduce içerideki toplam değişkenini döndürürken tabii ki yine kopya olarak döndürür. İşte o kopyanın result adlı dilime atanmaması gerekir çünkü dönen kopya hayatı çok kısa olan bir sağ değerdir (rvalue) ve bizim dilimin eli hemen boş kalacaktır. :)

Yeni hata raporu şu:

  https://issues.dlang.org/show_bug.cgi?id=12625

(Şimdi tekrar düşününce benim ilk hatanın aslında kullanıcı hatası olmadığını farkediyorum. Biz yine de sum[] diye dilim döndürebilmeliyiz çünkü nasıl olsa reduce'un en son dönüş türü int[1]'dir ama hemen yukarıdaki hata yüzünden kodun zaten derlenmemesi gerekir. Neyse... Bu hata gidici... :))

Ali
Avatar
Salih Dinçer #29
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Hocam hiç böyle düşünmemiştim, açıkcası kafam senin kadar iyi çalışmıyor...:)

Aslında hatalara karşı dikkatliyimdir ve sanki bana hemen göz kırparlar. Ama bugüne kadar bulduklarım hatadan öte sanki D dilini iyi bilmediğimden kaynaklanıyor ki bunları düzelmesini zaman zaman yapıyorsun. Dolayısıyla ancak senin gibi biri hata bildirimi yapmalı çünkü biz senin kadar dile hakim değiliz.
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Doğrulama Kodu: VeriCode Lütfen resimde gördüğünüz doğrulama kodunu girin:
İfadeler: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Özel Karakterler:
Sayfa:  önceki  1  2 
Bağlı değilsiniz. · Şifremi unuttum · ÜYELİK
This board is powered by the Unclassified NewsBoard software, 20100516-dev, © 2003-10 by Yves Goergen
Şu an: 2017-11-20, 01:37:20 (UTC -08:00)