![]() |
|
Array of Stings içerisinde arama yapma - Baskı Önizleme +- Delphi Can (https://www.delphican.com) +-- Forum: Delphi (https://www.delphican.com/forumdisplay.php?fid=3) +--- Forum: Genel Programlama (https://www.delphican.com/forumdisplay.php?fid=6) +--- Konu Başlığı: Array of Stings içerisinde arama yapma (/showthread.php?tid=6061) Sayfalar:
1
2
|
Array of Stings içerisinde arama yapma - esistem - 04-06-2021 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? Array of Stings içerisinde arama yapma - mrmarman - 04-06-2021 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;
Array of Stings içerisinde arama yapma - esistem - 05-06-2021 Teşekkürler Hocam, anlaşılan MatchStr kullanmaya devam edicez. Array of Stings içerisinde arama yapma - mrmarman - 05-06-2021 Ü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 ? Cvp: Array of Stings içerisinde arama yapma - esistem - 05-06-2021 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. Array of Stings içerisinde arama yapma - mrmarman - 05-06-2021 @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
* 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 : 52000Bu ö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;
Array of Stings içerisinde arama yapma - mrmarman - 05-06-2021 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 : 5000000Array of Stings içerisinde arama yapma - esistem - 05-06-2021 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. Array of Stings içerisinde arama yapma - mrmarman - 05-06-2021 Üstadım şöyle dene. Kayıtlarındaki en sondaki satırdakini 1000 kere ara o zaman daha net anlaşılır. Array of Stings içerisinde arama yapma - esistem - 05-06-2021 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
|