ПРИМЕЧАНИЕ: Поскольку заголовок уже намекает, этот вопрос не о заданной c java.util.ArrayList реализации списка на основе массива, а о необработанных массивах самих себя и как они могут вести себя в «чистой» (то есть полностью неоптимизированной) реализации списка на основе массива. Я решил упомянуть java.util.ArrayList, потому что это наиболее яркий пример списка на основе массива в Java, хотя он технически не "чист", поскольку использует предварительное распределение для сокращения времени работы add(). Если вы хотите знать, почему я задаю этот конкретный вопрос c, не заинтересовавшись оптимизацией предварительного распределения java.util.ArrayList(), я добавил небольшое объяснение моего варианта использования ниже.
Общеизвестно, что вы можете получить доступ к элементам в списках на основе массива (например, Java ArrayList<E>) с временной сложностью O(1), а для добавления элементов в этот список потребуется O(n). Со связанными списками все наоборот (для дважды связанного списка вы могли бы оптимизировать доступ к половине времени выполнения).
Причина, по которой добавление элементов в список на основе массива занимает O(n) в том, что массив не может быть просто изменен, но должен быть перераспределен и перезаполнен. Самый простой способ сделать это:
String arr[] = new String[n];
//...
String newElem = "foo";
String[] newArr = new String[n + 1];
int i = 0;
for (String elem : arr) {
newArr[i] = arr[i++];
}
newArr[i] = newElem;
arr = newArr;
Сложность времени O(n) хорошо видна благодаря функции для l oop. Но есть и другие способы скопировать массивы в Java, например, System.arraycopy().
Придерживаться ванили для решения l oop, даже сжатие массив займет O(n), поскольку массив имеет фиксированный размер и для его «сжатия» необходимо скопировать все сохраняемые элементы в новый меньший массив.
Итак, вот мои вопросы, касающиеся таких операции с массивами и их временная сложность:
Хотя ваниль для l oop всегда будет принимать O(n), возможно ли, что System.arraycopy() оптимизирует операцию добавления, если есть Достаточно места в памяти, чтобы расширить массив на месте, а это означает, что он оставит исходный массив на своем месте и просто добавит новый элемент в конце его?
Как сокращение операция всегда может быть выполнена теоретически с O(1), всегда ли System.arraycopy() оптимизирует эту операцию до O(1)?
Если System.arraycopy() равно не способен использовать эти оптимизации, есть ли ее путь в Java для фактического использования тех оптимизаций, которые возможны в теории ИЛИ будет массив "изменение размера" всегда займет O(n), независимо от того, при каких обстоятельствах?
TL; DR: есть ли ситуация, в которой "изменение размера" массива в Java займет менее O(n)?
Дополнительная информация:
Я использую openJDK11 ( самый новый выпуск), но если ответ окажется зависимым от JVM, я хотел бы знать, как другие JVM будут вести себя в сравнении.
Для любопытных
, которые хотят знать что я хочу сделать с этой информацией:
Я работаю над новой реализацией java.util.List, а именно гибридным списком, который может хранить данные в массиве и в связанном буфере. В некоторых случаях буфер будет сброшен в массив, что, конечно, требует изменения размера существующего массива. Но помимо этой идеи, я хочу использовать как можно больше других оптимизаций в части массива. Чтобы вообще избежать изменения размера массива, я экспериментировал с идеей сохранения массива в постоянном размере, но управления его «допустимым» диапазоном с некоторыми другими полями. Это означает, что если вы вытолкнете последний элемент массива, это уменьшит не массив, а диапазон допустимых элементов. Затем, при вставке новых элементов в часть массива, прежний недопустимый раздел может использоваться для сдвига значений, в основном повторно используя пространство, которое ранее использовалось теперь удаленным элементом. Если операции вставки превышают фактический размер массива, элементы все еще могут быть переданы в связанный буфер, чтобы избежать изменения размера. Для дальнейшей оптимизации я выбрал использование середины массива в качестве оси при удалении определенных элементов. Теперь допустимый диапазон может не начинаться с начала массива. По сути, это означает, что если вы удаляете элемент слева от оси, все элементы между началом допустимого диапазона и удаленным элементом смещаются в направлении оси, вправо. Удаление элемента справа от оси работает соответственно. Таким образом, после некоторого удаления массив может выглядеть следующим образом:
[null null|elem0 elem1 elem2||elem3 elem4 elem5|null null null]
(где | в начале и в конце помечают допустимый диапазон, а || обозначает ось)
Итак, как все это связано с моим вопросом?
Все эти оптимизации основаны на утверждении, что изменение размера массива дорого по времени, а именно O(n). Поэтому изменение размера массива по возможности избегается. Эти оптимизации могут показаться изящными, но код, реализующий их, может стать довольно грязным, , особенно , при реализации пакетных операций (addAll(), removeAll(), retainAll() ...). Итак, если окажется, что сама операция изменения размера массива в некоторых случаях может быть менее дорогой (особенно сокращение), я бы исключил многие из тех оптимизаций, которые затем оказываются бесполезными, делая код lot проще в этом процессе.
Итак, прежде чем придерживаться моих идей и экспериментов по оптимизации, я хотел бы знать, нужны ли они вообще.