Konuya ne yazsam bilemedim :) Elimde aşağıdaki gibi olan verileri nasıl saklamalıyım sonradan üzerinde arama yapabilmek için
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

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

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

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

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

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

Şö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

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

Şö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

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

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

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

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

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

Ç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
*/

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

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ı?

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

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

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