Тестирование различных техник для работы с довольно большими массивами
В настоящее время в мире современных фреймворков 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 '.
Требования:
- Значение N должно быть указано в качестве аргумента командной строки. Значение
по умолчанию должно быть 1 000 000. - Поиск дубликатов критичен по времени,
сделайте это максимально эффективным.
Руки вверх:
Https://github.com/andreluizmartinsramos/duplicates-benchmarking
- Создать массив
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 - лучшая стратегия.
Не стесняйтесь поделиться другими идеями, чтобы улучшить этот тест! Наша цель - улучшить код каждого.