JavaScript - testowanie wydajności algorytmów

W tym artykóle chcielibyśmy przedstawić, w jaki sposób można testować wydajność kodów lub algorytmów napisanych w JavaScript.

Gdy porównujemy czas wykonywania się algorytmów, warto powtórzyć pomiar wile razy, aby dostać wiarygodne wyniki. Takie podejście znajduje również zastosowanie w przypadku, gdy czas pojedyńczego wykonania algorytmu jest dosyć krótki. Ilość takich powtórzeń wyznaczana jest empirycznie (tzn. wybieramy tyle powtórzeń, aby czas wykonywania algorytmu dał się porównać z innym algorytmem - np. dany algorytm jest n-razy szybszy od drugiego). Część kodu, która nie stanowi algorytmu nie powinna podlegać pomiarom (np. inicjalizacja danych, itp.).

Szablonowy program do testowania:

// ONLINE-RUNNER:browser;

const test = (repeats, description, func) => {
	const t1 = Date.now();
  	for (let i = 0; i < repeats; ++i) {
  		func();
    }
  	const t2 = Date.now();
  	const dt = t2 - t1;
  	console.log(`${description}: totoal time is ${dt} ms`);
};


// Przykład użycia:

const repeats = 100000; // należy ustaić liczbę powtórzeń w zależności od złożoności badanych przypadków

test(repeats, 'przypadek 1', () => { /* kod uruchamiający algorytm 1 */ });
test(repeats, 'przypadek 2', () => { /* kod uruchamiający algorytm 2 */ });
test(repeats, 'przypadek 3', () => { /* kod uruchamiający algorytm 3 */ });

// możla tutaj dodać więcej przypadków do testowania ...

Wskazówka: powyższy kod źródłowy opisuje prosty sposób porównywania szybkości algorytmów - w praktyce testy wykonywane przez benchmarki są dużo bardziej precyzyjne.

Przktyczny przykład

W poniższym przykładzie, porównujemy algorytmy łaczenia tablic z pomijaniem zduplikowanych wartośći.

Całkowite czasy dla 10000 powtórzeń testów na procesorze Ryzen 9 x5900 zwróciły następujące wyniki:

łączenie tablic z obiektem pomocniczym: czas całkowity wyniósł 24 ms
łączenie tablic z strukturą Set: czas całkowity wyniósł 74 ms

Wniosek: rozwiązanie wykorzystujące algorytm z strukturą Set jest 3 razy wolniejszy.

Kod źródłowy testu: 

// ONLINE-RUNNER:browser;

const test = (repeats, description, func) => {
	const t1 = Date.now();
  	for (let i = 0; i < repeats; ++i) {
  		func();
    }
  	const t2 = Date.now();
  	const dt = t2 - t1;
  	console.log(`${description}: czas całkowity wyniósł ${dt} ms`);
};


// Testowane algorytmy:

const mergeArrays1 = (...arrays) => {
    const values = {}; // prevents duplications
    const result = [];
    for (let i = 0; i < arrays.length; ++i) {
        const array = arrays[i];
        for (let j = 0; j < array.length; ++j) {
            const item = array[j];
            if (item in values) {
                continue;
            }
            values[item] = true;
            result.push(item);
        }
    }
    return result;
};

const mergeArrays2 = (array1, array2) => {
  	return [...new Set([...array1, ...array2])];
};

// Dane wejściowe:

const array1 = [1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5];
const array2 = [3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6];

// Test wydajności:
  
const repeats = 10000; // należy ustaić liczbę powtórzeń w zależności od złożoności badanych przypadków

test(repeats, 'łączenie tablic z obiektem pomocniczym', () => mergeArrays1(array1, array2));
test(repeats, 'łączenie tablic z strukturą Set', () => mergeArrays2(array1, array2));