Optymalizacja pętli - propozycje

Odpowiedz Nowy wątek
2006-12-30 23:06
0

Jak w temacie. Muszę zoptymalizować petlę generującą raport roczny dla mojej bazy. Nie zaciemniając kodu pętla przeszukuje taką oto strukturę:

type
  TTab = array [1..8, 1..12, 1..31, 1..2, 1..600] of string[3];
  TTabelaWynikow = array [1..100] of LongWord;
  TWzorce = array [1..100] of string[3];

Pętle 1..8, 1..12, 1..31, 1..2 wykonują się całe (zawsze => 5952 iteracji). Dochodzimy do sedna problemu: pętla 1..600 . I tu własnie szukam optymalizacji. 1..600 to ilość sztuk, która jest zmienna, czyli pętla wykonuje się w zależności od zmiennej Wyniki.All. To też nie problem Jeżeli Wyniki.All = 0 to Break.
Tablica przechowuje dane typu: E29..E40, M24..M36, W03..W99. Litera to typ, cyfra to indeks. Całość wzorców mam w tablicy 1..100. Zrobienie raportu polega na wyliczeniu ile razy dany błąd wystąpił czyli mamy

for i := 1 to 8 do
 for j := 1 to 12 do
  for k := 1 to 31 do
   for l := 1 to 2 do
    for m := 1 to Wyniki.All do
     for n := 1 to 100 do
      if Tab[i, j, k, l, m] = Wzorce[n] then Inc(TabelaWynikow[n], 1);

Jak maksymalnie przyspieszyć wyszukiwanie odpowiedniego wzorca. Możecie dać propozycje? Celowo nie zamieszczam mojego rozwiązania aby nic nie sugerować.

// Dopisane: sam nie wiedziałem czy ten temat bardziej pasuje do IO czy do delphi lub może do nietuzinkowych tematów (optymalizacja to jednak złożone zagadnenie. Prośba do modów o przeniesienie do odp. działu. Pozdrawiam.


<span style="color: blue">"Kolarstwo to jedna z najtrudniejszych dyscyplin sportu. Nawet najgorszy kolarz jest wciąż wybitnym sportowcem."
s.p. Marco Pantani
</span>

Pozostało 580 znaków

2006-12-31 01:57
0

Nie wiem czy dobrze rozumiem: masz do przeszukania 812312m trzyliterowych stringów (n - zmienna 1..600), z których dwie litery stanowią cyfrę - jeśli string znajduje się we Wzorce pod indeksem n, w TabelaWyników zwiększasz element n - licznik wystąpień.. ?

Proponuję wcześnie string[3] we wzorcach i tabeli wejściowej pozamieniać przez jakieś zrzutowanie na DWORD - też 4 bajty (jak pominiesz długość to 3 i jeden wolny) - porównanie może być szybsze, lub chociaż porównywać jako:
(PDWORD(PCHAR(@Tab[i, j, k, l, m]))sup>=PDWORD(PCHAR(@Wzorce[n]))</sup)

Zamieszane co? Zrobiłem test:

var a,z:string[3];
    n,m,f:int64;
    l:longint;
    res:boolean;
begin
a:='aaa';
z:='aaa';
QueryPerformanceFrequency(f);
QueryPerformanceCounter(n);
for l:=0 to 1000000000 do
  begin
//WARIANT1: 2,2s
  res:=res and (PDWORD(PCHAR(@a))^=PDWORD(PCHAR(@z))^); 

//WARIANT2: 8,3s
//  res:=res and (a=z);
  end;

QueryPerformanceCounter(m);
if res then
  Caption:='Dobrze '+FloatToStr((m-n)/f)
else
  Caption:='Zle '+FloatToStr((m-n)/f);
end;

Czasy mówią same za siebie.

Podobne rezultaty daje rzutowanie bezpośrednie:

type myunit = record
     case boolean of
     TRUE: (text:string[3]);
     FALSE: (val:DWORD);
     end;
var a,z:myunit;
    n,m,f:int64;
    l:longint;
    res:boolean;
begin
a.text:='aaa';
z.text:='aaa';
QueryPerformanceFrequency(f);
QueryPerformanceCounter(n);
for l:=0 to 1000000000 do
  begin
//WARIANT1: 2,2s
  res:=res and (PDWORD(PCHAR(@a))^=PDWORD(PCHAR(@z))^); 

//WARIANT2: 8,3s
//  res:=res and (a.text=z.text);

//WARIANT3: 2,1s
//  res:=res and (a.val=z.val);
  end;
QueryPerformanceCounter(m);
if res then
  Caption:='Dobrze '+FloatToStr((m-n)/f)
else
  Caption:='Zle '+FloatToStr((m-n)/f);
end;

Od razu zaznaczę, że porównuje prawidłowo.

Dodatkowo wszystkie pętle licz

for i:=koniec-1 downto 0 do

Gdy indeksujesz tym tablicę, kod nie jest optymalizowany automatycznie, a przy tylu pętlach nawet to przyspieszy. Pamiętaj tylko, by również same tablice liczyć od 0.


<font color="red">Konto porzucone</span>

Dzięki wszystkim forumowiczom za lata wspólnych dyskusji; miłej zabawy w programowanie!
Sławomir 'Szczawik' Włodkowski

Pozostało 580 znaków

2006-12-31 10:55
0

Mogłem to napisać na początku. Wzorce w pliku przechowywane są alfabetycznie. Zastanawiam się nad bezpośrednim skokiem w odpowiednie miejsce w tabeli wzorców. Wówczas zamiast pętli 1..100 będę miał np 30..41.

// Dopisanie: Zastanawiam się też nad rozbiciem pętli 1..8 na osobne wątki.


<span style="color: blue">"Kolarstwo to jedna z najtrudniejszych dyscyplin sportu. Nawet najgorszy kolarz jest wciąż wybitnym sportowcem."
s.p. Marco Pantani
</span>

Pozostało 580 znaków

2007-01-01 19:03
0
Szczawik napisał(a)

...Proponuję wcześnie string[3] we wzorcach i tabeli wejściowej pozamieniać przez jakieś zrzutowanie na DWORD - też 4 bajty (jak pominiesz długość to 3 i jeden wolny) - porównanie może być szybsze...

Skoro tak, to można jeszcze troszkę zoptymalizować przechowywanie danych: mamy jedyne możliwości to duża litera na pierwszym miejscu i dwie spośród 10 cyfr na pozostałych dwóch miejscach, więc wychodzi powiedzmy 2600 możliwości, a to da radę w 2 bajtach zmieścić. Więcej obliczeń byłoby wykonywanych wtedy przy pobieraniu danej wartości lub jej wyświetlaniu.

Oleksy_Adam napisał(a)

Wzorce w pliku przechowywane są alfabetycznie. Zastanawiam się nad bezpośrednim skokiem w odpowiednie miejsce w tabeli wzorców
No, i wtedy wystarczy przechowywać początkowe i końcowe indeksy dla każdej litery w osobnej tablicy i będzie dobrze.

Pozdrawiam.

Pozostało 580 znaków

2007-01-01 19:32
0
Oleksy_Adam napisał(a)

// Dopisanie: Zastanawiam się też nad rozbiciem pętli 1..8 na osobne wątki.

Jeśli nie ma to działać na procesorze P4HT albo wielordzeniowym albo w sieci (np.: MOSIX), przyniesie tylko stratę.


<font color="red">Konto porzucone</span>

Dzięki wszystkim forumowiczom za lata wspólnych dyskusji; miłej zabawy w programowanie!
Sławomir 'Szczawik' Włodkowski

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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