V
Почему CopyOnWriteArrayList add O(n), Это ошибка или я что то не понимаю)?
Size: a a a
2020 December 09
g
нет не ошибка, ответ в названии
g
когда ты добавляешь элемент, он тебе создает новую копию твоего листа
V
ну да, но это же не зависит от размера массива
V
это какое то константное количество операций - заблокировать - скопировать - изменить - присвоить копию в переменную
DS
ну да, но это же не зависит от размера массива
Ну есть, наверно, разница, скопировать массив на 10 элементов, или на миллион элементов
V
ну я понял что вы имеете ввиду, но как то не логично для меня это.
V
операция то одна "скопировать массив" и она не выполнится больше или меньше раз, в зависимости от размера
g
операция то одна "скопировать массив" и она не выполнится больше или меньше раз, в зависимости от размера
окей, а операция удалить из аррей листа, почему тогда не константная?
DS
операция то одна "скопировать массив" и она не выполнится больше или меньше раз, в зависимости от размера
Ну это какая-то слишком большая операция ))) Она сама состоит из гораздо более маленьких операций, типа "скопировать элемент 0", "скопировать элемент 1" и т.д.
V
Ну это какая-то слишком большая операция ))) Она сама состоит из гораздо более маленьких операций, типа "скопировать элемент 0", "скопировать элемент 1" и т.д.
не, там же System.arrayCopy() операция супермена
g
не, там же System.arrayCopy() операция супермена
хм, есть какая-то магия в этой операции?
DS
не, там же System.arrayCopy() операция супермена
Ну внутри-то ей один фиг копировать элементы приходится. И чем больше элементов, тем дольше она работать будет.
V
хм, есть какая-то магия в этой операции?
да, она native. Вроде как сильно оптимизирована
F
не, там же System.arrayCopy() операция супермена
Там просто кусок памяти копируется?
g
да, она native. Вроде как сильно оптимизирована
так-с, скажи, что для тебя означает O нотация?
V
так-с, скажи, что для тебя означает O нотация?
Количесво операций, которое требуется для выполнения метода
V
O(n) - сколько элементов , столько операций. O(1) - всегда одно и то же количесво
F
O(n) - сколько элементов , столько операций. O(1) - всегда одно и то же количесво
Элементов чего
V
Элементов чего
размер коллекции