NodeJS array.indexof на несколько порядков быстрее, чем set.has и set.has на несколько порядков быстрее, чем array.indexof! == -1 - PullRequest
Новая
       72

NodeJS array.indexof на несколько порядков быстрее, чем set.has и set.has на несколько порядков быстрее, чем array.indexof! == -1

0 голосов
/ 28 января 2020

Я знаю, что сложность времени проявляется для больших входных данных, но для любого входного массива. Index быстрее. Например, для n = 20.000 массив занимает 0,008 мс, а набор занимает 0,4 мс

Я протестировал массив против набора с использованием этого кода: 

const NS_PER_SEC = 1e9;
const MS_PER_NS = 1e-6

function runTest(test) {
    let time = process.hrtime();
    test();
    let diff = process.hrtime(time);
    return (diff[0] * NS_PER_SEC + diff[1])  * MS_PER_NS 
}

function makeRandomString() {
    let length = Math.round(Math.random() * 4 + 2);
    let result = '';
    let characters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789- ';
    let charactersLength = characters.length;
    for (let i = 0; i < length; i++) {
        result += characters.charAt(Math.floor(Math.random() * charactersLength));
    }
    return result;//Math.floor(Math.random()); //result;
}

function main() {
    let testCases = [10, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 40000, 100000, 10000000];
    let times = 5000;
    let words = [];
    for (let i = 0; i < times; i++) {
        words.push(makeRandomString());
    }

    for (let tci = 0; tci < testCases.length; tci++) {
        let array = [];
        const items = testCases[tci];
        for (let i = 0; i < items; i++) {
            array.push(makeRandomString());
        }
        console.log('List ' + items);
        for (let i = 0; i < 10; i++) {
            let res = runTest( () => {
                for (let j = 0; j < times; j++) {
                    let tmp = array.indexOf(words[j]);
                }
            });
            console.log(res);
        }
        console.log('Set ' + items);
        let set = new Set(array);
        for (let i = 0; i < 10; i++) {
            let res = runTest(() => {
                for (let j = 0; j < times; j++) {
                    let tmp = set.has(words[j]);
                }
            });
            console.log(res);
        }
    }
}
main();

Но изменив только следующую строку: 

                    let tmp = array.indexOf(words[j]);

в: 

                    let tmp = array.indexOf(words[j]) !== -1;

Я получаю ожидаемые результаты - например, для n = 20.000 массив занимает 333 мс и задает 0,4 мс.

Как это может быть ? Конечно, !== -1 не может замедлить линию на порядки.

1 Ответ

2 голосов
/ 28 января 2020

Я не согласен с тем, что Set.has "порядков" медленнее, чем Array.indexOf . Я думаю, что есть какой-то механизм кеширования кода V8, и поэтому вы видите эти результаты.

Когда я смотрю на ваш код, я вижу, что вы выполняете один и тот же тест с одинаковыми значениями в 10 раз: 

for (let i = 0; i < 10; i++) {
    let res = runTest(() => {
        for (let j = 0; j < times; j++) {
            let tmp = array.indexOf(words[j]);
        }
    });
    console.log(res);
}

Я не уверен, что ваши тесты выполнены правильно. Когда я настраиваю ваш скрипт так, чтобы он выглядел так: 

const NS_PER_SEC = 1e9;
const MS_PER_NS = 1e-6

function runTest(test) {
    let time = process.hrtime();
    test();
    let diff = process.hrtime(time);
    return (diff[0] * NS_PER_SEC + diff[1]) * MS_PER_NS
}

function makeRandomString() {
    let length = Math.round(Math.random() * 4 + 2);
    let result = '';
    let characters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789- ';
    let charactersLength = characters.length;
    for (let i = 0; i < length; i++) {
        result += characters.charAt(Math.floor(Math.random() * charactersLength));
    }
    return result;
}

function main() {

    let testCases = [100000, 200000, 300000, 400000];
    let times = 5000;
    let testResults = {};

    for (let tci = 0; tci < testCases.length; tci++) {
        let array = [];
        let words = [];
        const items = testCases[tci];

        for (let i = 0; i < times; i++) {
            words.push(makeRandomString());
        }

        for (let i = 0; i < items; i++) {
            array.push(makeRandomString());
        }

        let set = new Set(array);
        let msSetTest = runTest(() => {
            for (let j = 0; j < times; j++) {
                let tmp = set.has(words[j]);
            }
        });

        let msArrayIndexOfTest = runTest(() => {
            for (let j = 0; j < times; j++) {
                let tmp = array.indexOf(words[j]);
            }
        });

        let msArrayIndexOfEqTest = runTest(() => {
            for (let j = 0; j < times; j++) {
                let tmp = array.indexOf(words[j]) !== -1;
            }
        });

        testResults[`${items} items`] = { 'Set.has (ms)': msSetTest, 'Array.indexOf (ms)': msArrayIndexOfTest, 'Array.indexOf !== -1 (ms)': msArrayIndexOfEqTest };
    }

    console.table(testResults);
}

main();

Я вижу следующий вывод: 

┌──────────────┬────────────────────┬────────────────────┬───────────────────────────┐
│   (index)    │    Set.has (ms)    │ Array.indexOf (ms) │ Array.indexOf !== -1 (ms) │
├──────────────┼────────────────────┼────────────────────┼───────────────────────────┤
│ 100000 items │ 1.0594569999999999 │    1335.504929     │        1341.52334         │
│ 200000 items │      2.264941      │    2004.631142     │    2931.9868469999997     │
│ 300000 items │ 2.2363969999999997 │      0.851231      │        4597.312417        │
│ 400000 items │      1.05495       │ 5333.842428999999  │        5308.093365        │
└──────────────┴────────────────────┴────────────────────┴───────────────────────────┘

Обратите внимание, что значение 300000 items Array.indexOf равно 0.851231 мс кеширование кода, вероятно, имело место, и при использовании !== кеш не мог иметь место.

...