Forum: D Programlama Dili RSS
Sayı aralıklı dizi
Sayfa:  1  2  sonraki 
Avatar
zekeriyadurmus #1
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ı
Konu adı: Sayı aralıklı dizi
Konuya ne yazsam bilemedim :) Elimde aşağıdaki gibi olan verileri nasıl saklamalıyım sonradan üzerinde arama yapabilmek için
[Resim: http://s24.postimg.org/4vwzh370l/torrentw.png]
Tek tek dizi içerisinde arama yapmak mantıklı olur mu? Yoksa bunları saklayabilmek için daha mantıklı bir yol var mı?

Zekeriya
Bilgi meraktan gelir...
acehreli (Moderatör) #2
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ı
fileHash sütunundakileri aramak istiyorsun, değil mi? Anlayabildiğim kadarıyla eşleme tablosunda anahtar olarak kullanabilirsin. Yeterince hızlı olur.

Dizi içinde aramak da hızlıdır ama önce diziyi baştan bir kere sıralamalı ve ondan sonra ikili arama algoritması kullanmalısın. O zaman her arama O(log N) olur. Sırayla baştan aramak ise O(N)'dir. (Big Oh gösterimine alışık olmayan arkadaşlar için: O(N) bir milyon işlem olduğunda O(log N) yirmi işlem demektir.)

Ali
Avatar
zekeriyadurmus #3
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ı
Yanlış ve eksik anlattım :)

Hocam bende bu verilerin start kolonuna göre sıralanmış hali var. Bir start değeri vereceğim ve o start değerinden ilk büyük sayının bulunduğu indeks değerini alacağım.

Start değerleri:
10, 20, 30, 40, 50, 60 ..
Girdiğin değer: 19
Aldığın değer: 0
Girdiğin değer: 22
Aldığın değer: 1 
Girdiğin değer: 39
Aldığın değer: 2

Zekeriya
Bilgi meraktan gelir...
Avatar
zekeriyadurmus #4
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ı
Şöyle bir şey yaptım. find den sonraki dilimlemesi saçma ve gereksi gibi duruyor ama şimdilik aklıma gelen bu :) Eğer diziyi sola 1 genişletemezsek bir sonraki değerden itibaren diziyi bana veriyor.

    double[] arr = [ 0, 10, 20, 30, 40 ];
    auto _f = find!("a > b")(arr, -1321);
    auto f = _f.length == arr.length
        ? _f 
        : (cast(double*) _f.ptr)[-1.._f.length];
    writeln(f);

Zekeriya
Bilgi meraktan gelir...
acehreli (Moderatör) #5
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ı
Elinde zaten sıralı bir dizi varsa find() yerine ikili aramaya dayalı bir yöntem düşünmelisin. İhtiyacın olan işlevler lowerBound ve upperBound. Ancak, onlar da sıralı dizi isterler.

O yüzden, yapman gereken sıralı dizini assumeSorted'dan geçirerek bir SortedRange nesnesi elde etmek ve bu algoritmaları o nesne üzerinde işletmek. SortedRange'in fazladan bir masrafı olmadığı gibi ona verilen dizinin sıralı olup olmadığını programın debug modunda da denetler.
import std.range;
 
void main()
{
    double[] arr = [ 0, 10, 20, 30, 40 ];
    assert(arr.assumeSorted.lowerBound(15).equal([ 0, 10 ]));
    assert(arr.assumeSorted.upperBound(15).equal([ 20, 30, 40 ]));
}
Ali
acehreli (Moderatör) #6
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ı
lowerBound ve upperBound'ı birleştiren ve ek olarak bulduğunu da bildiren trisect çok daha uygun:
    auto sonuç = arr.assumeSorted.trisect(20);
 
    assert(sonuç[0].equal([ 0, 10 ]));    // öncesi
    assert(sonuç[1].equal([ 20 ]));       // bulunan
    assert(sonuç[2].equal([ 30, 40 ]));   // sonrası 
Aranan bulunmadığında 1 numaralı aralık boştur:
    auto sonuç = arr.assumeSorted.trisect(15);
 
    assert(sonuç[0].equal([ 0, 10 ]));
    assert(sonuç[1].empty);
    assert(sonuç[2].equal([ 20, 30, 40 ]));
Ali
Avatar
zekeriyadurmus #7
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ı
Şöyle bir benchmark testi yaptım. (Release modunda) find ile upperBound aynı çıktı ve trisect ise baya geride kaldı
ayrıca dizi içerisinden almadan direk ekrana yazdırdığım zaman find işlevi gibi çalıştığını fark ettim

Tuple!(SortedRange!(double[], "a < b"), SortedRange!(double[], "a < b"), SortedR
ange!(double[], "a < b"))([0, 10, 20], [], [30, 40])

a < b şeklinde denetim var :)

import std.stdio;
import std.algorithm;
import std.range;
import std.datetime;
int main(string[] argv){
    double[] arr = [ 0, 10, 20, 30, 40 ];
 
    void ll(){
        auto sonuç = arr.assumeSorted.trisect(25)[2];
    }
    void l2(){
        auto sonuç = arr.assumeSorted.upperBound(25);
    }
    void l3(){
        auto sonuç = find!("a > b")(arr, 25);
    }
 
    auto m = benchmark!(ll, l2, l3)(1_000_000);
    writeln(m[0].msecs, "--", m[1].msecs, "--", m[1].msecs);
 
    while(1){}
    return 0;
}

Zekeriya
Bilgi meraktan gelir...
acehreli (Moderatör) #8
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ı
1) Ölçümü yazdırırken find'ınkini de m[1] diye yazmışsın.

2) Algoritma karmaşıklıkları bir kaç on adetten az sayılarda önemsizdir. Bu testi en az bin elemanlı diziyle yapmak gerek.

Bir de, find'a ayrıcalık olmasın diye ortadaki değeri arattım.
import std.stdio;
import std.algorithm;
import std.range;
import std.datetime;
 
void main(string[] argv){
    auto adet = 1_000.0;
    auto aranan = adet * 10 / 2;    // ortadaki değer
 
    double[] arr = iota(adet).map!(a => a * 10).array;
 
    void ll(){
        auto sonuç = arr.assumeSorted.trisect(aranan)[2];
    }
    void l2(){
        auto sonuç = arr.assumeSorted.upperBound(aranan);
    }
    void l3(){
        auto sonuç = find!("a > b")(arr, aranan);
    }
 
    auto m = benchmark!(ll, l2, l3)(1_000_000);
    writeln(m);
    writeln(m[0].msecs, "--", m[1].msecs, "--", m[2].msecs);
}
64--37--1019
On bin adet için de siz deneyin. ;)

Ali
Avatar
Salih Dinçer #9
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Çok güzel...

Ben de konuyu 2 açıdan ele almak istedim. Birincisi, Associative Array'de ne kadar bir hız elde edeceğimiz konusunda; diğer ise farklı büyüklükteki dizilerde değişimin doğrusal olup olmadığı hakkında. Sonuçların ilginç olduğunu düşünüyorum!
import std.stdio;
import std.algorithm;
import std.range;
import std.datetime;
import std.getopt;/***                                          Salih ekledi */
void main(string[] argv){
    auto adet = 1_000.0;
    getopt(argv, "adet", &adet);/***                            Salih ekledi */
    auto aranan = adet * 10 / 2;    // ortadaki değer
    double[] arr = iota(adet).map!(a => a * 10).array;
    size_t[double] aal; foreach(i, v; arr) aal[v] = i;/***      Salih ekledi */
    
    void aa(){
        auto sonuç = aal.get(aranan, -1);/***                   Salih ekledi */
    }
    
    void ll(){
        auto sonuç = arr.assumeSorted.trisect(aranan)[2];
    }
    void l2(){
        auto sonuç = arr.assumeSorted.upperBound(aranan);
    }
    void l3(){
        auto sonuç = find!("a > b")(arr, aranan);
    }
 
    auto m = benchmark!(ll, l2, l3, aa)(1_000_000);
    //adet.writeln();
    writeln(m[0].msecs, "--", m[1].msecs, "--", m[2].msecs, "--", m[3].msecs);
}/* Çıktısı:
[atelyeweb@db dp]$ dmd arrfindbench.d
[atelyeweb@db dp]$ ./arrfindbench --adet=100
208--95--628--47
[atelyeweb@db dp]$ ./arrfindbench --adet=200
209--106--1212--46
[atelyeweb@db dp]$ ./arrfindbench --adet=300
209--114--1779--46
[atelyeweb@db dp]$ ./arrfindbench --adet=400
208--114--2350--47
[atelyeweb@db dp]$ ./arrfindbench --adet=500
210--115--2939--46
[atelyeweb@db dp]$ ./arrfindbench --adet=1000
212--125--5894--53
*/
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #10
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ı
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
Avatar
Salih Dinçer #11
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
Ben trisect()'in de tıpkı eşleme tablosundaki gibi bir karmaşıklığa sahip olduğunu ama biraz daha (4x kadar) yavaş kaldığını düşünüyorum.

Ayrıca trisect() bize verinin bulunduğu sırayı değil verinin kendisini, dolayısıyla bulduğu elemanı gönderiyor. Sanırım Zekeriya'nın ihtiyaç duyduğu, verinin kaç numaralı index (i)'de bulunduğu olmalı?
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
acehreli (Moderatör) #12
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ı
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
Avatar
Salih Dinçer #13
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
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.
Bilgi paylaştıkça bir bakmışız; kar topu olmuş ve çığ gibi üzerimize geliyor...:)
Avatar
zekeriyadurmus #14
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 #8
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

Ayrıca trisect() bize verinin bulunduğu sırayı değil verinin kendisini, dolayısıyla bulduğu elemanı gönderiyor. Sanırım Zekeriya'nın ihtiyaç duyduğu, verinin kaç numaralı index (i)'de bulunduğu olmalı?
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
Bilgi meraktan gelir...
Avatar
Salih Dinçer #15
Üye Ock 2012 tarihinden beri · 1912 mesaj · Konum: İstanbul
Grup üyelikleri: Üyeler
Profili göster · Bu konuya bağlantı
zekeriyadurmus:
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.
Anladım, belki şu yapı işine yarayabilir:

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
*/
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:  1  2  sonraki 
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-19, 05:55:14 (UTC -08:00)