View source for Psihologia concursurilor de informatică/3 Lucrul cu structuri mari de date

⇦ înapoi la [[Psihologia concursurilor de informatică]]

= Capitolul III: Lucrul cu structuri mari de date =

De multe ori în practică, atât la concursuri cât și atunci când scriem programe care vehiculează un volum mai mare de date, avem nevoie de structuri de date de mari dimensiuni. După cum se știe, însă, compilatorul Borland Pascal nu permite definirea de structuri de date mai mari de 64KB. Ce facem dacă, spre exemplu, avem nevoie de un vector cu sute de mii de elemente sau de o matrice pătratică de 400 x 400 elemente ?

O primă soluție este să schimbăm limbajul de programare folosit și să ne orientăm spre C / C++ sau alte limbaje în care gestiunea datelor voluminoase se face mai comod pentru utilizator. De fapt, programele scrise „la domiciliu” se scriu mai degrabă în C decât în Pascal, deoarece codul generat este mai eficient. Din nefericire, compilatorul de C este destul de lent, cel puțin în comparație cu cel de Pascal și, deși există destui concurenți care lucrează în C la olimpiadă, Pascal-ul mi se pare o alegere mai bună atunci când timpul de implementare contează decisiv.

În aceste condiții, se impune găsirea unor modalități de a ne supune rigorilor limbajului Pascal și de a „înghesui” cumva datele în memorie. Chiar dacă dispunem de memorie extinsă, segmentarea la 64KB a datelor ridică destul de multe probleme. Vom trata pe rând câteva cazuri.


== Vectori de tip boolean de mari dimensiuni ==

În Borland Pascal, variabilele de tip logic (<tt>Boolean</tt>) se reprezintă pe un octet. Se știe însă că variabilele booleene pot lua doar două valori, deci un singur bit ar fi suficient pentru a le reprezenta. Motivul acestei aparente „risipe” de memorie este viteza de rulare a programului. Regiștrii lucrează la nivel de octet, iar operațiile la nivel de bit sunt mai costisitoare din punct de vedere al timpului. În plus, cei șapte biți care ar fi economisiți nu ar putea fi folosiți decât cel mult pentru alte variabile booleene.

În unele cazuri, însă, comprimarea variabilelor logice la un singur bit este necesară, această misiune revenindu-i programatorului. Iată un exemplu de problemă de concurs:

'''ENUNȚ''': Se dau '''''N'''''-1 numere naturale distincte cuprinse între 1 și '''''N'''''. Să se tipărească cel de-al '''''N'''''-lea număr (cel care lipsește).

'''Intrarea''' se face din fișierul <tt>INPUT.TXT</tt>, care conține pe prima linie valoarea lui '''''N''''' ('''''N''''' ≤ 500.000), iar pe următoarele '''''N'''''-1 linii câte un număr cuprins între 1 și '''''N'''''.

'''Ieșirea''': pe ecran se va tipări numărul care lipsește.

'''Exemplu''': Pentru fișierul de intrare:

<pre>
5
3
2
5
1
</pre>

rezultatul tipărit pe ecran va fi 4.

'''Complexitate cerută''': <math>O(N)</math>.

'''Timp de implementare''': 30 minute.

'''REZOLVARE''': O soluție foarte elegantă a problemei este următoarea: se știe că suma primelor '''''N''''' numere naturale este

<math>S_N = \frac{N(N + 1)}{2}</math>

Se calculează suma <math>S'</math> a numerelor din fișierul de intrare, iar numărul lipsă este <math>K = S_N - S'</math>. Această metodă are un dezavantaj care o face inutilizabilă: <math>S_{500000}</math> este aproximativ <math>125 \cdot 10^9</math>, adică un număr mult prea mare chiar și pentru tipul de date <tt>Longint</tt>. Ar trebui să se memoreze numerele foarte mari pe un vector de cifre, apoi ar trebui scrise funcțiile pentru adunarea și scăderea unor asemenea numere (vezi capitolul al II-lea), lucru destul de incomod dacă se ține seama de timpul de implementare.

Pentru a memora tot vectorul în memorie este nevoie de 500.000 x 4 = 2.000.000 octeți, adică foarte mult, iar găsirea valorii care lipsește ar presupune în cel mai bun caz o sortare în <math>O(N \log N)</math>, care ar depăși complexitatea cerută. Ar mai fi soluția de a căuta pe rând fiecare număr în fișier și de a tipări primul număr pe care nu-l găsim. În cazul cel mai rău, însă, algoritmul ar face '''''N''''' parcurgeri ale fișierului de intrare și <math>N^2</math> comparații, deci ar depăși de asemenea complexitatea cerută, ca să nu mai vorbim de timpul de rulare.

Rezolvarea cea mai la îndemână este de a construi un vector de variabile booleene cu '''''N''''' elemente. Se face apoi citirea datelor și se bifează în vector fiecare număr citit. Apoi se parcurge vectorul și se caută singurul element nebifat. Această versiune face o singură parcurgere a fișierului, adică minimul posibil.

Mai rămâne de văzut cum operăm cu un vector de 500.000 de variabile booleene. Dacă fiecare variabilă ar ocupa un octet, necesarul de memorie ar fi de 500.000 de octeți, care sunt greu de găsit în memoria de bază. Dacă însă alocăm câte un bit pentru fiecare element, necesarul de memorie este 500.000 / 8 = 62.500 octeți, adică o sumă rezonabilă care, mai mult, încape într-un singur segment de memorie și poate fi alocată static fără probleme. Cum se poate accesa și modifica valoarea unui bit din acest vector comprimat? Vom numerota vectorul nostru începând de la 0, deci ultimul său element va fi '''''V'''''[62499]. Primii săi opt biți (biții 0...7, adică octetul '''''V'''''[0]) vor fi variabilele logice atașate numerelor 1...8, următorii opt biți (biții 8...15, adică octetul '''''V'''''[1]) vor fi variabilele logice atașate numerelor 9...16, și așa mai departe. Ultimii opt biți (biții 499.992...499.999, adică octetul '''''V'''''[62499]) vor fi variabilele logice atașate numerelor 499.993...500.000. În general, bitul cu numărul '''''X''''' indică dacă numărul '''''X'''''+1 a fost găsit sau nu. Iată cum ar putea arăta vectorul la un moment oarecare al citirii din fișier:

[[File:Psycho-fig09.png]]

Vectorul este reprezentat „pe dos”, ceea ce ar putea să pară ciudat la prima vedere. Am făcut însă acest lucru deoarece, în cadrul octetului, biții sunt numerotați în ordine crescătoare de la dreapta spre stânga și am ținut să păstrăm aceeași ordine și pentru numerotarea octeților în vector.

Primul octet semnifică că numărul 1 a fost întâlnit, numerele 2, 3 și 4 nu au fost întâlnite încă, numărul 5 a fost găsit etc. Trebuie acum să vedem cum se face efectiv modificarea vectorului. Inițial toți biții au valoarea 0. Se citește din fișier un număr '''''X''''' și trebuie ca al '''''X'''''-1-lea bit să fie setat pe 1.

Mai întâi trebuie aflat în ce octet se află al '''''X'''''-1-lea bit. Se observă imediat că în octetul <tt>Oct = (X-1) div 8</tt>. De exemplu, biții 0..7 se află în octetul 0, biții 7..15 în octetul 1 ș.a.m.d. Mai e nevoie să știm al câtulea bit este bitul nostru în cadrul octetului. El va fi pe poziția <tt>B = (X-1) mod 8</tt> (numărătoarea începe de la 0). În sfârșit, trebuie să setăm bitul respectiv la valoarea 1. În problema de mai sus, singura operație necesară este modificarea unui bit din 0 în 1. Vom trata însă cazul cel mai general, când se cere setarea unui bit la o anumită valoare (0 sau 1) fără a se ști ce valoare a avut el înainte.

Să pornim de la un exemplu particular urmând ca apoi să generalizăm rezultatul. Se cere să se seteze bitul 2 al octetului '''''A''''' = 00110010 la valoarea 1. Pentru aceasta, putem folosi o mască logică în care numai bitul 2 este setat pe 1, iar ceilalți sunt 0, adică masca '''''M''''' = 00000100. Între octeții '''''A''''' și '''''M''''' se poate face acum un SAU logic:

<pre>
A  00110010 SAU
M  00000100
   --------
B  00110110
</pre>

Se observă că '''''B''''' = '''''A''''' cu excepția bitului 2, care a luat valoarea 1. Acest fapt este ușor de explicat: 0 este element neutru în raport cu operația SAU (0 SAU '''''X''''' = '''''X''''', ∀'''''X''''') și deci biții de valoare 0 din '''''M''''' nu modifică biții corespunzători din '''''A'''''. În schimb, 1 SAU '''''X''''' = 1, ∀X, deci bitul 2 din '''''B''''' va lua valoarea 1 indiferent de valoarea bitului corespunzător din '''''A'''''.

Revenind la cazul nostru, octetul <tt>Oct</tt> are o valoare oarecare cuprinsă între 0 și 255, iar noi trebuie să-i setăm bitul '''''B''''' (0 ≤ '''''B''''' ≤ 7) la valoarea 1. Masca '''''M''''' va avea toți biții de valoare 0, cu excepția bitului '''''B''''' care va avea valoarea 1. Aceasta înseamnă ca masca '''''M''''' are valoarea <math>M = 2^B = 1 \text{ shl } B</math>. Operația pe care o avem de făcut este:

<syntaxhighlight>
V[Oct] := V[Oct] or (1 shl B)
</syntaxhighlight>

Să luăm acum un exemplu pentru a vedea cum se setează un bit oarecare la valoarea 0. Fie '''''A''''' = 01101101. Se cere să setăm bitul 5 la valoarea 0. De data aceasta, vom folosi o mască în care toți biții sunt 1, mai puțin al 5-lea și vom aplica operația ȘI logic:

<pre>
A 01101101 SI
M 11011111
  --------
B 01001101
</pre>

Se observă că '''''B''''' = '''''A''''' cu excepția bitului 5, care a trecut de la valoarea 1 la valoarea 0. Aceasta deoarece 1 este element neutru în raport cu operația ȘI (1 ȘI '''''X''''' = '''''X''''', ∀'''''X''''') și deci biții de valoare 1 din '''''M''''' nu modifică biții corespunzători din '''''A'''''. În schimb, 0 ȘI '''''X''''' = 0, ∀'''''X''''', deci bitul 5 din '''''B''''' va lua valoarea 0 indiferent de valoarea bitului corespunzător din '''''A'''''.

Să ne întoarcem la problema noastră: trebuie setat bitul '''''B''''' din octetul <tt>Oct</tt> la valoarea 0. Pentru a construi masca '''''M''''' remarcăm că un octet cu toți biții de valoare 1 este egal cu 255. Din 255 trebuie să scădem (<tt>1 shl B</tt>), deci operația necesară este:

<syntaxhighlight>
V[Oct] := V[Oct] and (255 - (1 shl Bit))
</syntaxhighlight>

Mai avem nevoie și să testăm valoarea unui bit. Să luăm de exemplu '''''A'''''=00101111 și să aflăm ce valoare au biții 3 și 7. Folosim măștile <math>M_3 = 00001000</math> și <math>M_7 = 10000000</math>, aplicând de fiecare dată operația ȘI logic.

<pre>
A    00101111 SI        A  00101111 SI
M3   00001000          M7  10000000
     --------              --------
     00001000              00000000
</pre>

În ce caz rezultatul poate fi diferit de 0? Șapte dintre biții măștii sunt 0, deci biții corespunzători din B vor fi oricum 0. Cel de-al optulea depinde de bitul respectiv din '''''A''''': dacă acesta este 0, rezultatul va fi 0, dacă este 1, rezultatul va fi diferit de 0. Revenind la problemă, testul care trebuie făcut este:

<syntaxhighlight>
V[Oct] and (1 shl Bit) <>  0
</syntaxhighlight>

Cel mai bine este să se creeze o „interfață” care să aibă implementate cele două funcții (setarea și testarea unui bit). După aceasta nu se va mai accesa direct vectorul, ci numai prin intermediul acestor funcții. În felul acesta, dacă vor apărea erori de funcționare din cauza lucrului cu vectorul, vom ști unde să le căutăm.

Inițializarea vectorului se poate face prin două metode: una, mai elegantă, constă în folosirea funcției de atribuire pentru fiecare element al său în parte. A doua, mai rapidă, constă în suprascrierea cu valoarea 0 a tuturor celor 62.500 de elemente ale vectorului '''''V''''', printr-un acces direct al memoriei (procedura <tt>FillChar</tt> din Pascal).

În program, pentru creșterea vitezei, s-au făcut următoarele modificări: 

* <tt>(X-1) div 8</tt> înseamnă <tt>(X-1) div 2^3</tt>, adică <tt>(X-1) shr 3</tt>;
* <tt>(X-1) mod 8</tt> reprezintă ultimii 3 biți din reprezentarea binară a lui ('''''X'''''-1), adică <tt>(X-1) and 7</tt> (deoarece 7 în binar este 00000111).
* <tt>255-(1 shl A) = 255 xor (1 shl A)</tt>. Cu alte cuvinte, schimbarea unui singur bit din 1 în 0 se poate face atât prin scădere, cât și printr-un SAU exclusiv, a doua variantă fiind mai rapidă.

<syntaxhighlight>
program VectorDeBiti;
type Vector=array[0..62499] of Byte;
var V:Vector;
    N,X,i:LongInt;

function GetValue(X:LongInt):Boolean;
begin
  GetValue:=V[Pred(X) shr 3] and (1 shl (Pred(X) and 7))<>0;
end;

procedure SetValue(X:LongInt;B:Boolean);
begin
  if B
    then V[Pred(X) shr 3]:=V[Pred(X) shr 3] or
                           (1 shl (Pred(X) and 7))
    else V[Pred(X) shr 3]:=V[Pred(X) shr 3] and
                           ($FF xor (1 shl (Pred(X) and 7)));
end;

begin
  FillChar(V,SizeOf(V),0);
  Assign(Input,'input.txt');Reset(Input);
  ReadLn(N);
  for i:=1 to N-1 do
    begin
      ReadLn(X);
      SetValue(X,True);
    end;
  Close(Input);
  i:=0;
  repeat Inc(i) until not GetValue(i);
  WriteLn(i);
end.
</syntaxhighlight>


== Vectori de dimensiuni mari cu elemente de valori mici ==

Metoda descrisă la punctul anterior se poate aplica și în alte două cazuri particulare. Dacă elementele vectorului de care avem nevoie pot lua nu doar două valori, ci patru valori (0, 1, 2, 3), atunci ele se pot reprezenta pe doi biți. În concluzie, într-un octet putem „înghesui” patru elemente ale vectorului, iar pe un segment de memorie se pot reprezenta peste 250.000 elemente. În cazul în care elementele vectorului iau valori între 0 și 15, ele se reprezintă pe 4 biți (în limba engeză, grupul de 4 biți poartă un nume special - nibble), adică două elemente pe un octet, iar pe un segment încap peste 125.000 elemente. Vom trata numai al doilea caz, lăsându-l pe primul ca temă.

Vom folosi de asemenea un vector '''''V''''' cu 62.500 elemente numerotate cu începere de la 0. Octetul 0 va fi folosit pentru a memora primele două elemente din vectorul dat, octetul 1 va memora al treilea și al patrulea element etc. Octetul 62.499 va memora elementele 124.999 și 125.000. Să vedem de exemplu cum se memorează vectorul (5, 12, 4, 11, 0, 15).

[[File:Psycho-fig10.png]]

Avem nevoie de aceleași operații ca și în cazul precedent:

* Setarea valorii unui element, indiferent de valoarea sa precedentă;
* Aflarea valorii unui element;
* Inițializarea vectorului.

Pentru a seta valoarea elementului cu numărul '''''X''''' (1 ≤ X ≤ 125.000), trebuie alterat nibble-ul cu numărul X-1. În ce octet se află acest nibble? În octetul <tt>Oct= (X-1) div 2</tt>. Ce poziție ocupă nibble-ul în cadrul octetului? Poziția <tt>Nib = (X-1) mod 2</tt>. Să luăm acum un caz particular și să vedem cum se face modificarea propriu-zisă, urmând ca apoi să generalizăm.

Se dă octetul '''''A'''''=01110010 și se cere ca nibble-ul 1 (cel din stânga) să fie setat la valoarea 13 (în binar 1101). Se observă că nibble-ul stâng are deja o altă valoare, deci în primul rând trebuie „curățată zona”, respectiv nibble-ul trebuie adus la valoarea 0. Cum? Probabil ați învățat deja, cu o mască logică. Cum toți patru biții trebuie puși pe 0, iar ceilalți patru trebuie să rămână nealterați, folosim masca <math>M_1=00001111</math> și aplicăm operatorul ȘI logic:

<pre>
A   01110010 SI
M1  00001111
    --------
A’  00000010.
</pre>

Așadar nibble-ul 0 a rămas nemodificat, iar nibble-ul 1 are valoarea 0. Acum putem aduna pur și simplu nibble-ul de valoare 13. Pentru aceasta, luăm numărul 13 (în binar 1101) și îl deplasăm spre stânga cu 4 poziții, pentru a-l alinia în dreptul nibble-ului 1, după care efectuăm un SAU logic (se poate face și adunarea, dar ea este mai lentă din punct de vedere al calculatorului).

<pre>
A’  00000010 SAU
M2  11010000
    --------
B   11010010
</pre>

Să presupunem acum că voiam să setăm nibble-ul drept la aceeași valoare, 13. Ce aveam de făcut? „Curățam” jumătatea dreaptă a octetului printr-un ȘI logic cu masca <math>M_1=11110000</math>, apoi făceam un SAU logic cu nibble-ul 13:

<pre>
A   01110010 SI
M1  11110000
    --------
A’  01110000 SAU
M2  00001101
    --------
B   01111101
</pre>

Metoda generală este deci următoarea. Se construiește masca <math>M_1</math> cu care se setează pe 0 nibble-ul dorit. Masca se obține scăzând din octetul „plin” 11111111 (zecimal 255, hexazecimal $FF) valoarea 1111 (zecimal 15, hexazecimal $0F), deplasată la stânga cu 4 poziții dacă Nib=1. O primă formă a instrucțiunii de construire a măștii ar fi:

<syntaxhighlight>
if Nib=1 then M1:=$FF - ($0F shl 4)
         else M1:=$FF - $0F
</syntaxhighlight>

Pentru a evita instrucțiunea „if”, destul de mare consumatoare de timp, se poate calcula direct

<syntaxhighlight>
M1:=$FF xor ($0F shl (Nib shl 2))
</syntaxhighlight>

deoarece <tt>Nib shl 2</tt> este 0 dacă <tt>Nib=0</tt> și 4 dacă <tt>Nib=1</tt>. S-a înlocuit scăderea cu operația SAU exclusiv, pentru motivul arătat la punctul 1.

Apoi se adună, după aceeași metodă, valoarea K dorită (0 ≤ K ≤ 15):

<syntaxhighlight>
V[Oct] = (V[Oct] and ($FF xor ($0F shl (Nib shl 2))))
         or (K shl (Nib shl 2))
</syntaxhighlight>

Să vedem cum se află valoarea unui nibble. Să presupunem că se dă octetul '''''A'''''=01111010 și se cere să se afle nibble-ul 1 (cel din stânga). Pentru aceasta, se face un AND logic cu masca '''''M'''''=11110000 (deoarece ultimii patru biți nu interesează), iar rezultatul se deplasează spre dreapta cu 4 biți:

<pre>
A   01111010 SI
M   11110000
    --------
A’  01110000 >>>>
    --------
B   00000111
</pre>

Deci nibble-ul stâng are valoarea 7. Revenind la cazul nostru, valoarea '''''K''''' a nibble-ului Nib din octetul Oct este:

<syntaxhighlight>
K = (V[Oct] and ($0F shl (Nib shl 2))) shr (Nib shl 2)
</syntaxhighlight>

Se recomandă și în acest caz scrierea unor funcții și folosirea vectorului '''''V''''' numai prin intermediul acestor funcții. În cazul inițializării vectorului, dacă toate elementele trebuie puse la valoarea 0, se poate folosi totuși procedura <tt>FillChar</tt>, care e mult mai rapidă decât apelarea funcțiilor noastre pentru fiecare element în parte.

Prezentăm mai jos numai un program demonstrativ despre modul de lucru cu aceste funcții:

<syntaxhighlight>
program Nibbles;
type Vector=array[0..62499] of Byte;
var V:Vector;

function GetValue(X:LongInt):Word;
var Oct,Nib:Word;
begin
  Oct:=Pred(X) shr 1;
  Nib:=Pred(X) and 1;
  GetValue:=(V[Oct] and ($0F shl (Nib shl 2)))
            shr (Nib shl 2);
end;

procedure SetValue(X:LongInt;K:Word);
var Oct,Nib:Word;
begin
  Oct:=Pred(X) shr 1;
  Nib:=Pred(X) and 1;
  V[Oct]:=(V[Oct] and ($FF xor ($0F shl (Nib shl 2))))
          or (K shl (Nib shl 2));
end;

begin
  FillChar(V,SizeOf(V),0);
  SetValue(12345,12);
  SetValue(12346,13); { Doi nibble de pe acelasi octet }
  WriteLn(GetValue(12345),' ',GetValue(12346));
end.
</syntaxhighlight>

== Alocarea dinamică a matricelor de mari dimensiuni ==

Să presupunem că avem nevoie de o matrice cu 400 linii și 400 coloane cu elemente de tip Integer. Necesarul de memorie este deci de 400 x 400 x 2 = 320.000 octeți, adică mult mai mult decât un segment. O cale foarte comodă de a rezolva această dificultate este de a declara matricea drept un vector de pointeri la vectori, ca în figura de mai jos:

[[File:Psycho-fig11.png]]

Dimensiunea vectorului de pointeri este de 400 x 4 = 1600 octeți (un pointer se reprezintă pe 4 octeți). Dimensiunea unei linii din matrice este de 400 x 2 = 800 octeți. Așadar, fiecare structură de date încape pe un segment. Vectorii sunt alocați dinamic la intrarea în program.

Metoda este comod de implementat (practic singura diferență este că elementul de la coordonatele ('''''i''''','''''j''''') din matrice nu va mai fi adresat cu <tt>A[i,j]</tt>, ci cu <tt>A[i]^[j]</tt>) și nu este consumatoare de timp (adresarea unui element mai presupune, pe lângă cele două incrementări datorate indicilor, și o indirectare datorată pointerului).

Iată un exemplu demonstrativ de folosire a acestei structuri de date, care calculează suma numerelor naturale de la 1 la 100.

<syntaxhighlight>
program VPV;
type Vector=array[1..400] of Integer;
     Matrix=array[1..400] of ^Vector;
var A:Matrix;
    i:Integer;

begin
  for i:=1 to 400 do New(A[i]);
  A[1]^[1]:=1;
  for i:=2 to 100 do A[i]^[i]:=A[i-1]^[i-1]+i;
  WriteLn(A[100]^[100]);
end.
</syntaxhighlight>

== Fragmentarea matricelor de mari dimensiuni ==

O altă soluție pentru a reprezenta în memorie structuri de date care depășesc un segment este de a le fragmenta în bucăți mai mici, fiecare din acestea nedepășind un segment. Pentru a accesa un element oarecare al structurii, depistăm întâi fragmentul din care el face parte, apoi îl localizăm în cadrul fragmentului.

Să considerăm același exemplu al unei matrice '''''A''''' de dimensiuni 400 x 400 cu elemente de tip Integer. Spațiul necesar este de 320.000 octeți, adică mai mult de 4 segmente de câte 64KB și mai puțin de 5. Să spunem că am dori să fragmentăm această matrice în 5 matrice <tt>B[0], B[1], B[2], B[3], B[4]</tt>, fiecare având câte 400 linii și 80 de coloane (vom numerota liniile de la 0 la 399 și coloanele de la 0 la 79).  Cele 5 matrice se vor aloca dinamic, fiecare încăpând pe un segment (așadar vectorul '''''B''''' este un vector de pointeri la matrice).

Unde se va regăsi elementul <tt>A[i,j]</tt> ? Primele 80 de coloane din matricea '''''A''''' se vor afla în matricea <tt>B[0]</tt>, următoarele 80 de coloane din '''''A''''' se vor afla în matricea <tt>B[1]</tt> ș.a.m.d. Coloana '''''j''''' a matricei '''''A''''' se va afla prin urmare în matricea <tt>B[j div 80]</tt>. Linia '''''i''''' va fi aceeași, iar coloana pe care se află elementul <tt>A[i,j]</tt> în cadrul matricei <tt>B[j div 80]</tt> este <tt>j mod 80</tt>.

Acum se vede de ce, pentru a calcula mai rapid câtul și restul împărțirilor, este bine ca numărul de coloane la care se face fragmentarea să fie o putere a lui 2, astfel încât operațiile „div” și „mod” să se poată înlocui printr-un „<tt>shr</tt>” și un „<tt>and</tt>”. Pentru problema noastră, cea mai rezonabilă cifră este 64, ceea ce înseamnă că avem nevoie de <math>\lceil 400/64 \rceil = 7</math> fragmente (prin rotunjire în sus a rezultatului). De fapt, prin alocarea a 7 segmente (numerotate de la 0 la 6) se creează 7 x 64 = 448 de coloane, cu 48 mai mult decât era necesar. Se pierde deci o cantitate de memorie de 48 x 400 x 2 = 38.400 octeți. În cazul în care această memorie nu este vitală, se poate face „risipă”, câștigându-se în schimb viteză.

Iată cum ar arăta matricea fragmentată la 64 de coloane:

[[File:Psycho-fig12.png]]

Prezentăm mai jos un scurt exemplu de fragmentare, care face același lucru ca și programul de la punctul anterior. S-au scris, ca și în cazurile precedente, două funcții, una pentru modificarea unui element și una pentru aflarea valorii lui. De asemenea, „<tt>X div 64</tt>” a fost înlocuit peste tot cu „<tt>X shr 6</tt>”, iar „<tt>X mod 64</tt>” cu „<tt>X and 63</tt>”.

<syntaxhighlight>
program Fragment;
type FragType=array[0..399,0..63] of Integer;
     Matrix=array[0..6] of ^FragType;
var B:Matrix;
    i:Integer;

function GetValue(i,j:Integer):Integer;
begin
  GetValue:=B[j shr 6]^[i,j and 63];
end;

procedure SetValue(i,j,Value:Integer);
begin
  B[j shr 6]^[i,j and 63]:=Value;
end;

begin
  for i:=0 to 6 do New(B[i]);
  SetValue(1,1,1);
  for i:=2 to 100 do SetValue(i,i,GetValue(i-1,i-1)+i);
  WriteLn(GetValue(100,100));
end.
</syntaxhighlight>