Да, спасибо, очепятка)

Можно представить себе так: программа — это труба, в которую втекает STDIN, а вытекает STDOUT.

Скорее труба с разветвлением на конце: stdin и stderr

Я не понимаю, как можно работать с амортизированной сложностью в данной ситуации. Если у Вас есть какие-то предложения, поделитесь, пожалуйста. Возможно, я не до конца понимаю смысл этого метода.

 

А для чего Вы используете md5 хеш сумму? Почему бы не воспользоваться готовым методом Object.hashCode()?

Согласен. Но я опять же мыслю в контексте текущей проблемы, где вставка идёт именно в середину списка. И, кстати, усреднённая точка вставки для общего случая будет с=(1+2+...+n)/n=n/2, опять же середина списка.

Спасибо, не знал. Как раз для моего случая!

Поясните, пожалуйста, почему при сдвиге кэш используется больше? За счёт того, что мы двигаемся линейно по памяти, а не прыгаем ко куче?

Да, эту проблему я тоже учитывал в тесте, вызывая сборщик мусора и паузу для его работы после каждой новой инициализации списков, но какого-то видимого изменения статистики я не увидел.

Есть следующий вопрос. Правильно ли я понимаю следующее. Сложности, которыми вы оперируете, находятся в разных координатных системах. Т.е., если у ArrayList и LinkedList параметр O(1) равен разному физическому времени, поэтому одинаковые сложности O(n) — не означают, что время вставки будет одинаково. Оно может ощутимо различаться.

Да, скорость выполнение операций — разная, а сложность — одна. Это можно сравнить с испытанием одного алгоритма на машинах разной производительности.

А если мы пробегаем не весь linkedList, а как максимум его половину — сложность точно будет O(n)? Может, O(n/2) или O(n)/2? Мы же пробегаем половину.

Кстати, в ArrayList мы тоже смещаем только половину массива.

Вообще, вопрос был с подвохом. ИМХО, если он звучал именно так, как вы написали — вы вообще не по той ветке пошли. Надо было сказать, что вставка по индексу и вставка по итератору отличаются.

Да, тут согласен, про вставку по итератору я тогда не догадался сказать.

Да, согласен, практического интереса нет. Мне было интересно ответить на конкретно поставленный теоретический вопрос.

Вопрос на собеседовании подразумевал разовую вставку именно в самую середину, поэтому я не могу воспользоваться ListIterator. А в цикле я вставлял данные, пытаясь показать, что многократное увеличение размера массива у ArrayList снижает производительность относительно LinkedList.

Самое простое, понятное и наглядное применение — объединение в группу всех устройств одного пользователя. Когда нам нужно отправить сообщение, нам надо его отправить прежде всего пользователю. И дабы не вспоминать идентификаторы всех устройств пользователя (registration_id), мы используем только идентификатор пользователя (notification_key), к которому уже привязаны на стороне GCM сервера идентификаторы всех его устройств.

По поводу Deprecated: не обратил внимание, что устаревшим помечен notification_key только для HTTP, но не для XMPP