Până la un subiect mai serios, care se află deja în scriere, vin cu o problemă, ce se adresează celor care se considera începători. Mi s-a întamplat sa dau această “problemă” unora de nivelul celui menţionat mai devreme, iar răspunsurile să  mă surprindă de fiecare dată.

Aşadar, dându-se un array (vector) cu 2 milioane de elemente, indexate corespunzător de la 0 la 1.999.999 cu valori de tip string, să zicem sub 1 KB ca dimensiune. 

Scrieţi o funcţie care să determine dacă vectorul în cauză este sau nu mulţime. Evident, se cere un timp de execuţie al funcţiei minim

Un vector este considerat mulţime dacă are toate valorile distincte

Trackback

13 comments until now

  1. Ce zici de ideea de a face un concurs cu astfel de mini probleme?

  2. ea e o idee bună, si mă tot gândesc să adun din practică astfel de situaţii

    tu ai o soluţie pentru problema de faţă? :)

  3. In principiu … neverificat ..

    function eMultime($v){
    $tmp = array_unique($v);
    if ((count($v) == count($tmp)){
    return true;
    }
    return false;
    }

    ,toate cele bune

  4. Verificarea vine din partea noastra.
    Intr-adevar, aceasta este si solutia pe care o aveam. Se bazeaza direct pe functiile native din php care sunt optimizate pentru lucrul rapid cu vectorii.

  5. Orice sortare consuma cel putin NlogN timp. In plus, array_unique chiar elimina elementele duplicate – n-am idee cate resurse cunsuma treaba asta dar e clar ca omori musca cu ciocanul.
    Solutia generica optima este un hash table in care se stocheaza cate o referinta la fiecare string. Timpul de acces la hashtable (daca are o dimensiune suficienta, si algoritm bun de coliziuni) tinde spre constant, deci complexitatea deciziei tinde spre O(N) intr-o implementare buna. Daca merita sa implementezi asa ceva cand poti scrie ceva in 3 randuri cu array_unique, e alta poveste :)

  6. Si nu ai vrea tu sa ne dai un exemplu de cum s-ar realiza cu hash?

  7. theheartcollector

    Pentru O(n*log(n)) se poate folosi algoritmul Heapsort: http://en.wikipedia.org/wiki/Heapsort (deşi sunt şi altele). Practic poţi pune o condiţie de oprire unde se face comparaţia pentru cazul în care elementul anterior este egal cu cel curent. În caz că ai nevoie de o implementare, aş putea să îmi sparg puţin creierii cu el pentru că de mult îmi doream să îl înţeleg mai în detaliu…

    Desigur, pentru optimizări mai serioase, s-ar putea să fie necesară şi exploatarea structurii elementelor vectorului. În functie de aceasta, se poate spune care algoritm e mai bun. Totuşi, rămânând la soluţia Heapsort, stringurile de 1k nu sunt un capăt de ţară, dar, decât compararea directă a elementelor, poate o parcurgere iniţială a vectorului şi crearea unui nou vector din md5-urile fiecărui string, iar apoi compararea md5-urilor (care sigur va fi mai rapidă) poate va produce rezultate mai bune. Desigur, după efectuarea unor benchmark-uri se poate stabili exact care variantă e mai bună. Dacă precizia determinării nu trebuie să fie 100% se pot folosi sume de tip CRC în locul MD5-urilor (bine, nici MD5-ul nu garantează unicitatea, dacă vrei să fim cârcotaşi).

  8. Ideea de hash este crearea unei valori suficient de mari care o vei divide la valoarea dintr-un element. Dupa cum s-a precizat mai sus acest lucru va genera erori, insa se pot simula cozile si se pot adauga elementele cu acelasi hash intr-o structura asemanatoare implementata in PHP(folosind array mai mult ca sigur). Dupa problema se va reduce la un timp foarte mic pentru a parcurge acele cozi si sa te asiguri ca nu exista duplicat. Aceasta solutie tinde spre O(n), neglijand coada. Pentru a face algoritmul si mai eficient se pot folosi doua valori pentru crearea hashurilor, micsorand sansa coliziunilor si astfel timpul de executie fiind redus considerabil.

    Un exemplu pentru acest lucru, implementat din pacate doar in C/C++ il puteti gasi la adresa aceasta : http://infoarena.ro/job_detail/331868?action=view-source ,transformarea lui in PHP nefiind dificila deloc.Problema respectiva rezolva cateva “greutati” intampinate in situatiile precizate de tine : adaugarea unui element, eliminarea unuia sau stergerea unuia, precum si asigurarea existentei acestuia in vector.

    Daca doriti explicatii doar spuneti-mi. :D

  9. theheartcollector

    @Avadanei Andrei: Și, totuși, de ce să folosești o listă simplu înlănțuită când poți folosi un arbore binar de căutare?

  10. Pai si vei avea un O(n*log(n)) pentru a verifica unicitatea fiecarui element in caz nefavorabil , pe cand la hashuri va tinde spre O(n) din ce in ce mai mult cu cat metoda de creare a hashului are mai putine coliziuni.

  11. Vrei sa spui un array de aproape 2 Gb, si asta daca folosesti SplFixedArray?

    Eu l-as partitiona in cate 10-20.000 de elemente, distribuind munca in mai multe php-cgi-uri. Bineinteles ca m-as opri imediat daca as detecta ca o partitie nu e o multime. Operatiile urmatoare nu mai au sens.

    Fiecare partitie si-ar confrunta apoi elementele cu toate partitiile urmatoare. Asa obtii toate combinatiile, nu mai mult, nici mai putin. Nu ai verificari duplicate, si nici “probleme” cu memoria.

    Nu am incercat, dar cred ca ar apare probleme si la congestia retelei, deci probabil as trimite cate un checksum mai intai, si verifica doar coliziunile, daca exista. Asa transporti prin retea sa zicem 16 bytes pentru md5.

    Asta numesti tu problema de incepator in PHP? Mai ziceam daca era orice alt limbaj :))

  12. PS: gaseste-mi un programator care stie DOAR PHP si stie SI sa rezolve problema asta calumea, si eu ma inchin la el :D

    PPS: ar trebui sa dai drumu la “edit comment” macar pentru o perioada limitata de timp.

  13. PPS: mai sa te inchini la unele comentarii de mai sus. Stimabililor, se cere unul din raspunsurile TRUE sau FALSE la intrebarea “Este multime?”. Sortari auzi si tu… Un script PHP are in primul rand un max_memory_limit.

Add your comment now