Delphi Can

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;

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  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 
  
• MD5 string halindeki indexlenmiş haldeki 5 milyon adet hash içeren text dosya linki için 
  

* 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. 





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... ) 

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