Cześć 🙂

Będąc na jednej z rozmów kwalifikacyjnych zostałem poproszony o napisanie funkcji zwracającej unikalne wartości z tablicy podanej jako argument. Wydaje mi się to ciekawym zadaniem i chciałbym się z tym z Wami podzielić.

Typy proste

Zacznijmy od najprostszej wersji – typów prostych, takich jak między innymi string czy number.

Tutaj mamy dwa podejścia do napisania takiej funkcji:

  • Możemy użyć funkcji indexOf żeby znaleźć index (pierwszy) elementu i na tej podstawie przefiltrować tablicę:
const values = [1, 2, 3, 4, 3, 2, 1];

const uniq = arr => arr.filter((el, i) => arr.indexOf(el) === i);

uniq(values); // [1, 2, 3, 4];
  • Możemy użyć obiektu Set, który przechowuje tylko unikalne wartości:
const values = [1, 2, 3, 4, 3, 2, 1];

const uniq = arr => [...new Set(arr)];

uniq(values); // [1, 2, 3, 4];

Testy, na których zobaczymy, który z wyżej napisanych algorytmów jest szybszy możecie znaleźć tutaj.

Wyniki (im więcej operacji tym lepiej)

  1. Set – 362,652
  2. IndexOf -191,022

Callback

Teraz spróbujmy użyć funkcji przekazywanej jako callback do funkcji uniq, która pozwoli nam wybrać element który ma być unikalny:

const arr = [{ a: 1, b: 0 }, { a: 1, b: 2}, {a: 2, c: 1}];

uniq(arr, el => el.a); // [{ a: 1, b: 0}, { a: 2, c: 1}];

Przeanalizujmy trzy podejścia do napisania takiej funkcji. W każdym z podejść używamy innego elementu do przechowywania unikalnych wartości:

Array

const uniq = (arr, fn) => {
    const uniqueValues = [];
    
    return arr.filter((element, index) => {
        const value = fn(element);

        if (uniqueValues.includes(value)) {
            return false;
        }
        
        uniqueValues.push(value);
        return true;
    });
};

Object

const uniq = (arr, fn) => {
    const uniqueValues = {};
    
    return arr.filter((element, index) => {
        const value = fn(element);

        if (typeof uniqueValues[value] !== 'undefined') {
            return false;
        }
        
        uniqueValues[value] = value;
        return true;
    });
};

Set

const uniq = (arr, fn) => {
    const uniqueValues = new Set();
    
    return arr.filter((element, index) => {
        const value = fn(element);

        if (uniqueValues.has(value)) {
            return false;
        }
        
        uniqueValues.add(value);
        return true;
    });
};

Testy, na których zobaczymy, który z wyżej napisanych algorytmów jest szybszy możecie znaleźć tutaj.

Wyniki (im więcej operacji tym lepiej)

  1. Array – 5,115,177
  2. Set – 4,132,682
  3. Object – 2,075,234

Podsumowanie

Jak widać Array okazał najszybszym się algorytm wykorzystujący do przechowywania wartości unikalnych. Warto sobie przeprowadzać testy na różne algorytmy wykorzystując do tego http://jsperf.com 🙂