Optimizarea buclelor imbricate # 1

La început a fost cuvântul sau, mai degrabă, ideea sau ... proiectarea pentru a continua.

Când scrieți un program care calculează cuvinte încrucișate Sudoku, mai întâi a fost nevoie de






cicluri imbricate de o adâncime de cinci, și apoi până la nouă
cicluri. Apoi a fost nevoie de
optimizare. Mai ales că versiunea finală cu un algoritm simplificat simplificat (pe de o parte) conținea deja ... douăzeci și șapte
bucle imbricate. În plus, Pascal de la unchiul Borman, începând cu Turbo Pascal'ya și chiar până la cele mai multe Delphi, în rolul indexului nu poate fi folosit la toate matricea. Ie dacă ciclul dvs. este destul de adânc, de exemplu, până la 5
etaje, atunci trebuie să utilizați variabila pentru fiecare atașament.

Ie în secțiunea de descriere pe care o scriem, de exemplu, după cum urmează:

Var i1, i2, i3, i4, i5. octet;

Și în secțiunea de execuție, respectiv:

Pentru i1: = 1 la 2 nu
Pentru i2: = 1 la 3 nu
Pentru i3: = 1 la 4 nu
Pentru i4: = 1 până la 5 nu
Pentru i5: = 1 la 6 face SomeProcedure;

Vom automatiza această anomalie algoritmică. În plus, imaginați-vă un ciclu de monstru,
care are 27 atașamente!

Pentru această cercetare științifică în rolul unui ciocan cu unghii, nu avem nevoie de nimic: Turbo Pascal și Debugger Turbo pentru Dos - suficient de deasupra acoperișului. În plus, sunt necesare instrumente
lemn de foc sub forma mâinilor și capului tău direct cu o substanță gri de calitate (abilitatea de a te ruga lui Dumnezeu Pascal scriind codul corespunzător este cel puțin binevenită).

Mai întâi de toate, datele nu merg singure, iar procedurile și funcțiile nu sunt plictisite undeva,
ambele sunt unite sub steagul OOP.

În primul rând, începem să ne proiectăm obiectul. Dar, pentru a fi clar imediat, "trageți" schema potrivită. Lăsați rolul iepurelui experimental să fie un ciclu cu o adâncime de cinci:

Pentru i [1]: = Dn [1] la Sus [1] nu
Pentru i [2]: = Dn [2] la Sus [2] nu
Pentru i [3]: = Dn [3] la Sus [3] nu
Pentru i [4]: ​​= Dn [4] la Sus [4] nu
Pentru i [5]: = Dn [5] la Sus [5] face MainProc;

Ce piese de schimb pentru facilitatea noastră de aici puteți fura deja? Această variabilă indice (masa exactă) i, limita inferioară a - matrice Dn, iar partea de sus, respectiv sus și procedura MainProc, care este procedura utilizată în mod repetat ciclul nostru. În plus, datorită faptului că destul de dificil de a veni cu o scurtă și precisă din titlu, această procedură și am numit principalul (cu atât mai mult, deoarece toate acestea tam-tam pentru ea și planificate), care se reflectă în MainProc său nume.

În Turbo Pascal, deschideți biblioteca unde locuiește obiectul nostru și mergeți să descoperiți ce este în el.

Iată descrierea obiectului:

TLoopRunner = obiect
i, Dn, Sus. TByteArray10;
Adâncimea. octet;
MainProcAddr: Pointer;
ParamsStackIndex: octet;
RunItProcOfs: cuvânt;
CallCodeOfProcToLoopOfs: cuvânt;
Constructor Init (SomeProcAddr: Pointer;
SomeDepth: octet;
SomeDn, SomeUp: TByteArray10);






Procedură RunIt; virtuale;
End;

Acum, ce cuvinte ciudate au apărut TByteArray10 și Pointer în scrierile noastre? E ușor. În secțiunea de tip, adică Tip, TByteArray10 este descris ca o matrice de zece
bytes:

TByteArray10 = array [1..10] de byte;

Acum, avem nevoie de acțiuni care să transforme obiectul nostru într-un ciclu multidimensional. În primul rând despre constructor. Deși, în ansamblu, a fost posibilă o procedură simplă, dar întrucât această procedură trebuie efectuată mai întâi, ea este înzestrată și cu statutul de designer. Și numele este de asemenea standard, ca toți designerii săi.
init:

Constructor Init (SomeProcAddr: Pointer; SomeDepth:
octet; SomeDn, SomeUp: TByteArray10);

Apoi încă o acțiune, în care se află ciclul nostru. Se numește RunIt, adică efectua. El nu va avea parametrii - ei nu au nevoie de el, dar vor fi virtuali și nu pentru că sunt la modă, ci pentru că ne va simplifica munca de a ne reînvia propriul obiect:

Procedură RunIt; virtuale;

Procedură PushParam (AParamAddr: Pointer; AParamType: TParametersTypes);

Apropo, ce parametri pot fi transmise procedurii sau funcției? Pentru a nu ne rafina creierul, vom enumera cele standard prin adăugarea prefixului pt la fiecare nume (pentru că TParametersTypes). Această enumerare este situată în secțiunea din tipurile de biblioteci:

TParametersTypes = (ptByte, ptShortInt, ptWord, ptInteger, ptLongInt, ptReal, ptString, ptArray);

Parafrazând un personaj, putem spune: "Am proiectat, proiectat și proiectat în cele din urmă. “. Ce trebuie adăugat aici, cu excepția unui simplu "da"?

În procesul de întrupare

Acum, de la flori la fructe de padure, adică ne gândim cum se realizează și funcționează întreaga economie.

Mai întâi de toate, corpul ciclului nostru cu mai multe etaje este în procedura RunIt, care, întâmplător, ca toate procedurile decente, este descrisă în secțiunea de încarnări, adică după implementarea cuvântului. Și imediat observați că cuvântul magic virtual a dispărut și în loc să vină nu mai puțin decât asamblorul de cuvinte magice și locul cuvântului a început să ia cuvântul asm - procedura este făcută din asma pură:

Procedură TLoopRunner.RunIt; de asamblare;
asm
End;

În plus, procedura constă în principal din unsprezece (zece - buclele noastre imbricate, și al unsprezecelea. - Codul numesc MainProcAddr mod de rutină principal, aduce zece pur și simplu nu are sens - ele sunt de același tip, este probabil că nuanțele în primul și al zecelea pentru a arăta. modul în care tranziția de la un ciclu la altul, în plus față de prima subrutină pentru a lua o secundă.), după cum a spus mai devreme, rutine, și ne vom referi, de asemenea, la aceste părți ale cazului.

Acum, să aruncăm o privire asupra codului pe care procedează procedura noastră RunIt (de altfel, codul a fost obținut de la debuggerul Turbo Debugger):

Întoarceți din stivă valoarea bp, care
l-am salvat la intrarea în procedură.

Dacă vă uitați la etajele următoare, veți vedea aproape același cod. Diferențele vor fi în "aditivii" pentru
di registru pentru a obține adecvat de compensare pentru accesul la elementele de matrice rămase i, Dn și Up. De exemplu, pentru etajul al doilea, respectiv, acesta va fi numărul 2, și 0Sh 16h. În plus, toate celelalte etaje ne întoarcem la anterioare nu mai reveni, de exemplu, retf'om nu, ci pur și simplu ret'om, pentru că suntem cu toții în aceeași procedură RunIt, ceea ce înseamnă că - în același segment de cod, așa că trebuie să ne întoarcem pentru a schimba doar valoarea registrului IP și cs nu atingeți. Mai mult decât atât, pentru a reveni la podea, nu trebuie să scrie instrucțiunile de cod retur mnemonice, și anume, nu ret, și codul acestei instrucțiuni - db 0C3h. Aici, este evident că, datorită faptului că procedura este declarată ca RunIt de asamblare, atunci Pascal numit Turbo consideră toate ret'y lung și stick-uri
codul de returnare corespunzător lung (puteți vedea pentru dvs. prin schimbarea undeva db 0C3h la ret).

Și un cuvânt separat despre podeaua a zecea. Dacă, de exemplu, de la primul etaj la al doilea, vom merge pe „scara» suna @@ Loop02_Begin, nu are nimic de la etajul al zecelea, astfel încât a zecea ne-am merge imediat înapoi la ret din cauza codului de instrucțiuni nouă, și anume, 0S3h (după această instrucțiune sunt două nop'a, adică cu un cod de retur de 3 octeți primi - doar ceea ce ai nevoie pentru a intra în acest loc, dacă este necesar, instrucțiunile suna rutina principal și de ce este necesar. - aflați mai jos).

Distribuiți acest articol cu ​​prietenii dvs.:







Articole similare

Trimiteți-le prietenilor: