Salutare,
Să spunem că ai o aplicație care primește o serie de mesage, identificate printr-un ID unic. Chiar dacă nu ar trebui să primească același mesaj de două ori, din varii motive, acest lucru se întâmplă. Din acest motiv, ne propunem să scriem un mic algoritm prin care să detectăm faptul că în această listă de mesaje primite într-o azi avem cel puțin un duplicat. Nu ne interesează care este mesajul în cauză.
Haideți să luăm un mic exemplu pentru a face lucrurile cât mai clare: ["id1, "id2", "id3", "id4", "id1", "id5", "id6"]. După cum se poate observa foarte ușor, unul din id-uri, în speță "id1" se repetă în lista noastră. Bineînțeles că puteau fi și mai multe id-uri în această situație.
Ni se cere să scriem o funcție, care să returneze un boolean, cu următoarea semnificație: dacă lista conține id-uri duplicate să returneze true sau false dacă nu. În cazul prezentat mai sus, funcția va returna true. Momentan nu ne punem nicio problemă de concurență. Semnătura metodei va fi:
public boolean containsDuplicateId(final List<String> ids);O implementare naivă cu 2 for-uri
O primă variantă de implementare ar fi să folosim 2 for-uri imbricate pentru a compare fiecare element din listă cu celalalte elemente prezente ca să detectăm cel puțin un duplicat. În momentul în care am găsit cel puțin un duplicat, funcția noastră poate să returneze deja un rezultat. Soluția este straightforward, din acest motiv nici nu o voi mai implementa. Complexitatea de timp va fi: O(n2). Complexitatea de spațiu va fi O(1). Cu alte cuvinte, nu avem nevoie de memorie adițională pentru această funcție, dar din păcate avem nevoie de mult procesor pentru a rula această metodă.
În plus, probabil că știți deja o implementare foarte asemănătoare pentru sortarea unei liste - metoda bubble sort. Hmm dacă tot vorbim de sortare, nu am putea să folosim cumva sortarea pentru a le ordona și pentru a detecta mai rapid duplicate?
O implementare îmbunătățiță bazată pe sortare
Dacă tot ne-a venit ideea de bubble sort, ce ar fi dacă am aplica o sortare listei noastre? După aplicarea unei alte funcții de sortare, lista noastră ar arăta altfel: ["id1, "id1", "id2", "id3", "id4", "id5", "id6"]. Cu ușurință se poate observa acum că la o traversare liniară asupra listei, vom putea detecta duplicatele doar prin a compara elementul curent cu elementul următor, dacă acesta există bineînțeles. O traversare liniară înseamnă O(n), în aceea ce privește complexitatea de timp.
Dar încă nu am rezolvat problema noastră, pentru că folosim bubble sort, care comsună mult timp pe procesor. Cu alte cuvinte, ne trebuie un algoritm mai smart pentru sortare. Din fericire, putem alege un quicksort, care să aibă o complexitate: O(nlogn).
Complexitatea legată de spațiu / memorie folosită rămâne aceeași: O(1). Am înbunătățit considerabil complexitatea legată de timp, un lucru foarte bun de altfel.
Putem să mergem mai departe cu îmbunătățirea complexității legate de timp?
Răspunsul este da, se poate merge mai departe. Dar atenție! Vom îmbunătăți complexitatea legată de timp, dar din păcate vom crește complexitatea legată de spațiu. Cu alte cuvinte, varianta pe care urmează să o prezint, va avea o complexitate de spațiu de O(n).
Această variantă de fapt se bazează pe modelarea valorilor prin folosirea internă a unei noi structuri de date, în loc de listă, prin care să putem insera și căuta rapid elemente. De ce? În prima variantă descrisă, căutarea primului element în întreaga listă se făcea în O(n). Se poate face mai rapid? Adică în O(nlogn) sau chiar O(1) - timp constant? Răspunsul este da, folosind un HashMap.
Dacă HashMap-ul nostru nu are coliziuni, căutarea și inserarea într-un map se face în O(1). Acest lucru este perfect pentru noi. Dezavantajul este faptul că vom menține un HashMap în plus, deci vom folosi mai multă memorie. Cu alte cuvinte, dacă aplicația noastră prezintă constrângeri legate de memorie, atunci poate e mai bine să mergem cu varianta sortării.
Dar ce vom stoca în HashMap? Un map este un pair de chei și valori. În cazul de față cheia = valoarea = un element in listă. Cu alte cuvinte, putem să folosim fără probleme un HashSet. Sper să știați că în Java HashSet se bazează pe HashMap ca și implementare, nu?
Hai să vedem și o posibilă implementare:
public boolean containsDuplicateId(final List<String> ids);
final Set<Integer> set = new HashSet<>(ids); // complexitatea de spatiu e O(n).
for (String id: ids) { // iteram liniar peste toate id-urile, adica O(n).
if (set.contains(id)) { // cautarea se face in O(1)
return true;
}
set.add(id); // adaugarea in O(1)
}
return false;
}Recapitulare
Dragilor, ceea ce am făcut eu în acest articol este să descriu o problemă - cât se poate de simplă ce e drept și să încerc pas cu pas să descriu care ar trebui să fie mindset-ul pe care să-l aveți atunci când lucrați la dezvoltarea unei soluții. Întotdeauna trebuie să pornim cu soluția cea mai intuitivă, cea care ni se pare cea mai simplă. Pasul următor este să punem această soluție pe hârtie și să fim capabilă să o analizăm atât din perspectiva complexității de timp cât și a celei de spațiu. După ce am analizat-o, va trebui să ne folosim toate cunoștiințele dobândite în timp, pentru a încerca să găsim soluții care să adreseze și să îmbunătățească varianta respectivă. În programare, mulți developeri se bazează pe următorul principiu: nu îmbunătăți ceva ce poate nu trebuie îmbunătățit sau este acceptabil. Recunosc, sunt situații în care poate este foarte dificil să găsești o variantă mult mai bună într-o perioadă scurtă de timp. În această situația, da, este bine să nu stăm o lună, două, trei, până când ne dăm bătuți sau poate găsim o soluție mai bună. Managementul nu ne va acorda acest timp. Asta e realitatea. Dar, asta nu înseamnă că întotdeauna o să procedăm așa. A nu te gândi sub nicio formă la complexitatea legată de timp și spațiu, înseamnă că de la zi la alta codul aplicației tale va fi din ce în ce mai lent, cu mai multe resurse hardware consumate, adică cu costuri din ce în ce mai mari.
Pentru o aplicație mică, care consumă 100-200 MB de memorie RAM, poate nu e o problemă, pentru că în final vei cumpăra o plăcuță RAM de 1GB care îți va satisface nevoile. Dar haideți să ne gândim ce se întâmplă dacă mâine aplicația are nevoie de 512GB RAM?
Promit să mai vorbim de mindset și în articolele următoare... :)
