Тестирование различных техник для работы с довольно большими массивами

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

Соревнование

Напишите программу для классификации дубликатов в списке. Сначала сгенерируйте список из N + 1 int со значениями в диапазоне от 1 до N. Следовательно, в списке должен быть хотя бы один дубликат. Напишите функцию, которая найдет и распечатает все повторяющиеся целые числа.

Чтобы уточнить:

N = 3. В результате будет создан список с целыми числами N + 1 = 4 в диапазоне от 1 до ›3,
например {2, 3, 3, 2}. Поэтому ваша функция должна распечатать «2» и «3».

N = 4. Это приведет, например, к {3, 2, 1, 1, 4}, а затем вам
придется вывести значение ' 1 '.

Требования:

  1. Значение N должно быть указано в качестве аргумента командной строки. Значение
    по умолчанию должно быть 1 000 000.
  2. Поиск дубликатов критичен по времени,
    сделайте это максимально эффективным.

Руки вверх:

Https://github.com/andreluizmartinsramos/duplicates-benchmarking

  1. Создать массив

2. Стратегия первая: Поиск по .indexOf

3. Стратегия вторая: Сопоставление объектов

4. Стратегия третья: Далее и назад

Результат сравнения

После 10-кратного выполнения каждого алгоритма мы получили следующие результаты:

Вывод

Это только часть исследования, вероятно, существуют другие алгоритмы, более эффективные, чем упомянутые выше, однако любопытно понять разницу в поведении каждого из них. Крутые моменты:

  • Чем меньше объем данных, тем эффективнее Array Strategies [1,3];
  • Прежде чем создавать свою структуру данных, подумайте: «Сколько данных у нас будет?». Стратегия может меняться в зависимости от вашего количества, обратите внимание на разницу в 1.000 (предполагается, что используется Object) между 10.000 (предполагается, что используется Array.indexOf).
  • Обратите внимание, что Prev & Next никогда не было лучшим способом сделать это.
  • Для работы с ~ 100 000 номеров .indexOf в 20 раз лучше, чем другие, но не работает с 1 000 000 номеров.
  • Наконец, исследование показало, что когда вам нужно работать с ~ 1.000.000, Object Mapping - лучшая стратегия.

Не стесняйтесь поделиться другими идеями, чтобы улучшить этот тест! Наша цель - улучшить код каждого.

Бонус

Тестовые кейсы

Тестирование: generateArr

Тестирование: getAllDuplicates

Результат тестов