Возможная неэффективность в реализации ArrayBuffer в стандартной библиотеке Scala

Question

Во время изучения программирования, я думаю, что наткнулся на неэффективность в Scala, учитывая, что описание в нашем материале является правильным. Возможность более легкого внедрения была подтверждена моим другом, который получил Серебряную и Бронзовую медали на Международной олимпиаде по информатике.

В нашем учебном материале написано: «Например, для ArrayBuffer очень эффективно добавлять элементы в конце: поскольку внутренний массив всегда удваивается в размере, выделение и копирование в новый массив происходит довольно редко. Напротив, добавление элемента в начале занимает много времени, поскольку выделяется новый внутренний массив и элементы копируются в него каждый раз, когда вызывается метод. "

Не может ли быть другой массив, хранящий индексы, чтобы он всегда добавлял элементы в конец?

Answer 1

Может быть второй массив, содержащий индексы, но он будет менее эффективным по ряду причин:

1. Массив индексов потребует дополнительного хранения

2. Для доступа к элементу потребуется как минимум два чтения из памяти, а не одно

3. Если индексы не сортируются, то каждый доступ требует поиска в массиве индексов

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