Mişto problema! Soluţia nu e deloc evidentă şi eu nu mai auzisem de problemă, dar până la urmă e foarte simplă (un hashtable ca să trasăm o muchie între valori x şi x+/-1, urmat de componente conexe).
M-a rugat Cosmin să-mi dau cu părerea dacă există soluţie în timp liniar fără hashing. Probabil că nu, fiindcă fără hashing nu știm să facem în O(n) nici element distinctness (ai n întregi; se repetă vreunul?). De fapt asta e problemă majoră în teorie.
Dar hai să profit de ocazie să discut un pic filosofic.
1. Care-i problema cu hashingul? E un algoritm simplu care chiar merge bine. La companiile mari ale momentului, ai de lucrat cu date foarte mari și aproape că nu există cod fără hashing la problemele din industrie. Deci mi se pare aproape obligatoriu să fie întrebări de hashing la interviu.
Ca să ilustrez cu o poveste
Am fost la bere cu niște ingineri de la Google NY și după 3-4 beri s-au apucat să mă întrebe de puzzles cu hashing, zicând că ei vor să facă toate întrebările de interviuri despre hashing, fiindcă citez "e singura chestie de la algoritmi fundamentali care chiar e esențială".
Eu la AT&T n-am păreri așa drastice, fiindcă sunt în research și nu intervievez ingineri
Dar la ce lucrez zilele ăştea chiar e hashing, şi e esenţial în practică
Teoria și cât de rapid merg algoritmiiEu în liceu eram foarte confuz la capitolul "cât de mari sunt întregii", în ce complexitate merge radix sort, etc. Mi-aș fi dorit o explicaţie pe îndelete, și o să încerc acuma să dau o astfel de explicaţie, fiindcă văd că sunt oameni cu întrebări similare în comentarii.
În particular vreau să explic de ce radix sort nu e O(n) şi calcularea unui hash chiar e O(1), nu timp proporţional cu numărul de biţi.
Despre teorie: Dacă nu se pogoară Duhul Sfânt să ne dea o teorie aprobată de sus, teoria o definim noi matematic după cum ni se scoală, și n-are valoare decât în măsura în care scoate rezultate utile despre realitate. Matematic să poate defini orice, inclusiv o teorie fizică fără gravitație, doar că n-o să prezică chestiile care le vedem în experimente (ignorăm pe moment experimente despre cum acţionează gravitația pe Coyote și Roadrunner).
De la teoria algoritmilor vrem să aflăm care algoritmi sunt mai rapizi când îi codăm în C, și aproximativ cam cât de rapid e un algoritm relativ la un altul. Ca să obținem o astfel de teorie, trebe să admitem următorul fapt. Codul ăsta:
int add(int a, int b)
{
return(a+b);
}
... rulează mult mai repede decât să facem adunarea bit cu bit cu un for de la 1 la 32. Nu e greu să definești o teorie simplă care înglobează această proprietate:
Teoria spune că ai date de intrare pe un anume tip int, care nu știi fix câți biți are. Mărimea e o variabilă, nu o constantă, și nu se poate ignora în running time; notaţia încetăţenită pt nr. de biţi per int este "w" (vine de la machine Word). Teoria spune că operațiile din limbaj pe astfel de ints rulează în O(1), nu în O(w).
Mie personal mi se pare o presupunere rezonabilă. Limbajul C e foarte popular când ne doare de eficiență și orice proiectant de procesoare îl ia în seamă. Deci probabil orice procesor comercial are instrucțiuni care fac acele operațiile fundamentale din C, gen adunare, xor, etc. Deci o teorie care măsoară numărul de operații în C aproape măsoară numărul de cicluri de procesor, care e o măsură corectă pt timpul de rulare. Empiric se constată că modul ăsta de a defini complexitatea are corelații utile cu timpul de rulare măsurat pe multe calculatoare reale, cel puțin dacă nu iei complexitatea prea în serios (dacă îmbunătățeși un algoritm de la 7n operații la 5n operații, nu-mi e clar că ai îmbunătățit timpul de rulare;fix de-asta teoreticienii sunt mai mândrii când obțin îmbunătățiri asimptotice, nu doar de constantă).
În acest model, să calculezi un hash e O(1) pt hash functions simple (vezi universal hashing pe wikipedia). Cel mai simplu universal hashing face doar o îmulţire cu o constantă (un număr mare pe int care e musai să fie impar) urmat un shift. Ceva în genul:
#define BITS_PER_HASH 14
int a;
void init_hash(void)
{
srand(time(NULL));
a = rand()*2 +1;
}
int hash(int x)
{
return(((unsigned)a*x) >> (32-BITS_PER_HASH));
}
În această teorie, hash tables sunt algoritmi randomizaţi, iar running time chiar e O(1) pe operaţie (operaţie = insert /delete/lookup); bineînțeles, e vorba de expected running time, fiindcă nu e algoritm deterministic. Sunt multe hash tables și hash functions, care în combinații diverse obţin caracteristici variabile. Spre exemplu, unele combinații au varianță mică în timpul de rulare, etc.
Acuma, care e complexitatea la radix sort? Dacă nu putem ignora w, o să depindă de w. În practică w=32, dar ce contează? În practică totul e o constantă, inclusiv n (să zicem un milion), luăm acele constante, le băgăm în formula de running time, și estimăm cam cât de bine merge algoritmul. Radix sort depinde de cât spațiu ai pt algoritm, fiindcă faci un tabel cu spațiul ăla și indexezi în el ca să distribui valorile. Să notăm spațiul cu S (dacă faci byte cu byte, S=256). Atunci folosești radix S,iar timpul total o să fie fix O(n w/lgS). Acest timp nu e O(n) decât dacă ai spaţiu de counting sort, în care caz problema devine trivială (nu-ţi trebe nici hashing, faci un vector mare). Dar cât e S? Cât e disponibil în implementarea ta; în realitate S e un #define în cod. Fără presupuneri suplimentare, în teorie putem spune sigur că S>= n, fiindcă spaţiu O(n) e optim (trebe măcar să stocăm inputul). Folosind acest raţionament, timpul de rulare la radix sort e maxim O(nw/lg n), care nu e liniar deloc.
Normal că radix sort rămâne cel mai rapid algoritm de sortare în practică şi e mult mai bun ca quicksort, heapsort şi alţi algoritmi. Dar algoritmii ăştia chiar rulează în nlgn operații, şi dacă băgăm în formule valorile reale de n, w şi S, devine clar că radix sort va merge mai bine. Nu apare nicio surpriză aici; radix sort merge în ceva timp mai mare ca O(n) și mai mic ca O(nlg n), care depinde de w (un parametru necunoscut când ne gândim teoretic).
Totuşi, radix sort nu merge în O(n). Aici teoria chiar ne spune ceva interesant. Anume, ne spune că dacă ai de ales între radix sort şi hashing (care dă O(n) curat), ar trebui să alegi hashing. N-am avut timp să codez dar cred că e corect ce spune teoria aici şi la problema asta hashing chiar merge mai repede (cel puțin dacă implementezi bine). Legat de implementare, e clar că hashing e un pic mai neevident de codat și optimizat; la capitolul implementare e clar care soluție câștigă, și teoria algoritmică nu are nimic de spus despre asta.
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena