infoarena

Discutati aici pe marginea post-ului Subset maxim (http://infoarena.ro/blog/interviu-subset-consecutiv-maxim).

Parcurgem sirul si pentru fiecare element x, verificam daca x - 1 si/sau x + 1 au fost intalnite anterior(cu un hash). Daca ambele au fost, atunci inseram una dintre multimi in cealalta(multimea lui X= {multimea maximala de numere consecutive intalnite inaintea lui X}  U  {X} ), inclusiv pe x(cu multimi disjuncte), daca doar una din valori a fost intalnita anterior il inseram pe x in acea multime.

asta e N log* N. Cred ca se asteapta o solutie mai buna.

Later Edit:
Se poate totusi implementa in O(N) solutia cu multimi disjuncte datorita particularitatii problemei(mai exact faptul ca niciodata nu vei uni doua multimi decat dupa elemente de la capetele lor, deci informatii legate de multimea unui element nu trebuie updatate decat in capete)

Adi are dreptate, nu o solutie in complexitate O(Nlog*N) se asteapta.

Legat de modul de implementare in O(N), ai putea detalia pentru ca nu inteleg ce vrei sa spui?

o idee ..cred cam nepractica: ptr fiecare element din multimea data , un v[nr.resp] va lua valorile 1,2 sau 3.... 1 daca nr din multime e pozitiv si v[nr.resp] este 0, 2 daca elementul din multime este negativ si v[nr.resp] este 0, 3 daca v[nr.resp]nu era 0 ->adica daca exista in multime si x si -x..... apoi... ar mai ramane problema numararii celui mai lung suubsir de ne-zerouri la modul urmator...daca v[0] este 0 nu mai e problema unei submultimi care sa contina atat nr negativa, cat si pozitive.. ci trebui determinat cel mai lung subsir de 1si 3..sau de 2si3..daca v[0] este 1, atunci nu prea mai stiu:))

Exista o problema cu solutia oferita de tine. Abordarea ta e ok daca numerele (in modul) sunt relativ mici, insa acest lucru nu e specificat in enunt. Daca facem presupunerea standard ca numerele vor fi reprezentate pe 32 biti (int), atunci nu vei putea declara un vector v de ~2*10⁹ elemente. Problema asta poate fi depasita folosind hash-uri (http://infoarena.ro/problema/hashuri), dupa cum a sugerat si Bogdan mai sus.

merge doar cu hash, n-ai nevoie de structuri de multimi disjuncte.

Just my 2 cents:

Daca este permis sa folosim O(n) memorie, unde n este marimea sirului (banuiesc ca se poate daca se tot discuta solutia cu has-uri). Putem folosi un radix sort mai tunat (dupa cum se discuta http://www.cubic.org/docs/radix.htm (http://www.cubic.org/docs/radix.htm)) pentru a sorta sirul. O data sortat gasirea celui mai lung subsir crescator este banal. Dezavantajul major al acestei solutii este ca din punct de vedere teoretic complexitatea este O(n*number_of_radixes). Insa cum putem fixa numarul de bytes din care este alcatuit numarul la o valoare constanta (4 pentru numere pe 32 biti sau 8 pentru numere pe 64 biti) complexitatea practica este liniara cu o constanta relativ mica. Nu e cea mai eleganta solutie dar macar e putin inovatoare :).

Cateva note:

1) Daca e sa analizam compelxitatea teoretica, solutia cu hash-uri nu e neaparat mai buna decat cea cu radix sort-ul. Asta pentru ca oricum pentru a calcula acel hash (oricare ar fi el), trebuie parcursi toti bitii numarului, deci complexitatea teoretica cam tot aia e.

2) Pentru valori in virgula mobila este mai dificil (desi nu imposibil, dupa cum se vede aici http://www.codercorner.com/RadixSortRevisited.htm (http://www.codercorner.com/RadixSortRevisited.htm)). Problema cu valorile in virgula mobila este ca depinde de implementarea specifica (care poate diferi de la un limbaj la altul etc).

Una peste alta, solutia cu has-urile in practica ar necesita mai putine parcurgeri decat solutia cu radix sort si pare si mai versatila. Dar I felt like throwing my 2 cents into the ring. Va rog sa ma corectati daca am gresit in diverse locuri.

Claudiu



2) Se poate argumenta ca solutia cu radix sort nu va merge pe numere signed sau pe valori in floating point. Nu neaparat. Pentru numere negative merge, doar ca algoritmul le va considera valori unsigned si deci foarte mari. Acest neajuns se poate compensa cu o parcurgere in plus.

Folosim solutia  lui Bogdan numai ca in loc de multimi disjucte folosim o padure de arbori direct. Nodurile sunt numerotate folosind indicii vectorului.
Practic cand ajungem la un numar cautam in Hash indicele numarului v[ i ]-1 si v[ i ]+1
si daca  le gasim(pe oricare dintre ele, nu neaparat pe amandoua) trasam o muchie de la  i la indicele/indicii valorilor gasite.
La final putem face un DFS in care determinam numarul de elemente din fiecare arbore(lant) si minimul sau maximul ceea ce este suficient pentru a afisa numerele.
DFS-ul este O(N) fiindca avem maxim N-1 muchii.  

Am solutie in python in O(n) de 12 linii. O puteti scoate mai scurt?

Tinem doua hashuri. Pentru fiecare hash cheia e valoarea numarului intalnit si valoarea asociata cheii
e numarul de elemente care incep sau se termina la numarul intalnit. Cand intalnim un numar facem update
la cele doua hashuri in O(1) (vedem daca exista valoarea+1 si valoare-1 in hashtable si facem update). La sfarsit, pentru fiecare numar cautam cele doua lungimi memorate in hashtable, facem suma lor si updatam lungimea maxima.

Solutia O(N) cu hashuri e exact cea din primul post. Mai exact pentru fiecare element tinem capatul din stanga si capatul din dreapta al intervalului din care apartine. Atunci cand dam de un element cu valoarea x facem urmatorii pasi

1) Daca l-am intalnit il ignoram, sarim pasii urmatori
2) Daca exista in hash x - 1 unim hashul lui cu elementul curent
     mai exact fie [y, x - 1] intervalul din care apartine x - 1(nu se poate mai la dreapta pentru ca pana la momentul actual nu exista x)
     updatam in hash-ul lui y ca intervalul e [y, x] si la fel si in hash-ul lui x.
3) Daca exista in hash x + 1 unim intervalul lui x cu cel al lui x + 1 pe aceeasi idee ca la pasul 2

In total la un pas facem un numar constant de operatii si sunt numar constanti de pasi => pentru fiecare element facem un numar constant de operatii => complexitate O(N).

Aduce a paduri de multimi disjuncte dar este o particularitate.

Pentru Cosmin Negruseri: Exista vreo solutie care nu foloseste hash-uri si e mai buna de O(N log N)?

@Cosmin: Depinde cât trișez. :) Dacă le înghesui încape pe 10 linii (cu tot cu I/O).

Sau chiar 9 daca citesti direct in int cu struct.readInt32  \:D/
Normal sunt vreo 20 de linii, iar memoria e O(n*3) [cred].

O(N*3) nu exista. Faptul ca tii 3 vectori/liste/hashuri cu N elemente nu inseamna ca aloci O(N*3) memorie.

Nu știu ce zici aici. Uite codul meu:

Probabil imi scapa ceva, dar de ce nu duci doar muchie de la pozitia lui x la pozitia lui x + 1 si faci un DF la final?

Asa merge interactiv. Alta utilitate nu vad, DF-ul tot e varianta mai simpla.

Pare ca v-ati cam complicat. Asa fac eu

Ideea e ca punctele interesante sunt doar capetele din stanga ale posibilelor multimi compacte.

Codul mai compresat putin:

Îmi aduce aminte de statusul unui amic:

Ovidiu Gheorghioiu stie programare functionala :) si reduce solutia mea la 3 linii:

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ă :P

Teoria și cât de rapid merg algoritmii
Eu î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:
... 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:

Î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.

@Mihai, mersi de contributie. Ar fi mers comentariul tau ca spot separat pe blog :).
Legat de problema elementelor distincte, ai ceva referinte curate?
Bun "rule of thumb" hashing > radix sort > quick sort.

Pare ca in industrie lumea nu foloseste radix sort asa des, probabil pt ca trebuie sa sorteze obiecte nu intregi.

M-am uitat la cateva limbaje sa vad cum fac:

C are implementat un quick sort care e tunat sa nu aiba probleme cu cazuri degenerate si sa aiba complexitate O(n log n) in general. Jon Bentley, autorul are un talk de care v-am mai spus: http://www.youtube.com/watch?v=aMnn0Jq0J-E

In C++ se foloseste intro sort.
http://www.sgi.com/tech/stl/sort.html (documentatie)
www.sgi.com/tech/stl/stl_algo.h (cod sursa)

Python pare ca foloseste un merge sort modificat, si daca sirul de la intrare e scurt face binary insertion sort.
http://hg.python.org/cpython/file/1eae8154c109/Objects/listsort.txt (explicatie detaliata)
http://hg.python.org/cpython/file/1eae8154c109/Objects/listobject.c (cod sursa)

Java pare ca foloseste merge sort pentru liste, varianta de quick sort din C pentru siruri de bytes, floats, ints si un  merge sort modificat pt siruri de obiecte.
http://docs.oracle.com/javase/1.5.0/docs/api/java/util/Arrays.html (documentatie)
http://www.docjar.com/html/api/java/util/Arrays.java.html (cod)
Uitandu-ma la cod vad ca cei din Java sunt in proces de tranzitie pe sortul din python pentru obiecte generale.


E interesant ca pentru sortari distribuite in MapReduce sau Hadoop, iau intai un sample al datelor. Asa se prind de distributie, pentru a partitiona datele in bucati de marime cat de cat egala si a le copia doar o data prin retea la calculatorul care le va sorta pe final. Pasul asta e important pentru ca la sortari distribuite se petrece mult timp in pasul de copiere al datelor pe retea.La terasort/petasort obiectele sortate erau siruri de 100 de bytes, deci presupun ca se foloseste radix sort pentru sortarea locala (nu am gasit nici o referinta externa la hadoop sau mapreduce care sa zica clar ce fac pt sortare locala).
http://googleresearch.blogspot.com/2011/09/sorting-petabytes-with-mapreduce-next.html
http://research.google.com/archive/mapreduce-osdi04.pdf

Varianta din Python e descrisă ceva mai pe scurt în Wikipedia: Timsort (http://en.wikipedia.org/wiki/Timsort).

Am scris mai demult ceva de radix sort (http://rgrig.blogspot.com/2008/08/sorting-out-stuff.html). (Dacă vă uitați, aveți grijă că folosesc alte litere.) Citind acum în diagonală văd două lucruri care nu cred că s-au spus mai sus.
1. Numarul optim de bucketuri depinde de lungimea listei sortate, dar nu depinde de numărul de biți pe cuvânt.
2. O implementare de mână e cam de 2--3 ori mai rapidă decât std::sort.

Hmm, cred ca am incercat radix sort pentru suffix arrays si tin minte ca std::sort() mergea mai repede. (http://infoarena.ro/siruri-de-sufixe) Ar trebui sa incerc din nou.

Si eu am incercat si am ajuns la aceeasi concluzie. std::sort chiar se comporta la fel de bine, chiar mai bine uneori.

La suffix arrays foloseam o combinatie de radix cu stl::sort, si anume sortam cu radix dupa prima valoare si apoi sortam cu sort dupa a 2a.
Stiu ca in felul asta obtineam timpi semnificativi mai buni decat daca as fi folosit doar una din metode.
http://infoarena.ro/job_detail/285375?action=view-source

La mine pe calculator asta văd:

      size  std::sort     rsort0     rsort1     rsort2     rsort3     rsort4
       100      0.000    x13.500     x7.000     x6.500    x55.500  x7996.250
      1000      0.000    x55.778     x4.417     x2.306     x4.889  x1649.028
     10000      0.000    x10.685     x3.476     x1.813     x1.121   x116.789
    100000      0.006     x5.298     x2.667     x1.344     x0.734    x10.838
   1000000      0.067     x4.733     x2.393     x1.223     x0.667     x2.037
  10000000      0.753     x4.668     x2.360     x1.205     x0.645     x1.247
 100000000      8.600     x4.269     x2.163     x1.112     x0.598     x1.150


Adică radix sort merge mai repede dacă grupează pe octeți (rsort3 înseamnă că grupează câte 2³ biți) și vectorul are peste 10⁵ elemente. (Dar nu așa de repede cum am zis mai devreme.)

Am generat vectorul cu rand() și am compilat cu -O3, g++-4.4.

@Mihai Patrascu

Super explicatia! (recunosc am recitit-o de cateva ori pana s-o inteleg cat de cat calumea). Am cam aberat grav la complexitate, heh. De acum inainte o sa las comentariile despre teoria fundamentala in informatica in mainile celor care se pricep.

putem deodata de la citire sa il sortam

Counting sort a fost deja mentionat.