Delphi Can

Orjinalini görmek için tıklayınız: Array of Stings içerisinde arama yapma
Şu anda (Arşiv) modunu görüntülemektesiniz. Orjinal Sürümü Görüntüle internal link
Sayfalar: 1 2
Merhaba,

yazdığım bir uygulamada içinde 2500 adet civarı 60-120 karakter arasında değişen boyutlarda indexli string bulunan array içerisinde seçilen bir string değerin aramasını sağlıyorum, bunun içinde MatchStr kullanıyorum, öğrenmek istediğim bunun daha hızlı bir yolu varmıdır acaba?
Merhaba.

- Aşağıda verdiğim örnek üzerinden çok hızlı buluyor. 
- Örnekte "5 milyon" tane MD5 hash oluşturup hiç sırlama yapmaksızın kontrol ettiriyoruz. 5 milyon hash için bir süre donuyor ama message dialog butonuna basar basmaz bulundu diyor. 

- Aşağıdaki görselde belki tıkladığım anlaşılmaz diye mouse ile butona basmadan hemen önce üçe kadar saydığımı ifade etmek için buton etrafında üç defa döndürdüm.

Uses System.Hash;

Var
  FArray : Array of String;

procedure RandomFill( aCount: Integer );
var
  i : Integer;
begin
  if Length(FArray) > 0 then Finalize(FArray);
  SetLength( FArray, aCount );
  for i := low(FArray) to high(FArray) do
    FArray[i] := THashMD5.GetHashString( IntToStr(i) );
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  LSrc : String;
begin
  RandomFill( 5000000 );
  LSrc := THashMD5.GetHashString( '4000000' );
  showmessageFmt( '%s'#13'%s', [ FArray[4000000], LSrc ] );  // 4 milyonuncu
  if MatchStr( LSrc, FArray ) then Showmessage('Bulundu') else Showmessage('Maalesef.... ');
end;



ubo4qeviepvzcmdfuxmh.gif
Teşekkürler Hocam, anlaşılan MatchStr kullanmaya devam edicez.
Üstadım bildiğiniz üzere kod yazmak strateji kurmayı gerektirir.
* Yani anlatmak istediğim, temel fonksiyonlar öngörüsü kıt çalışır.

* Örneğimizdeki matchstr için konuşursak temel işlevi sıralı arama yaparak karşılaştırma yapar.

* Aradığınız string ilk sıralarda ise çabuk son sıralarda ise görece daha geç bulur ama oldukça hızlıdır.

Son cümlenizden "mecburen" anlamına gelen "anlaşılan" kısmı sizi bağlamasın. İlk mesajınızda belirtmişsiniz Indexli demişsiniz. (Sıralı bir arama söz konusu ise basit sıçramalar ile bu performansı kendi ihtiyacınız için mükemmelleştirebilirsiniz.

Nasıl mı ? Sıralı demiştiniz. 
(1) 5 milyon SIRALI eleman içerisinde önce tam ortadaki 2,5 milyonuncu elemanı alır ve elinizde aradığınız string eşit / daha küçük / veya büyük olduğunuz sorarsınız. alacağınız cevap size 2,5 milyon tane sorgulanacak elemanı devre dışı bırakarak kafadan %50'ini çöpe atacaktır.
(2) cevap küçük diyelim, bu defa da      baştan bu 2,5 milyonun tam ortasını yani 1,250 milyonu sorarsınız eşit/küçük/büyük
(3) 1 - 1,250 ortası = 750 bin eşit/küçük/büyük
(4) 1 - 750 bin ortası = 375 bin eşit/küçük/büyük
(5) 1-  375 bin ortası = 187,5 bin
(6) 1-  187,5 bin ortası = 93750 
(7) 1-  93750 = 46875 
(8) 1-  46875 ortası = 23437 

bu makul seviyeye indi mi indi. Kaç adımda indi 7 veya 8 adımda. Şimdi kalan kısmı bir diziye alıp MatchStr yapın bakalım hız ışık hızında olmuyor mu ? 

Anlatabildim mi ?
Gayet iyi anlıyorum sizi hocam, normalde elimde 52K civarında kayıt var zaten, bunu sıraya dizip ilk 2 karakteri baz alarak 58 adet diziye zaten böldüm, en büyük dizide 2500 kayıt var, önce ilk 2 karakterin hangi dizide olduğunu bulup sonra onda arama yapıyorum da sanırım ben biraz daha zorluyorum Smile acaba diyorum daha da hızlanabilirmi ? 

MatchStr fonksiyonunu  aşağıdaki şekilde değiştirdim;

function ArrayTara(const AText: string; const AValues: array of string): Integer;
var
 i : longint;
begin
 result:=-1;
 if (high(AValues)=-1) or (High(AValues)>MaxInt) Then
   Exit;
{
 for i:=low(AValues) to High(Avalues) do
    if (avalues[i]=AText) Then
      exit(i);
}
for i:=low(AValues) to ceil(High(Avalues)/2) do begin

  if (avalues[i]=AText) or
     (avalues[High(Avalues)-i]=AText)
  Then
    exit(i);
   end;
end;

fakat pek birşey farketmedi.
@esistem
Size bir örnek hazırladım, aşağıdaki şekilde bir deneyin bakalım farkı görebilecek misiniz ?

* Burada MatchStr kesinlikle kullanılmıyor, onun yerine indexli (sıralı) array olmak kaydıyla, MatchStr fonksiyonu benzeri bir karşılaştırma yapıyor. 

* Tek farkı size yukarıda belirttiğim şekilde sıçrama ile eleme yaparak performans arttırma işlemi var..


function SearchArray( aSrc : String; const aArray: Array of String ): boolean;
const
  MakulElemanSayisi = 10;
var
  i, LSayac, idxBas, idxSon, iOrta : Integer;
begin
  Result := False;

  idxBas := Low (aArray);
  idxSon := High(aArray);
  LSayac := High(aArray)+1;
  iOrta  := (idxSon - idxBas) div 2;
  repeat
    if aSrc > aArray[iOrta] then begin
      idxBas :=  iOrta+1;
    //idxSon := Aynı...
      iOrta  :=  iOrta + (idxSon - idxBas) div 2;
      LSayac := (idxSon - idxBas + 1);
    end else
    if aSrc < aArray[iOrta] then begin
    //idxBas := Aynı...
      idxSon :=  iOrta -1;
      iOrta  :=  idxBas + (idxSon - idxBas) div 2;
      LSayac := (idxSon - idxBas + 1);
    end
    else Result := True; // tesadüfen bulundu... :)
  until ( LSayac <= MakulElemanSayisi ) or Result;

  i := idxBas;
  while (not result) AND  (i <= idxSon) do begin
    Result := aArray[i] = aSrc;
    inc(i);
  end;
end;

procedure TForm1.Button2Click(Sender: TObject);
var
  LSrc : String;
begin
  LSrc := THashMD5.GetHashString( intToStr(1) );
//if MatchStr( LSrc, FArray ) then Showmessage('Bulundu') else Showmessage('Maalesef.... ');
  if SearchArray( LSrc, FArray ) then Showmessage('Bulundu') else Showmessage('Maalesef.... ');
end;





* Denemek isteyenler için 
  • MD5 string halindeki indexlenmiş haldeki 52 bin adet hash içeren text dosya linki için image_StringArray_52000.php
  • MD5 string halindeki indexlenmiş haldeki 5 milyon adet hash içeren text dosya linki için image_StringArray_52000.php

* Bu dosya içerisinde 0 .. 519999 kadar string rakamların MD5 hash'ı alınmış ve MD5 hallerine göre sort edilmiş hallerini bulacaksınız.

herhangi bir rakamın MD5 hash halini yukarıdaki fornksiyonda arama yaptırabilirsiniz.

Örnekte 52K elemanlıda 12 sıçrama (satır sorgusu) + 5 sıralı sorgu = 17 sıralı sorguda bulundu. 1'den 52000'e kadar sıralı sorgudan kaç kar hızlı anlatabildim sanırım. ( 1ncide de olsa 519999 ncuda da olsa benzer sürede bulacaktır. Diğer türlü 1'de ilk denemede 51999'da sıra numaralı denemede buluyordu. 

PHP Kod:
(Sıçra : 0) iBas:0 iSon:51999 / iOrta: 25999 / Aradaki Eleman Say : 52000
Daha küçük
....
(
Sıçra : 1) iBas:0 iSon:25998 / iOrta: 12999 / Aradaki Eleman Say : 25999
Daha BÜYÜK
....
(
Sıçra : 2) iBas:13000 iSon:25998 / iOrta: 19498 / Aradaki Eleman Say : 12999
Daha BÜYÜK
....
(
Sıçra : 3) iBas:19499 iSon:25998 / iOrta: 22747 / Aradaki Eleman Say : 6500
Daha küçük
....
(
Sıçra : 4) iBas:19499 iSon:22746 / iOrta: 21122 / Aradaki Eleman Say : 3248
Daha BÜYÜK
....
(
Sıçra : 5) iBas:21123 iSon:22746 / iOrta: 21933 / Aradaki Eleman Say : 1624
Daha BÜYÜK
....
(
Sıçra : 6) iBas:21934 iSon:22746 / iOrta: 22339 / Aradaki Eleman Say : 813
Daha küçük
....
(
Sıçra : 7) iBas:21934 iSon:22338 / iOrta: 22136 / Aradaki Eleman Say : 405
Daha BÜYÜK
....
(
Sıçra : 8) iBas:22137 iSon:22338 / iOrta: 22236 / Aradaki Eleman Say : 202
Daha BÜYÜK
....
(
Sıçra : 9) iBas:22237 iSon:22338 / iOrta: 22286 / Aradaki Eleman Say : 102
Daha BÜYÜK
....
(
Sıçra : 10) iBas:22287 iSon:22338 / iOrta: 22311 / Aradaki Eleman Say : 52
Daha küçük
....
(
Sıçra : 11) iBas:22287 iSon:22310 / iOrta: 22298 / Aradaki Eleman Say : 24
Daha küçük
....
(
Sıçra : 12) iBas:22287 iSon:22297 / iOrta: 22292 / Aradaki Eleman Say : 11
Daha BÜYÜK
....
 
Arama yapmak için kalan eleman sayısı : 5 


j29pqzcsv3thtpbz5gyd.gif


Bu örnek projenin kaynak kodları :

Uses System.Hash, System.StrUtils;

Var
 FArray : Array of String;

procedure RandomFill( aCount: Integer );
var
 i : Integer;
begin
 if Length(FArray) > 0 then Finalize(FArray);
 SetLength( FArray, aCount );
 for i := low(FArray) to high(FArray)
   do FArray[i] := THashMD5.GetHashString( IntToStr(i) );
end;

procedure SortArray;
var
 LTemp   : string;
 i       : Integer;
 LAgain  : Boolean;
begin
 repeat
   LAgain  := False;
   i       := low(FArray);
   repeat
     if CompareStr( FArray[i], FArray[i+1]) > 0 then
     begin
       LTemp       :=  FArray[i];
       FArray[i]   :=  FArray[i+1];
       FArray[i+1] :=  LTemp;
       LAgain      :=  True;
     end;
     Inc(i);
   until(i > High(FArray)-1 );
 until(LAgain = False);
end;

procedure TForm1.Button1Click(Sender: TObject);
const
  ArraySize = 52*1000; // 52K kayıt
var
  LTextFile : TextFile;
  LFilename : String;
  i         : Integer;
begin
  LFilename := ExtractFilePath( ParamStr(0) ) + 'StringArray_' + IntToStr(ArraySize) + '.TXT';
  if NOT FileExists(LFilename) then
  begin
    RandomFill( ArraySize );
    SortArray();
    AssignFile( LTextFile, LFilename );
    try
      ReWrite( LTextFile );
      for i := Low(FArray) to High(FArray) do
        WriteLn( LTextFile, FArray[i] );
    finally
      CloseFile(LTextFile);
    end;
    Showmessage('Sıralama ve doldurma tamam...');
  end else begin
    if Length(FArray) > 0 then Finalize(FArray);
    SetLength( FArray, ArraySize );

    AssignFile( LTextFile, LFilename );
    Reset( LTextFile );
    try
      i := 0;
      while NOT EOF(LTextFile) do
      begin
        ReadLn( LTextFile, FArray[i] );
        inc(i);
      end;
    finally
      CloseFile(LTextFile);
    end;
    Showmessage('Array doldurma tamam...');
  end;
end;

function SearchArray( aSrc : String; const aArray: Array of String ): boolean;
const
 MakulElemanSayisi = 10;
var
 i, LSayac, idxBas, idxSon, iOrta : Integer;
 LSicrama : Integer;
begin
 Result := False;

 idxBas := Low (aArray);
 idxSon := High(aArray);
 LSayac := High(aArray)+1;
 iOrta  := (idxSon - idxBas) div 2;
 LSicrama := 0;
 repeat
   form1.memo1.lines.Add( Format('(Sıçra : %d) iBas:%d iSon:%d / iOrta: %d / Aradaki Eleman Say : %d', [ LSicrama, idxBas, idxSon, iOrta, LSayac ]) );
   if aSrc > aArray[iOrta] then begin
     form1.memo1.lines.Add( 'Daha BÜYÜK....' );
     idxBas :=  iOrta+1;
   //idxSon := Aynı...
     iOrta  :=  iOrta + (idxSon - idxBas) div 2;
     LSayac := (idxSon - idxBas + 1);
   end else
   if aSrc < aArray[iOrta] then begin
     form1.memo1.lines.Add( 'Daha küçük....' );
   //idxBas := Aynı...
     idxSon :=  iOrta -1;
     iOrta  :=  idxBas + (idxSon - idxBas) div 2;
     LSayac := (idxSon - idxBas + 1);
   end
   else Result := True; // bulundu... :)
   Inc(LSicrama);
 until ( LSayac <= MakulElemanSayisi ) or Result;

 form1.memo1.lines.Add( Format(' Arama yapmak için kalan eleman sayısı : %d', [ LSayac ]) );
 i := idxBas;
 while (not result) AND  (i <= idxSon) do begin
   Result := aArray[i] = aSrc;
   inc(i);
 end;
end;

procedure TForm1.Button2Click(Sender: TObject);
var
 LSrc : String;
begin
 Memo1.Lines.Clear;
 LSrc := THashMD5.GetHashString( intToStr(51999) );
//if MatchStr( LSrc, FArray ) then Showmessage('Bulundu') else Showmessage('Maalesef.... ');
 if SearchArray( LSrc, FArray ) then Showmessage('Bulundu') else Showmessage('Maalesef.... ');
end;

Bu da 5 milyon kayıttaki bulma hızı... 18 + 8 = 26 sorguda...  ( o da 8. kayıttaysa... ) 

PHP Kod:
(Sıçra : 0) iBas:0 iSon:4999999 / iOrta: 2499999 / Aradaki Eleman Say : 5000000
Daha küçük
....
(
Sıçra : 1) iBas:0 iSon:2499998 / iOrta: 1249999 / Aradaki Eleman Say : 2499999
Daha BÜYÜK
....
(
Sıçra : 2) iBas:1250000 iSon:2499998 / iOrta: 1874998 / Aradaki Eleman Say : 1249999
Daha BÜYÜK
....
(
Sıçra : 3) iBas:1874999 iSon:2499998 / iOrta: 2187497 / Aradaki Eleman Say : 625000
Daha küçük
....
(
Sıçra : 4) iBas:1874999 iSon:2187496 / iOrta: 2031247 / Aradaki Eleman Say : 312498
Daha BÜYÜK
....
(
Sıçra : 5) iBas:2031248 iSon:2187496 / iOrta: 2109371 / Aradaki Eleman Say : 156249
Daha BÜYÜK
....
(
Sıçra : 6) iBas:2109372 iSon:2187496 / iOrta: 2148433 / Aradaki Eleman Say : 78125
Daha küçük
....
(
Sıçra : 7) iBas:2109372 iSon:2148432 / iOrta: 2128902 / Aradaki Eleman Say : 39061
Daha BÜYÜK
....
(
Sıçra : 8) iBas:2128903 iSon:2148432 / iOrta: 2138666 / Aradaki Eleman Say : 19530
Daha BÜYÜK
....
(
Sıçra : 9) iBas:2138667 iSon:2148432 / iOrta: 2143548 / Aradaki Eleman Say : 9766
Daha küçük
....
(
Sıçra : 10) iBas:2138667 iSon:2143547 / iOrta: 2141107 / Aradaki Eleman Say : 4881
Daha BÜYÜK
....
(
Sıçra : 11) iBas:2141108 iSon:2143547 / iOrta: 2142326 / Aradaki Eleman Say : 2440
Daha BÜYÜK
....
(
Sıçra : 12) iBas:2142327 iSon:2143547 / iOrta: 2142936 / Aradaki Eleman Say : 1221
Daha küçük
....
(
Sıçra : 13) iBas:2142327 iSon:2142935 / iOrta: 2142631 / Aradaki Eleman Say : 609
Daha küçük
....
(
Sıçra : 14) iBas:2142327 iSon:2142630 / iOrta: 2142478 / Aradaki Eleman Say : 304
Daha küçük
....
(
Sıçra : 15) iBas:2142327 iSon:2142477 / iOrta: 2142402 / Aradaki Eleman Say : 151
Daha BÜYÜK
....
(
Sıçra : 16) iBas:2142403 iSon:2142477 / iOrta: 2142439 / Aradaki Eleman Say : 75
Daha küçük
....
(
Sıçra : 17) iBas:2142403 iSon:2142438 / iOrta: 2142420 / Aradaki Eleman Say : 36
Daha küçük
....
(
Sıçra : 18) iBas:2142403 iSon:2142419 / iOrta: 2142411 / Aradaki Eleman Say : 17
Daha küçük
....
 
Arama yapmak için kalan eleman sayısı : 8 
Hocam, yanılmıyorsam %5 civarında bir hız artışı oldu, MatchStr ile 930/sn işlem yaparken, sizin kodunuz ile 980/sn civarı işlem yapıyor görünüyor, tabi hata olmaması için farklı birkaç cihazda daha kontrol edicem.
Üstadım şöyle dene. Kayıtlarındaki en sondaki satırdakini 1000 kere ara o zaman daha net anlaşılır.
akşam bolca deneme yapıcam inşallah hocam, bundan sonraki aşama bu işlemleri GPU ya yaptırmak olucak ama sanırım oda pascal ile olmayacak Sad
Sayfalar: 1 2