
W dzisiejszym artykule zajmiemy się tematem bardzo ważnym, mianowicie: algorytmy i struktury danych w JavaScript. Jest to temat ważny dla programowania w ogóle. Nie należy mieć uprzedzeń – JavaScript nadaje się do tego celu bardzo dobrze. Być może pewne rzeczy będą w przypadku tego języka nieco trudniejsze, ale za to inne będą uproszczone, jak chociażby podstawowa implementacja stosu (FIFO).
Algorytmy w JavaScript
My skupimy się dziś bardziej na przykładach rozwiązań, niż na samej teorii.
Silnia
Na początek klasyka, czyli silnia obliczana rekurencyjnie.
Przykład – obliczanie silni w JavaScript:
function silnia(n) { if (n == 0) return 1; else return (n * silnia(n-1)); } alert(silnia(5));
Rok przestępny
Kolejnym algorytmem jest sprawdzanie, czy podany rok jest rokiem przestępnym czy też nie.
// is leap year - JavaScript function checkLeapYear(year) { if ( ((year % 4 == 0) && (year % 100 != 0)) || (year % 400 == 0) ) { alert('Rok ' + year + ' jest przestępny'); return true; } else { alert('Rok ' + year + ' NIE jest przestępny'); return false; } } alert(checkLeapYear(2012)); alert(checkLeapYear(2013));
Algorytm Min-Max
Czyli wyznaczanie najmniejszej i największej wartości z podanego zbioru.
Przykład – implementacja algorytmu min-max w JavaScript:
var tab = new Array(16, 9, 86, 48, 59, 2, 78, 240, 18); // default var min = tab[0]; var max = tab[0]; for (var i = 0; i < tab.length; i++) { if (min > tab[i]) { min = tab[i]; } if (max < tab[i]) { max = tab[i]; } } alert("Min = " + min + ", Max = " + max);
Jest to prosta, ale skuteczna implementacja bazująca na porównywaniu za sobą elementów tablicy.
Random string
Ten algorytm to prosty generator losowego łańcucha znaków.
var _list = "abcdefghijklmnopqrstuvwxyz9876543210"; function randomStringGenerator(how_long) { var tmp = '', i = 0; var list_len = _list.length; for (i = 0; i < how_long; i++) { tmp += _list.charAt(Math.floor(Math.random() * list_len)); } return tmp; } alert(randomStringGenerator(8));
Implementacja bazuje na wejściowej liście znaków (można ją dowolnie kształtować).
Wyszukiwanie binarne
Oparte na metodzie „dziel i zwyciężaj” wyszukiwanie binarne to prosty ale optymalny sposób wyszukiwania wartości nawet w dużych listach wejściowych.
Przykład – wyszukiwanie binarne w JavaScript:
inputList = new Array(); inputList[0] = 'E'; inputList[1] = 'I'; inputList[2] = 'O'; inputList[3] = 'P'; inputList[4] = 'Q'; inputList[5] = 'R'; inputList[6] = 'T'; inputList[7] = 'U'; inputList[8] = 'W'; inputList[9] = 'Y'; function binarySearch(inputList, key) { var left = 0; var right = inputList.length - 1; while (left <= right) { var mid = parseInt((left + right) / 2); if (inputList[mid] == key) return mid; else if (inputList[mid] < key) left = mid + 1; else right = mid - 1; } return 'Not found'; } alert(binarySearch(inputList, 'T')); alert(binarySearch(inputList, 'Z')); // Not found
Zobacz także: Wikipedia – Złożoność obliczeniowa.
Przejdźmy teraz do struktur danych.
Struktury danych w JavaScript
W JavaScript bez większych problemów zaimplementujemy także struktury danych.
Stos / LIFO
Stos (ang. Stack) lub też bufor typu LIFO (Last In, First Out czyli ostatni na wejściu, pierwszy na wyjściu) to klasyka przy omawianiu struktur danych.
W JavaScript można bardzo szybko zaimplementować działanie tej struktury danych.
Przykład – prosta implementacja stosu w JavaScript:
function odpowiednikStosu() { var stos = new Array(); stos.push('Audi'); stos.push('Skoda'); stos.push('Opel'); stos.push('VW'); // w tym przypadku na górze stosu znajduje się VW // ponieważ był dodany jako ostatni alert(stos.toString()); stos.pop(); // pobiera VW ze stosu alert(stos.toString()); // nie ma VW // dodajemy nowy element stos.push('Mercedes'); alert(stos.toString()); // teraz na "topie" jest Mercedes } odpowiednikStosu();
W tym przypadku korzystamy z tablic JavaScript oraz metod operacji na tablicach, które to występują także w implementacjach stosu:
– push() – wrzuć element na stos
– pop() – zdejmij ostatni element ze stosu
To oczywiście bardzo proste podejście. Możemy pokusić się o bardziej wyrafinowaną implementację stosu, na przykład taką jak zaprezentowana w serwisie algorytm.org:
http://www.algorytm.org/klasyczne/stos/stos-1-js.html
W JavaScript można implementować na wiele sposobów (czasem naprawdę błyskotliwych) inne, bardziej zaawansowane struktury danych, takie jak listy powiązane czy drzewa.
Kolejny punkt traktuje o bibliotekach oferujących algorytmy i struktury danych w JavaScript.
Biblioteki wspierające algorytmy i struktury danych w JavaScript
Własne implementacje algorytmów i struktur danych to z pewnością znakomity trening programowania.
Jednak w przypadku typowych algorytmów i struktur danych warto rozważyć biblioteki, ponieważ jeżeli coś jest zrobione dobrze i udostępnione, korzystajmy – to oszczędza nasz cenny czas.
Algorithms in JavaScript – biblioteka implementująca podstawowe algorytmy:
https://github.com/idosela/algorithms-in-javascript
Data Structures and Utilities – to bardzo ciekawa biblioteka z implementacjami wielu struktur danych w JavaScript:
https://github.com/monmohan/dsjslib
computer-science-in-javascript – implementacje kilku algorytmów i struktur danych, które przygotował guru JavaScript, Nicholas C. Zakas:
https://github.com/nzakas/computer-science-in-javascript
CryptoJS – to zaawansowana biblioteka implementująca algorytmy używane w kryptografii:
https://code.google.com/p/crypto-js/
Na koniec polecam także artykuł o strukturach danych w JavaScript, który oprócz kodów zawiera także graficzne przedstawienie działania struktur danych:
http://www.codeproject.com/Articles/669131/Data-Structures-with-JavaScript
Podsumowanie
Temat algorytmów i struktur danych jest naprawdę obszerny, szczególnie jeśli dodamy do niego zagadnienia złożoności obliczeniowej i optymalizacji. Ale bez wątpienia warto poznawać te zagadnienia.
Osobiście zagłębiam się coraz bardziej w programowanie gier w HTML5 i JavaScript, a w tym przypadku (jak i wielu innych) algorytmy i struktury danych są nieodzowne.
Dziękuję za uwagę.