Note de curs, clasele 9-10, 27 februarie 2014

From Algopedia
Jump to: navigation, search

Sortări

Cercetătorii britanici au descoperit că apelarea obsesivă a algoritmului std::sort dăunează grav sănătății.

Sortarea prin numărare

Sortările bazate pe comparații între două elemente au nevoie de cel puțin O(n log n) operații elementare. (Idee de demonstrație, dacă timpul permite).

În cazul în care vectorul conține doar elemente întregi între 0 și k, putem sorta în timp O(n + k) folosind memorie suplimentară O(k). Construim un vector suplimentar C unde C[i] reține numărul de elemente egale cu i din vector. Apoi parcurgem vector C de la 0 la k și afișăm elementul i de C[i] ori.

Exemplu. Pseudocod.

Radix sort

Să considerăm că toate numerele au maxim 3 cifre. Atunci putem proceda astfel:

  • Definim un vector de 10 liste înlănțuite, L0, L1, ... L9.
  • Inițial toate listele sunt goale.
  • Parcurgem vectorul și distribuim numerele în cele 10 liste potrivit cu ultima cifră.
  • Colectăm cele 10 liste, în ordine, suprascriind vectorul.
  • Parcurgem vectorul și distribuim numerele în cele 10 liste potrivit cu cifra din mijloc.
  • Colectăm cele 10 liste, în ordine, suprascriind vectorul.
  • Parcurgem vectorul și distribuim numerele în cele 10 liste potrivit cu prima cifră.
  • Colectăm cele 10 liste, în ordine, suprascriind vectorul.

Exemplu. Pseudocod.

Care este necesarul de memorie? Avem nevoie de

  • vectorul cu capetele de listă
  • un element din listă (întreg + pointer) pentru fiecare element din vector.

Așadar, avem nevoie de triplul memoriei.

În practică, în loc de cifre zecimale operăm cu puteri ale lui doi, cum ar fi 28 sau 216. Acestea au avantajul că putem extrage a k-a cifră folosind operații pe biți, nu modulo.

Această variantă de radix sort are două mari dezavantaje:

  • Triplează memoria
  • Din această cauză, memoria nu mai este cache-uită bină, ceea ce încetinește mult algoritmul. El este mai lent decât std::sort.

Avem așadar nevoie de o variantă de radix sort in place (fără vector suplimentar).

Radix sort fără vector suplimentar

Pornim cu cifra cea mai semnificativă. Facem o trecere prin vector și numărăm de câte ori apare fiecare cifră. Apoi precalculăm pozițiile din vector pe care le vor ocupa numerele cu prima cifră 0, 1, ...

De exemplu, pentru vectorul { 19, 83, 47, 18, 55, 13, 23, 58 } vom constata că prima cifră 1 apare de 3 ori, 5 de două ori, iar 2, 4 și 8 câte o dată. Pentru fiecare din cifrele 0, ..., 9 calculăm prima și ultima poziție din vector pe care o vor ocupa numerele începând cu acea cifră. Reținem aceste intervale închise la stânga, deschise la dreapta.

prima  = { 0, 0, 3, 4, 4, 5, 7, 7, 7, 8 }
ultima = { 0, 3, 4, 4, 5, 7, 7, 7, 8, 8 }

Într-adevăr, examinând vectorul sortat { 13, 18, 19, 23, 47, 55, 58, 83 } putem verifica corectitudinea vectorilor prima și ultima.

Dorim acum să mutăm fiecare număr în intervalul lui corect, conform primei cifre. Deoarece nu dorim să folosim vectori suplimentari, vom face interschimbări astfel:

  • pentru fiecare cifră de la 0 la 9, menținem un pointer la primul element încă neexaminat
    • inițial, acești pointeri coincid exact cu vectorul prima
    • în practică, vom refolosi chiar acest vector, incrementând diverse valori prin el pe măsură ce examinăm elemente
    • la final, vectorul prima va coincide cu ultima
  • parcurgem toate cifrele de la 0 la 9
  • pentru fiecare cifră c parcurgem intervalul din vector de la prima[c] la ultima[c]
  • pentru fiecare număr întâlnit care nu începe cu cifra c, îi calculăm bucketul corect și îl interschimbăm cu următorul element din acel bucket
    • la nevoie, repetăm această operație până când pe poziția curentă ajunge un număr care începe cu cifra c.

Observăm că acest algoritm nu este stabil. Dacă l-am aplica începând cu ultima cifră, ca pe radix sort-ul clasic, o iterație ar putea inversa elemente sortate de iterațiile anterioare. De aceea, vom începe cu cifra cea mai semnificativă. După prima iterație, vom sorta recursiv cele 10 intervale obținute, ținând cont de a doua cifră (acest algoritm are deci elemente comune și cu quicksort).

O altă observație importantă este că, pentru porțiuni mici din vector, nu mai rentează să reapelăm recursiv radix sort. Acesta iterează mereu prin vectorul de cifre, care în practică are 256 de elemente. Pentru vectori mai mici de 40-60-100 de elemente, recurgem la sortarea prin selecție.

Măsurători

Am comparat std::sort cu radix sort clasic și cu radix sort fără vector suplimentar. Am variat următorii parametri:

  • lui N i-am dat valorile 1.000.000 și 10.000.000
  • vectorii au fost generați prin trei metode: aleator, sortați crescător, sortați descrescător
N = 1.000.000 std::sort radix1 radix2
vector aleator 122 ms 215 ms 67 ms
vector crescător 23 ms 218 ms 51 ms
vector descrescător 168 ms 215 ms 51 ms
N = 10.000.000 std::sort radix1 radix2
vector aleator 1.395 ms 2.810 ms 457 ms
vector crescător 310 ms 2.820 ms 268 ms
vector descrescător 1.979 ms 2.810 ms 333 ms

Concluzia? Radix sort are limitări. Nu se pretează la numere negative, la numere reale etc. Dar, odată stabilite condițiile, el merge mult mai rapid decât std::sort. Cazul de interes practic pentru olimpiadă este N = 1.000.000, unde radix sort economisește zeci de milisecunde.

Surse

Operații pe biți

Reprezentarea a opt elemente booleene pe un octet

Dacă avem de stocat un vector cu un milion de elemente booleene, atunci fiecare element necesită, la limită, un singur bit. Deci putem folosi doar 125.000 de octeți în loc de 1 MB.

Pentru a ne ușura operațiile pe biți, vom folosi reprezentarea:

octetul 0 octetul 1 octetul 2
bitul 0 bitul 1 bitul 2 bitul 3 bitul 4 bitul 5 bitul 6 bitul 7 bitul 8 bitul 9 bitul 10 bitul 11 bitul 12 bitul 13 bitul 14 bitul 15 bitul 16 bitul 17 bitul 18 bitul 19 bitul 20 bitul 21 bitul 22 bitul 23

Atunci bitul al k-lea va fi stocat pe octetul k / 8, pe poziția k % 8. Atenție! Poziția 0 este bitul cel mai puțin semnificativ, iar poziția 7 este bitul cel mai semnificativ. În imaginea de mai sus, biții sunt reprezentați invers decât în scrierea curentă.

În loc de v[i] = x (pentru atribuire) și v[i] (pentru scriere) vom folosi două funcții:

void set(int i, int x) {
  char mask = ~(1 << (i & 7));
  b[i >> 3] = (b[i >> 3] & mask) ^ (x << (i & 7));
}

int get(int i) {
  return (b[i >> 3] >> (i & 7)) & 1;
}

Funcția set() șterge întâi bitul deja existent la poziția i, folosind masca 11...101...11, care are 0 pe poziția dorită și 1 în rest. Apoi, atribuie noua valoare. Funcția get() izolează bitul dorit.

Aceste funcții merg cam cu 20% mai lent decât implementarea normală, cu vectori, un preț modest pentru o economie de memorie de 87%.

Stocarea pe 64 de biți

Putem implementa aceleași operații pe 64 de biți: în loc să împachetăm opt variabile booleene pe un octet (tipul char) putem împacheta 64 de variabile booleene pe tipul unsigned long long. Cu această reprezentare, impactul asupra vitezei este sub 10%. Atenție, însă, la detaliile de implementare:

  • Dacă dimensionați vectorul doar ca unsigned long long b[N / 64];, riscați să pierdeți un ultim element dacă N nu este multiplu de 64. Acest risc există, desigur, și pentru lucrul pe char, dar poate trece neobservat deoarece, în general datele de intrare sunt multiplu de 8.
  • Unele valori trebuie convertite explicit la unsigned long long.

Codul rezultat este:

typedef unsigned long long u64;

void set(int i, int x) {
  u64 mask = ~(1ull << (i & 63));
  b[i >> 6] = (b[i >> 6] & mask) ^ ((u64)x << (i & 63));
}

int get(int i) {
  return (b[i >> 6] >> (i & 63)) & 1;
}

Stocarea valorilor pe doi sau patru biți

Ce alte valori interesante mai pot fi compactate într-un octet?

  • numerele pe 2 biți, cu valori între 0 și 3 (de exemplu: codificarea direcțiilor NSEV într-o matrice)
  • numerele pe 4 biți, cu valori între 0 și 15 (de exemplu: codificarea a două cifre zecimale într-un singur octet; valorile hexa A-F rămân neutilizate)

Valorile acestea pot fi compactate câte 4 (respectiv 2) pe un octet sau câte 32 (respectiv 16) pe un unsigned long long. Implementarea vă rămâne vouă ca temă.