Ubrzati search kroz TStringList

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Imam StringGrid koji u prvoj (nultoj) koloni sadrzi imena fajlova, a u drugoj koloni MD5 hashsumm tih fajlova.

Drugi elemenat je lista koja sadrzi slicnu strukturu. Jedna linija u listi sadrzi ime fajla, pa ";" kao delimiter, pa MD5 hash (filename.ext;MD5hash)

Program treba da proveri za svaki fajl iz StringGrida da li postoji u StringListi (DBList u kodu dole) fajl sa istim MD5 hashom, i u trecu kolonu StringGrida upisuje da li je fajl vec poznat.

To kod mene sada izgleda ovako:
procedure TfrmMain.btCompareClick(Sender: TObject); var   i,j: integer;   posComma: integer;   tmpStr: string; begin   frmMain.Caption := 'I know you (working...)';   for i := 0 to StringGrid1.RowCount -1 do   begin     if cancelOP then break;  //na formi postoji dugme Cancel koji setuje cancelOP := true     application.ProcessMessages;     for j := 0 to DBList.Count -1 do     begin       if cancelOP then break;       application.ProcessMessages;       if AnsiContainsStr(DBList[j], (';' + StringGrid1.Cells[1, i])) then       begin         posComma := pos(';', DBList[j]) -1;         tmpStr := copy(DBList[j], 1, posComma);         StringGrid1.Cells[2, i] := 'Known as ' + tmpStr;         StringGrid1.Selection := rect(0, i, 3, i);  //ovaj i sledeca tri reda su kozmeticke prirode         if i > 15 then StringGrid1.TopRow := i - 10           else StringGrid1.TopRow := i;         application.ProcessMessages;         break;       end;     end;   end;   if not cancelOP then compared := true;   frmMain.Caption := 'I know you';   cancelOP := false; end;

Problem je sto radim sa velikim kolicinama podataka, tako da je ova moja Search metoda ocajno spora. Zna li neko nacin kako bi mogao da je ubrzam?

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Malo mi je konfuzan tvoj nacin programiranja, ali ajde...

sto ovo ne radis na kraju?!

StringGrid1.Selection := rect(0, i, 3, i); //ovaj i sledeca tri reda su
if i > 15 then StringGrid1.TopRow := i - 10 else StringGrid1.TopRow := i;


Ovo je ubitacno sporo. Narocito sto dodajes StringGrid1.Cells...
if AnsiContainsStr(DBList[j], (';' + StringGrid1.Cells[1, i])) then


Mislim da ti je cela ideja pogresna. Zasto bi uopste pretrazivao po string gridu?! Ti podaci su negde (baza, fajl, lista). Zasto ne pretrazis samo tvoj storage?

Takodje, besomucno pozivanje Application.ProcessMessages takodje znatno usporava.

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

StringGrid se puni klikom na dugme imenima fajlova iz nekog foldera.
Zajedno sa upisivanjem imena fajlova u prvu kolonu, paralelno se u drugu kolonu upisuje MD5 fajla.

Taj Selection mi sluzi samo da bi se vizuelno na Gridu videlo do kog se fajla stiglo, i ne oduzima neko znacajno vreme u procesiranju.

Cells se ne dodaju, samo se u njih upisuje. StringGrid odgovarajuce velicine se formira odmah nakon sto se utvrdi koliko fajlova ima u foderu, znaci nema dinamickog menjanja velicine grida.

Moj problem je search rutina koja je oblika:
for i := 0 to velicinaGrida do begin   for j := 0 to velicinaListe do     begin        if j=i then          begin             upisi_u_grid_da_je_nadjeno;             break; //nemoj vise da trazis do kraja liste posto je vec nadjen          end;     end; // prosli smo celu listu u potrazi za jednim elementom grida end; // ajmo opet za sledeci element grida
Sve ostalo u gornjem kodu je kozmetika.
Bez onih application.procesmessages dobar deo vremena imam beli prozor aplikacije, posto se interfejs ne osvezava jer je aplikacija u petlji.

Lista i grid su mi velicine 100.000 elemenata, pa uporedjivanje ume da potraje i preko 10 minuta, to me nervira.

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Pa dobro... s obzirom da uporedjujes stringove, to i nije neko vreme. Meni je zamena stringova u bazi potrajala i preko toga. String je jednostavno spor.

Da koristis bazu, onda bi tu binary search pomogao, ali ovako.. stvarno ne znam sta da ti kazem.

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Jedino da koristis thread cisto da mozes da radis sa appom, dok u pozadini thread radi svoj posao.
Mozda ce i to donekle da ubrza proces.

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Snoop... nece. Jedino da threadu das HIGH prioritet.
Onaj loop samo moze da se ubrza da se izvede na drugi nacin. Ja bih izbegao string grid, posto je nepotreban i spor, i koristio TListView, tj. koristio bih moj TRPCBuffer a ListView samo koristio za prikaz.

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

TListView.IndexOf koristi binarni search ukoliko je lista sortirana (Sorted propertie), barem koristi u FPC-u.
Problem je sto, da bih koristio sortiranu listu, morao bih da menjam kako mi se podaci cuvaju u listi, tj. da u listi cuvam samo MD5.

Izgleda da je to jedino resenje.

Sto se tice StringGrid, ne bih se slozio sa belijem da je spor, primera radi, StringGrid velicine 50.000 x 7 popunjavam podacima za manje od 3 sekunde na Lazarus/FPC-u.

Da objasnim jos i sta treba da radi ovaj program, pa mozda neko od vas ima bolju ideju:
- imam vise od 100.000 sortiranih fajlova u jednoj arhivi (virusi, trojanci i slicno)
- svakodnevno dobijam jos na stotine, od kojih 99% vec imam
- da ne bih svaki put morao da analiziram nove fajlove da bih utvrdio koji vec imam, resio sam da napravim prost program koji ce da ima malu bazu onoga sto vec imam (pamti se MD5 hash fajla), pa kad dobijem nove fajlove, on mi na osnovu hasha kaze da li fajl vec imam ili ne.
- ovo mora preko hasha iz vise razloga
- ovo mora preko baze iz razloga sto meni fajlovi stizu pakovani i arhivirani na najrazlicitije nacine, i ubacujem ih u kolekciju tek nakon sto izvucem cist fajl. Ovaj program mi pamti MD5 oba oblika (spakovanog i raspakovanog), tako da kada mi sledeci put naidje pakovan - ja znam da sam se vec jednom mucio da raspakujem taj fajl. Iz ovog razloga ne bih mogao da koristim prosto poredjenje fajlova u folderima da bih video da li novi fajl imam u kolekciji ili ne, jer ga u kolekciji nemam pakovanog.

Znaci, cilj programa je da mi pomogne da izbegnem da po hiljadu puta raspakujem iste fajlove, da ih na kraju utvrdio da ih vec imam raspakovane.

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Ako stvarno hoces brzinu, prepakuj sve to na PgSQL i koristi binary search nad bazom i ubrzaces ga par stotina puta. Sve sto ima preko 1000 registara, vredi stavljati na server bazu. Trust me.

• 0Niko još nije pohvalio poruku.
  Registruj se da bi pohvalio/la poruku!

Moracu nekako bez baze, jer je ideja da program bude portabilan, tj. bez instalacije...

Dopuna: 11 Jul 2006 15:31

Evo resenja koji radi search za jednu sekundu na bazi od 10.000 stringova, i sa isto toliko stringova u gridu za uporedjivanje:
procedure TfrmMain.btCompareClick(Sender: TObject); var   i: integer;   DBindex: integer;   sl: TStringList;   slRes: TStringList; begin   frmMain.Caption := 'I know you (working...)';   sl := TStringList.Create;   slRes := TStringList.Create; //rezultat pretrage   try     sl.AddStrings(StringGrid1.Cols[1]);     for i := 0 to sl.Count -1 do     begin       if cancelOP then break;       DBIndex := DBList.IndexOf(sl[i]);       if DBIndex <> -1 then         slRes.Add('Known as ' + DBList[DBIndex])       else slRes.Add('');     end;     StringGrid1.Cols[2] := slRes;   finally     sl.free;     slRes.Free;     if not cancelOP then compared := true;     frmMain.Caption := 'I know you';     cancelOP := false;   end; end;     

Fora je sto sam morao da promenim i strukturu baze (liste koja izigrava bazu), tako da sada sadrzi samo MD5 hash, a ne vise (imefajla;MD5hash),
sto u sustini zavrsava posao.

Dopuna: 11 Jul 2006 15:33

Zaboravih, bitno je i sledece da bi se dobilo na brzini:

DBList.Sorted := true;
DBList.Duplicates := dupIgnore;