przyspieszenie algorytmu

0

porównuje zawartość dwóch plików i oto mój kod. są to duże pliki
mające po 100 tys lini (pliki rejestru). pytanko- czy dało by się to
jakoś przyspieszyć?? w programie porównuje tylko nazwy kluczy- już bez
żadnych wartości. Jakby ktoś chciał zobaczyć całość to śmiało
niech pisze.może jakby pliki były posortowane ewentualnie używać innego
komponentu niż memo. - czekam na propozycje. pozdrawiam

procedure TForm1.Button3Click(Sender: TObject);
var
i,k,z:integer;
jest:boolean;
begin
for i:=0 to memo1.Lines.Count-1 do
begin
memo4.Lines.Add('');
z:=memo1.Lines.Count-1-i;
memo4.Lines[i]:=IntToStr(z); // pokazuje ile zostało do zakączenia
jest:=false;
for k:=0 to memo2.Lines.Count-1 do
begin
if memo1.Lines[i]=memo2.Lines[k] then
begin
jest:=true; //jeśli dwa klucze identyczne to nic nierobie
break;
end;
end;
if jest=false then
begin
memo3.Lines.Add('');
memo3.Lines[licz]:= IntToStr(licz+1) + ' '+ memo1.Lines[i];
licz:=licz+1;
end;
end;
end;

0

Ja proponuję zastosować wątki i zamiast raz uruchamiać pętlę

for k:=0 to memo2.Lines.Count-1 do 

uruchomić powiedzmy trzy pętle z innym punktem startowym i końcowym np. pierwsza pętla niech sprawdza od 0 do (memo2.Lines.Count-1) mod 3
druga od (memo2.Lines.Count-1) mod 3 do 2*((memo2.Lines.Count-1) mod 3
)
a trzecia od 2*((memo2.Lines.Count-1) mod 3) do końca czyli do memo2.Lines.Count-1

o wątkach jest artykuł na 4programmers - na pewno znajdziesz

0
Artur napisał(a)

Ja proponuję zastosować wątki i zamiast raz uruchamiać pętlę (...) uruchomić powiedzmy trzy pętle z innym punktem startowym i końcowym

twierdzisz, że to przyspieszy algorytm na jednoprocesorowym systemie? nawet na P4 z HT to w zasadzie nic nie da.

proponuję posortować oba pliki (złożoność sortowania n*logn) i wyszukiwać zmiany binarnie (złożoność wyszukiwania logn).

0

Myślę, że przyspieszy - dlaczego? A dlaczego widzimy przyspieszenie wyszukiwania plików jak zastosujemy wątki? Odsyłam do książki adama Boducha - Delphi. Kompendium Programisty. Kolejna sprawa wtedynasz program zajmuje trochę więcej pamięci - bo działają trzy wątki które robią tę samą czynność a nie jeden wątek - kosztem pamięci zyskujemy na szybkości

// program zajmuje więcej pamięci RAM -> więcej pamięci L2 i L1 -> nie mieści się w cache procesora -> wątki nawzajem wyrzucają się z cache -> synchronizacja cache z RAM -> wolniejsze działanie programu. oczywiście jest to sytuacja możliwa, ale nie stuprocentowa. - Ł

0

Jeszcze jeden pomysł - załadować wszystko do tablicy dynamicznej i porównywać odpowiednie elementy tablicy - operacje zczytania z Memo i porównania są dłuższe niż operacje na tablicach

0

A może nie ładuj do memo1 i memo2 tych plikow tylko jedna linijke do jakiejs zmiennej porownywaj i jesli inne/takie same/ co tam jeszcze wymyslisz to dopiero wsadz do tego wspolnego memo albo co tam jeszcze innego chcesz :)?

0

Pierwsza i najważniejsza rzecz: Memo nie służy do przechowywania linijek tylko do wyświetlania ich. Jak już musisz ładować wszystko do pamięci, to lepiej wykorzystaj TStringList.

Ale tutaj, to ja bym w ogóle z rezygnował z takiego podejścia. Najchętniej to bym przepuścił przez sort a potem diff i się za bardzo nie męczył w kodowanie, ale ponieważ raczej tego nie możesz zrobić, to proponuję skorzystać z podpowiedzi ŁF. Sortowanie powinno przyspieszyć operacje.

A co do pomysłu z wątkami, to polemizowałbym, czy na pojedynczym procesorze przyspieszyłoby to nam coś.
Jeżeli mamy dla przykładu wykorzystać liczby z tablicy przedziału <0;99> to jeżeli zrobimy to w 1 pętli to wykonamy 100 operacji. Powiedzmy, niech każda zajmuje 1s. Czyli czekamy 100s.

A teraz podzielmy sobie ten przedział na 3:
I - <0;33>, II - <34;66>, III - <67;99>
Więc pierwsze zostanie wyliczone w ciągu 34s, drugie 33s i trzecie 33s, jeżeli byłoby wykonywane pojedynczo.
Ponieważ walniemy to w wątkach, to będziemy mieli złudzenie, że wykonuje się równolegle, ale będzie się w rzeczywistości wykonywać np. tak:
2s z I, 2s z II, 2s z III, 2s z I, 2s z II...
I tak dalej. Pomimo, że będziemy obserwować, że każdy fragment wykonuje się jakby w tym samym czasie co pozostałe, to łączny czas trwania operacji będzie co najmniej równy temu, który byśmy mieli wykonując w jednej pętli. Co więcej, przy wątkach należy jeszcze doliczyć koszty przełączania się.

Jak widać, wątki są tutaj zdecydowanie nie potrzebne, a wręcz szkodzą (spowalniają i zaciemniają obraz algorytmu).

0

Dryobates -niestety nie zgodze sie Toba.Sprawdzilem to porownujac zawartos dwoch mem w jednym watku i w 2 ,4.Roznica powalajaca.Przy dwoch watkach porownuje 2-3 razy szybciej a przy 4 okolo 5-6 razy.

pozdrawiam

0

Mamy dwie tablice a[m] oraz b[n], powiedzmy, że m>n.
Tak jak zrobiło R_Jarek potrzeba nm kroków.
m
n > mlog(n)>nlog(m)
Trzy sposoby:

  1. posortujmy a[] (O(mlog m)), wyszukiwanie binarne b[1..n] w a[] O(nlog(m))
  2. sortujemy b[] (O(n* log n)). Szukamy a[1..m] w b[], O(m*log(n))
  3. posortujmy obie, wtedy sprawdzenie będzie kosztować O(n+k), k<=m-n.
0

a może tak:

stwórz sobie jakas funkcję mieszającą. tj taką funkcję która stringowi przyporządkuje jakąś liczbę z zakresu 0..cZakres.

stwórz tablicę obiektów TStringList o długości cZakres.

wczytaj jakąś nazwę klucza z pierwszego pliku i dodaj ją do listy o indeksie równym wartości funkcji mieszającej dla tej nazwy. zrób to dla wszystkich nazw kluczy z pliku 1.

teraz, dla każdego klucza z pliku 2 oblicz warosc funkcji mieszającej, weź listę z indeksu tej wrtości i poszukaj tego klucza na tej (krótkiej) liście. jeśli jest, wypisz/zapisz gdzieś nazwę klucza

jeśli cZakres będzie odpowiednio duże wówczas listy będą krótkie i ich przeszukiwanie będzie szybkie. jednak wzrośnie też rozmiar tablicy obiektów list i zaczną się problemy z pamięcią.

dla małego cZakres listy będą długie i efektywność indeksowania będzie mała. w szczególności dla cZakres=0 wszytkie nazwy trafią na tą samą listę i działanie sprowadzi się do porównania każdego z każdym.

0

ale się obudziliście - ten wątek ma TRZY lata.

0

a do tego jak zwykle czyta(ją) piąte przez dziesiąte :P
przyspieszenie po użyciu wątków będzie widoczne na procesorze więcej niż jednordzeniowym, mamy 2008 więc się nie zdziwię jak masz ich 4 kolego jakiś tam 3 posty wyżej Patryku chyba.

1 użytkowników online, w tym zalogowanych: 0, gości: 1