Încă urmărim "actualizarea" principiilor de lucru ale programului prezentat în [1] şi vizăm acum subrutina 'engine.s', care are de construit orarul propriu-zis al unei zile. Deocamdată ne ocupăm aici de constituirea datelor necesare acestei subrutine, într-un format cât mai convenabil exploatării lor la nivelul limbajului de asamblare.
Presupunem că avem un fişier 'schema_1.txt' conţinând repartiţia orelor pentru una dintre zile; redăm aici un caz cu număr mic de clase:
vb@Home:~/_ORAR$ pr -3 -t schema_1.txt
Ailioaei AD Cocuz BDbf Solomon BFbe
Badea BDEce Ianul ef Sirbu ABCFae
Bojescu BCabd Iovu EF Tudorache Ed
Busuioc Ccdf Lupu AAcd Tanase Db
Butnaru Cabc Neagu acd Taune bf
Ceru C Prelipcean ABFde Ungureanu DEFa
Ciubotaru Ff Racovita AEcf Vatamanu CEae
Am folosit programul utilitar pr (din GNU coreutils) - redând mai scurt (pe 3 coloane), conţinutul unui asemenea fişier; am evitat caracterele româneşti - de exemplu 'Vătămanu' ocupă 10 octeţi (nu 8) şi aş fi avut atunci de şters manual nişte spaţii, pentru a păstra alinierea pe coloană.
Clasele au fost înregistrate prin câte o literă; de exemplu, 'Tanase' are în ziua respectivă 2 ore - la clasele 'D' şi 'b'. Putem folosi awk, pentru a afla câte ore sunt în total, pe ziua respectivă:
vb@Home:~/_ORAR$ awk '{nore += length($2)} END{print nore}' schema_1.txt 71 # numărul total de ore
(s-au însumat lungimile câmpurilor de rang 2, de la fiecare linie a fişierului - afişând totalul)
Sarcina subrutinei 'engine' constă în a aşeza orele fiecărui profesor pe un câmp de lungime 7 (având cel mult 6-7 ore pe zi, la oricare clasă), în aşa fel încât o clasă oarecare să nu figureze pe o aceeaşi poziţie la profesori diferiţi (adică să nu existe suprapuneri de ore), poziţiile în care apare o aceeaşi clasă în ansamblul orarului să fie consecutive (să nu existe "ferestre" în orarul vreunei clase) şi deasemenea, poziţiile claselor profesorului să fie consecutive (să nu existe "ferestre" în orarul vreunui profesor).
Intenţionând să folosim backtracking, devine foarte importantă ordonarea prealabilă a datelor. Cea mai convenabilă ordonare pare a fi aceea care are în vedere numărul de ore ale profesorului (întâi cei cu 6 ore, apoi cei cu 5 ore, ş.a.m.d.) şi eventualele opţiuni (de exemplu, dacă are mai puţin de 5 ore - ar putea opta pentru a începe de la prima oră, sau de la a doua, etc.)
În plus, este important să avem în vedere şi numărul de clase comune: eşuând plasarea orei 'A' la profesorul curent, trebuie să asigurăm revenirea cât mai "scurtă" la unul care are ore comune cu acesta; degeaba reamplasăm orele la profesorii intermediari fără ore comune cu cel curent - este suficient să ştergem amplasările respective, urmând să reamplasăm efectiv numai orele primului din spate (acesta devenind cel "curent") care are ore comune cu profesorul la care am eşuat şi apoi să reluăm avansarea începând de la noul "curent".
Pentru engine, numele profesorilor sunt inutile şi le vom înlocui cu câte un octet a cărui valoare să fie numărul liniei aferente profesorului respectiv în 'schema_1.txt'; astfel, vom putea institui înregistrări de o aceeaşi lungime pentru toţi profesorii.
Vizând deja maniera de lucru în limbaj de asamblare, structurăm o astfel de înregistrare astfel:
— rang - indexul profesorului, în ordinea alfabetică (din schema_1.txt);
— nr_ore - câte ore are, în ziua respectivă (maximum 7);
— iklo - tablou de 16 octeţi, reflectând clasele (cel mult 7) şi plasarea curentă a acestora;
Clasele sunt indicate prin rangul respectiv într-un tablou implicit al acestora (nu neapărat accesibil din 'engine') şi în 'engine.s' vom avea din start o listă în care octetul de rang k indică (într-un format binar convenabil) numărul de ore pe acea zi la clasa de rang k; deasemenea, vom prevedea un tablou _oto în care octetul de rang k să reprezinte şablonul binar curent al orelor deja plasate clasei de rang k (plasarea orei de rang j=0..6 echivalând cu setarea bitului j, în octetul _oto[k]).
— kls - câmp de 32 de biţi, reprezentând prin poziţiile biţilor 1 rangurile claselor la care are ore;
Dacă AND între câmpurile kls a doi profesori setează flagul Z (zero) - atunci ei nu au clase comune.
— sab_opt - şablonul opţiunilor (implicit 0x7F: clasele pot fi plasate în orice subinterval orar 0..6; 0x0F ar însemna: plasează orele într-un subinterval orar din 0..3; ş.a.m.d.);
Ora la clasă este plasată conform opţiunilor ⇔ CL AND sab_opt ≠ 0, unde registrul CL conţine un octet de rang impar din tabloul iklo[] (având un singur bit 1, a cărui poziţie indică a câta oră a fost curent plasată clasa respectivă).
— ocup - şablonul orelor plasate până la momentul curent (OR între octeţii de rang impar din iklo[]);
Vom putea evita apariţia de ferestre în orar, impunând condiţia ca diferenţa dintre rangul maxim şi rangul minim al biţilor 1 din ocup să fie mai mică decât nr_ore (vom putea determina aceste ranguri prin instrucţiunile bsf şi bsr, ale microprocesorului).
Următorul program - în C++11 - constituie fişierul binar 'schema.bin', conţinând câte o înregistrare de 24 de octeţi (cum am descris mai sus) pentru fiecare profesor, înregistrările fiind ordonate după criteriile menţionate mai înainte (neglijând totuşi aici, valorile posibile ale octetului sab_opt):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 | #include <fstream> #include <string> #include <vector> #include <cstdint> // uint8_t (întregi 0..255) #include <algorithm> // sort(), find_if() #include <unordered_map> using namespace std; struct klasa { string nume; uint8_t nr_ore; // pe ziua respectivă (max. 7) uint8_t sab_ore; // şablonul orelor 0x00111110 (a II-a .. a VI-a) uint32_t idx; // un singur bit 1 - pe rangul clasei în lista claselor }; struct bin_prof { // înregistrare cu 24 octeţi (multiplu de 8) uint8_t rang; // rangul în lista iniţială a profesorilor uint8_t nr_ore; // maximum 7 uint8_t sab_opt = 0x7F; // 0x7E "de la a doua oră"; etc. uint8_t ocup = 0; // şablonul orelor puse (OR între părţile "rang_oră") uint8_t iklo[16] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; // [rang_clasă, rang_oră]* uint32_t kls = 0; // OR pe câmpurile 'idx' ale claselor indicate de "rang_clasă" }; struct prof { string nume; // "Vatamanu", sau "Popescu_Alina" string ore; // "CEae" bin_prof schema; // înregistrarea care va fi vizată în `engine.s` }; vector<klasa> qlase; vector<prof> profs; ifstream sch("schema_1.txt"); uint8_t bitCount(uint32_t n) { // câte clase comune au doi profesori uint8_t count = 0; while(n) { if(n & 1) count++; // incrementează dacă bit_0 == 1 n = n >> 1; // deplasează spre dreapta cu o poziţie binară } return count; } template<typename T> ostream& binary_write(ostream& stream, const T& value) { return stream.write((char*)(&value), sizeof(T)); } int main() { unordered_map<char, uint8_t> Ql; unordered_map<char, uint8_t>::iterator Ql_it; prof P; sch >> P.nume; while(!sch.eof()) { sch >> P.ore; size_t n = P.ore.size(); for(size_t i=0; i < n; i++) { char q = P.ore[i]; Ql_it = Ql.find(q); if(Ql_it == Ql.end()) Ql[q] = 1; else Ql[q] ++; } P.schema.nr_ore = (uint8_t) n; P.schema.kls = 0; profs.push_back(P); sch >> P.nume; } klasa K; for(auto& q: Ql) { K.nume = q.first; K.nr_ore = q.second; qlase.push_back(K); } sort(qlase.begin(), qlase.end(), [&](klasa q1, klasa q2) { return q1.nume < q2.nume; }); for(size_t i=0, n=qlase.size(); i < n; i++) qlase[i].idx = 1 << i; for(size_t i=0, n=profs.size(); i < n; i++) { profs[i].schema.rang = (uint8_t)i; size_t j = 0; for(auto& q: profs[i].ore) { auto qit = find_if(begin(qlase), end(qlase), [&](klasa &K) { return K.nume[0] == q; }); size_t id = qit - qlase.begin(); profs[i].schema.iklo[j] = (uint8_t)id; j += 2; profs[i].schema.kls |= (*qit).idx; } profs[i].schema.iklo[j] = 0xFF; // marchează sfârşitul listei claselor } sort(profs.begin(), profs.end(), [&](prof p1, prof p2) { return (p1.schema.nr_ore > p2.schema.nr_ore) && (bitCount(p1.schema.kls & p2.schema.kls) > 1); }); ofstream bf("schema.bin", ios::binary|ios::app); for(size_t i=0, n=profs.size(); i < n; i++) { prof P = profs[i]; binary_write(bf, P.schema); } bf.close(); } |
Compilăm programul şi apoi lansăm executabilul obţinut:
vb@Home:~/_ORAR$ g++ -std=gnu++11 -o oraz orar_zi.cpp vb@Home:~/_ORAR$ ./oraz
Putem vizualiza în hexazecimal fişierul binar obţinut, folosind programul xxd:
vb@Home:~/_ORAR$ xxd -c 24 -g 1 -u schema.bin 0000000: 0F 06 7F 00 00 00 01 00 02 00 05 00 06 00 0A 00 FF 00 00 00 67 04 00 00 0000018: 01 05 7F 00 01 00 03 00 04 00 08 00 0A 00 FF 00 00 00 00 00 1A 05 00 00 0000030: 12 02 7F 00 07 00 0B 00 FF 00 00 00 00 00 00 00 00 00 00 00 80 08 00 00 /* ... */ 00001c8: 13 04 7F 00 03 00 04 00 05 00 06 00 FF 00 00 00 00 00 00 00 78 00 00 00 00001e0: 14 04 7F 00 02 00 04 00 06 00 0A 00 FF 00 00 00 00 00 00 00 54 04 00 00
Fiecare linie reprezintă înregistrarea de 24 de octeţi asociată unui profesor din fişierul 'schema_1.txt'. Prima linie corespunde profesorului cu rang = 0x0F (primul octet din linia de 24 octeţi asociată), adică lui 'Sirbu' (ajuns pe primul loc în urma reordonării efectuate prin liniile 98-101 din programul redat mai sus); acesta are nr_ore = 0x06 (al doilea octet) şi sab_opt = 0x7F.
Al patrulea octet este cel pe care l-am denumit 'ocup', având 0 ca valoare iniţială. Rolul acestuia în cursul funcţionării subrutinei 'engine' este următorul: dacă bitul de rang j=0..6 din ocup este 1, atunci clasa a cărei plasare se încearcă la momentul curent nu poate fi pusă în ora de rang j; altfel - ea poate fi plasată astfel (cu condiţia suplimentară de a se încadra în şablonul opţiunilor), setând în acelaşi timp şi bitul respectiv.
Urmează apoi zona 'iklo'[16]; 'Sirbu' are clasele 'ABCFae' - de ranguri implicite (date de ordinea ASCII a literelor) 0, 1, 2, 5, 6 şi 10 şi aceste ranguri sunt reprezentate respectiv pe octeţii de indecşi pari din tabloul iklo: 00 . 01 . 02 . 05 . 06 . 0A . (marcând prin octetul 0xFF (al 17-lea de pe prima linie redată mai sus) sfârşitul listei claselor); pe fiecare octet '.' urmează să se înregistreze (pe parcursul execuţiei lui 'engine') a câta oră j=0..6 este plasată clasa indicată de octetul precedent acestuia: octetul '.' va avea 1 numai pe bitul de rang j.
În sfârşit, ultimii 4 octeţi din linie reprezintă împreună (ca valoare pe 32 biţi, format "little endian") clasele profesorului respectiv (câmpul denumit 'kls' - vezi linia 93 şi liniile 81-82 din programul redat mai sus); astfel, valoarea 0x0467 (corespunzătoare ultimilor 4 octeţi de pe prima linie) are setaţi biţii de ranguri 0, 1, 2, 5, 6 şi 10 (pentru clasele 'A', 'B', 'C', 'F', 'a' şi 'e').
Câmpurile 'kls' vor asigura o optimizare importantă a mecanismului backtracking folosit de subrutina engine. Presupunând că s-a ajuns la profesorul P1 şi toate încercările de plasare a orei 'A' a acestuia eşuează - se va reveni la profesorul P2 aflat imediat "deasupra"; dacă intersecţia câmpurilor kls de la P1 şi respectiv P2 este nulă (însemnând că ei nu au clase comune), atunci se anulează octetul ocup la P2 şi se trece la linia aflată imediat "deasupra" lui P2 - repetând până ce se ajunge la un profesor P3 care are ore comune cu P1 (şi nu neapărat, la clasa 'A': amplasarea acesteia depinde evident, de a altor clase); se reamplasează orele lui P3 (dacă se poate), reluând amplasarea orelor la profesorii aflaţi dedesubtul lui P3 (cu şansa ca ajungând înnapoi la P1, să putem acum amplasa şi clasa 'A').
Desigur că engine ar putea fi produsă folosind C++ (în loc de a o scrie în limbaj de asamblare, cum intenţionăm noi); dar… de exemplu, programul C++ redat mai sus este unul extrem de voluminos, în comparaţie cu subrutina 'engine' pe care am formulat-o folosind Turbo Assembler (sub DOS/Windows, cu Intel-486) acum 15 ani: aceasta avea nu mai mult de 100 de instrucţiuni (plus câteva directive de asamblare specifice modelului pe 16 biţi), măsurând (ca fişier binar, fără zona de date) numai 168 de octeţi. Cu siguranţă că un program C++ care să facă acelaşi lucru ca această subrutină ar fi mult mai voluminos şi pe de altă parte - încă pare clar că viteza de execuţie ar fi mai bună lucrând direct în limbaj de asamblare.
Având în vedere experienţa tocmai amintită, putem considera că modelul de date pe care l-am definit mai sus (prin înregistrarea de 24 de octeţi 'bin_prof') este bun, dacă ne va permite să reconstruim subrutina "engine" - de data aceasta pentru x86_64, folosind asamblorul GNU Gas, sub Linux - cu cel mult 100 de instrucţiuni în limbaj de asamblare, ajungând la o viteză de execuţie mai bună decât a versiunii pe 16 biţi din 2002 (faţă de care am şi "îmbunătăţit" puţin, modelul de date menţionat).
vezi Cărţile mele (de programare)