Блог

Например, учитывая два массива (числа / буквенно-цифровые элементы):

 const a1 = [1, 2, 3, 4, 5];
const a2 = [1, 3, 5, 7, 9];
 

Я хочу получить что-то вроде:

 a3 = [1, 2, 3, 4, 5, 7, 9];
 

где не имеет значения, будут ли a1 или a2 уничтожены / изменены в процессе. Я нашел следующие три метода:

1.

 const a3 = [...new Set([...a1, ...a2])];
 

 const a3 = [...a1, ...a2].filter((element, index, arr) => {
    return index === arr.indexOf(element);
});
 

 a2.forEach((element) => {
        if (!a1.includes(element)) {
            a1.push(element);
        }
    });
 

Какой из этих или любых других методов является наилучшей практикой и / или более эффективным?

Использование набора имеет лучшую временную сложность. Таким образом, это означает, что вы можете найти размер массива таким образом, чтобы, когда входные массивы имели хотя бы такой размер, это решение с набором превосходило два других.

Здесь я разработал простой тестовый скрипт, который попытается найти размер массива, выше которого решение на основе набора выполняется быстрее. Поскольку существует множество факторов, которые определяют фактическую скорость выполнения (движок JS, оптимизатор времени выполнения, сборщик мусора, другие процессы, …), результат не следует воспринимать как точную цифру… просто как указание. Также попробуйте в разных браузерах.

Я сделал несколько вариантов (которые вы, конечно, можете изменить по своему вкусу):

• Два входных массива равны по размеру и имеют небольшие целые числа
• Первый массив имеет числа от 0 до n-1, где n — его размер.
• Второй входной массив имеет только кратные 5, в диапазоне от 0 до 5 (n-1)
• Оба массива перемешиваются
• Я выбрал решение на основе набора и вариант решения на основе включения.
• Тест подсчитывает, сколько раз выбранный алгоритм может выполнить работу с этими массивами в течение 500 миллисекунд.
• Эти два показателя сравниваются, чтобы решить, какой из них быстрее.

Размер массивов динамически адаптируется, поэтому для нахождения «идеального» размера оба значения примерно одинаковы.

Вот фрагмент:

 // Utility functions:
function shuffle(a) {
    var j, x, i;
    for (i = a.length - 1; i > 0; i--) {
        j = Math.floor(Math.random() * (i   1));
        x = a[i];
        a[i] = a[j];
        a[j] = x;
    }
    return a;
}

const delay = ms => new Promise(resolve => setTimeout(resolve, ms));

function hasSetBetterPerformance(length) {
    console.log("Measuring performance for arrays with length "   length   "...");
    
    // As test material we create 2 equal sized, numerical arrays.
    //   These arrays have no duplicates.
    //   The second one has 20% of its values occuring also 
    //   in the first, while the other 80% do not occur in the first.
    let arr1 = shuffle(Array.from({length}, (_, i) => i));
    let arr2 = shuffle(Array.from({length}, (_, i) => i * 5)); // 1 in 5 is a duplicate   
    let stop, res, balance = 0;

    // Execute the Set-based solution during 500 milliseconds
    stop = performance.now()   500;
    while (performance.now() < stop) {
        res = [...new Set([...arr1, ...arr2])];
        balance  ;
    }
    
    res = [];
    
    // Execute the includes-based solution during 500 milliseconds
    stop = performance.now()   500;
    while (performance.now() < stop) {
        res = [...arr1]; // To be fair, we must create a new array
        for (let element of arr2) {
            if (!arr1.includes(element)) res.push(element);
        }
        balance--;
    }
    
    return balance >= 0;
}


async function findTurningPoint() {
    let high = 2;

    // Find size for which Set algorithm is faster
    while (!hasSetBetterPerformance(high)) {
        high *= 2;
        await delay(10);
    }
    // Narrow down, using binary search...
    let low = high / 2;
    while (low < high) {
        let mid = Math.floor((low   high) / 2);
        if (hasSetBetterPerformance(mid)) {
            high = mid;
        } else {
            low = mid   1;
        }
        await delay(10);
    }
    console.log("Turning point after which Set is faster: arrays with length >=", low);
    return low;
}

findTurningPoint(); 

Разные прогоны могут давать разные результаты, но на моем ПК FireFox и Chrome сообщают о размере где-то между 50 и 90.

Таким образом, это может дать вам указание, следует ли использовать установленное решение, в зависимости от фактических размеров массива, с которым вы работаете.

Будьте осторожны: производительность может отличаться, когда значения массива имеют другой тип (значения с плавающей точкой, строки, …), или разная вероятность наличия дубликатов, или когда массивы не имеют одинакового размера. Все это следует учитывать.