Algorytmy i struktury danych w JavaScript

javascript-html5-tutorial.pl

Listopad 4th, 2013

Dominik-W

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