Блог

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

Я замечаю, что очень странный эффект Array.includes на порядок быстрее, чем Set.has . Несмотря Set.has на то, что гораздо больше возможностей для оптимизации поиска: это целая идея использования set .

Мой код инициализации (этот код выходит за рамки времени для тестов):

 function shuffle(a) {
    for (let i = a.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i   1));
        [a[i], a[j]] = [a[j], a[i]];
    }
}

const arr = []
for (let i = 0; i < 1000; i =1) {
    arr.push(i);
};

shuffle(arr);
const prebuildset=new Set(arr);
  

И тесты:

 (new Set(arr)).has(-1); //20.0 kOps/s
arr.includes(-1); //632 kOps/s
(new Set(arr)).has(0); //20.0 kOps/s
arr.includes(0); //720 kOps/s
prebuildset.has(-1); //76.7 kOps/s
prebuildset.has(0); //107 kOps/s
  

Протестировано с chrome 73.0.3683.103 в Ubuntu 18.04 с использованием https://jsperf.com/set-array-has-test/1

Я могу ожидать, что версии, которые создают набор «на лету», будут медленнее, чем прямое тестирование массива на включение. (Хотя мне было бы интересно, почему chrome не оптимизирует массив JIT — я также тестировал использование литерального массива и литерального массива, а использование переменной вообще не имеет значения в скорости). Однако даже готовые наборы на порядок медленнее, чем тест на включение массива: даже для самого отрицательного случая (запись не внутри массива).

Почему это так? Что за черная магия происходит?

РЕДАКТИРОВАТЬ: я обновил тесты, чтобы перетасовать результаты, чтобы не слишком сильно искажать раннюю остановку array.includes() , хотя она уже не в 10 раз медленнее, она все еще во много раз медленнее, очень актуальна и отличается от того, что я ожидаю.

Начну с того, что я не эксперт по реализации движка JavaScript и оптимизации производительности; но в целом, вы не должны доверять такого рода тестам, чтобы дать вам надежную оценку производительности.

Временная сложность базового алгоритма становится значимым фактором только при очень (очень) больших числах, и, как правило, 1000, безусловно, не такое большое число, особенно для простого массива целых значений.

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

В качестве примера я отредактировал ваши тесты, просто увеличив размер массива до 100 000. Результаты на моем бедном старом ноутбуке выглядят так:

 arr.includes(-1); //3,323 Ops/s
arr.includes(0); //6,132 Ops/s
prebuildset.has(-1); //41,923,084 Ops/s
prebuildset.has(0); //39,613,278 Ops/s
  

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