История IT-технологий сегодня — 28 ноября
ℹ️ Кто родился в этот день
Кристиан Керстинг (родился 28 ноября 1973 года в Куксхафене, Германия) — немецкий учёный в области ИИ и машинного обучения, профессор, возглавляющий лабораторию по ИИ и машинному обучению (AIML) в Darmstadt; значимые публикации в probabilistic inductive logic programming.
🌐 Знаковые события
1964 — к Марсу запущена американская автоматическая станция «Маринер-4».
#Biography #Birth_Date #Events #28Ноября
Кристиан Керстинг (родился 28 ноября 1973 года в Куксхафене, Германия) — немецкий учёный в области ИИ и машинного обучения, профессор, возглавляющий лабораторию по ИИ и машинному обучению (AIML) в Darmstadt; значимые публикации в probabilistic inductive logic programming.
1964 — к Марсу запущена американская автоматическая станция «Маринер-4».
#Biography #Birth_Date #Events #28Ноября
Please open Telegram to view this post
VIEW IN TELEGRAM
👍2
Глава 2. List — списки
Метод get
Доступ к элементам по индексу — это базовая операция, которая раскрывает фундаментальные различия в архитектуре различных реализаций List. В то время как некоторые реализации обеспечивают мгновенный доступ к любому элементу, другие требуют последовательного обхода для достижения целевой позиции. Это различие проистекает из компромисса между скоростью доступа, эффективностью модификаций и потреблением памяти, который каждая реализация решает по-своему.
ArrayList: мгновенный доступ через массив
ArrayList реализует список на основе динамического массива, что обеспечивает ему исключительную производительность при операциях доступа по индексу. Внутренняя структура ArrayList построена вокруг массива Object[], который служит непосредственным хранилищем элементов.
Эта архитектура предоставляет несколько ключевых преимуществ для операции get:
Прямая адресация через смещение в памяти
Константное время доступа к любому элементу
Высокая пространственная локальность, благоприятная для кэширования процессора
Минимальные накладные расходы на операцию доступа
Детальный процесс выполнения get(index)
Фаза валидации и проверки границ
Первым и обязательным шагом в выполнении метода get является проверка корректности запрошенного индекса:
Проверка диапазона:
Система убеждается, что указанный индекс находится в пределах от 0 (включительно) до текущего размера списка (исключительно). Эта проверка включает сравнение индекса с полем size ArrayList и при необходимости выброс исключения IndexOutOfBoundsException с информативным сообщением.
Валидация состояния:
Неявно проверяется, что внутренняя структура данных находится в консистентном состоянии и готова к операции чтения.
Фаза непосредственного доступа к элементу
После успешной валидации индекса происходит собственно извлечение элемента:
Вычисление позиции в массиве:
Поскольку ArrayList использует непрерывный блок памяти, позиция элемента вычисляется как прямое смещение в массиве. Для массива elementData и индекса i элемент находится точно в позиции elementData[i].
Извлечение значения:
Происходит чтение ссылки на объект из соответствующей позиции массива. Эта операция компилируется в одну машинную инструкцию доступа к памяти.
Возврат результата:
Найденный объект возвращается вызывающему коду. Если в указанной позиции хранится null, метод возвращает null без дополнительных проверок.
Отсутствие структурных изменений
Важной характеристикой операции get в ArrayList является то, что она не модифицирует внутреннюю структуру данных.
В отличие от операций добавления или удаления, get является read-only операцией, что означает:
Отсутствие необходимости в блокировках для thread-safe доступа (в read-only сценариях)
Нет модификации счетчика изменений (modCount)
Сохранение целостности внутреннего массива
Производительность и оптимизации
Временная сложность
Операция get в ArrayList имеет временную сложность O(1) в худшем случае. Это означает, что время доступа к первому, последнему или любому другому элементу практически идентично и не зависит от размера списка.
Влияние кэширования процессора
Благодаря непрерывному расположению элементов в памяти, ArrayList идеально использует принцип пространственной локальности:
Кэш-линии процессора:
Смежные элементы часто попадают в одну кэш-линию, что делает последовательный доступ чрезвычайно эффективным.
Prefetching:
Современные процессоры могут предсказывать и предзагружать следующие элементы массива, еще больше ускоряя последовательные операции доступа.
Оптимизации на уровне JVM
JIT-компиляция:
HotSpot JVM может агрессивно оптимизировать операции доступа к массиву, включая elimination bounds checking в некоторых сценариях.
Inlining:
Частые вызовы get могут быть inline-ированы, уменьшая overhead вызова метода.
#Java #для_новичков #beginner #List #ArrayList #LinkedList #get
Метод get
Доступ к элементам по индексу — это базовая операция, которая раскрывает фундаментальные различия в архитектуре различных реализаций List. В то время как некоторые реализации обеспечивают мгновенный доступ к любому элементу, другие требуют последовательного обхода для достижения целевой позиции. Это различие проистекает из компромисса между скоростью доступа, эффективностью модификаций и потреблением памяти, который каждая реализация решает по-своему.
ArrayList: мгновенный доступ через массив
ArrayList реализует список на основе динамического массива, что обеспечивает ему исключительную производительность при операциях доступа по индексу. Внутренняя структура ArrayList построена вокруг массива Object[], который служит непосредственным хранилищем элементов.
Эта архитектура предоставляет несколько ключевых преимуществ для операции get:
Прямая адресация через смещение в памяти
Константное время доступа к любому элементу
Высокая пространственная локальность, благоприятная для кэширования процессора
Минимальные накладные расходы на операцию доступа
Детальный процесс выполнения get(index)
Фаза валидации и проверки границ
Первым и обязательным шагом в выполнении метода get является проверка корректности запрошенного индекса:
Проверка диапазона:
Система убеждается, что указанный индекс находится в пределах от 0 (включительно) до текущего размера списка (исключительно). Эта проверка включает сравнение индекса с полем size ArrayList и при необходимости выброс исключения IndexOutOfBoundsException с информативным сообщением.
Валидация состояния:
Неявно проверяется, что внутренняя структура данных находится в консистентном состоянии и готова к операции чтения.
Фаза непосредственного доступа к элементу
После успешной валидации индекса происходит собственно извлечение элемента:
Вычисление позиции в массиве:
Поскольку ArrayList использует непрерывный блок памяти, позиция элемента вычисляется как прямое смещение в массиве. Для массива elementData и индекса i элемент находится точно в позиции elementData[i].
Извлечение значения:
Происходит чтение ссылки на объект из соответствующей позиции массива. Эта операция компилируется в одну машинную инструкцию доступа к памяти.
Возврат результата:
Найденный объект возвращается вызывающему коду. Если в указанной позиции хранится null, метод возвращает null без дополнительных проверок.
Отсутствие структурных изменений
Важной характеристикой операции get в ArrayList является то, что она не модифицирует внутреннюю структуру данных.
В отличие от операций добавления или удаления, get является read-only операцией, что означает:
Отсутствие необходимости в блокировках для thread-safe доступа (в read-only сценариях)
Нет модификации счетчика изменений (modCount)
Сохранение целостности внутреннего массива
Производительность и оптимизации
Временная сложность
Операция get в ArrayList имеет временную сложность O(1) в худшем случае. Это означает, что время доступа к первому, последнему или любому другому элементу практически идентично и не зависит от размера списка.
Влияние кэширования процессора
Благодаря непрерывному расположению элементов в памяти, ArrayList идеально использует принцип пространственной локальности:
Кэш-линии процессора:
Смежные элементы часто попадают в одну кэш-линию, что делает последовательный доступ чрезвычайно эффективным.
Prefetching:
Современные процессоры могут предсказывать и предзагружать следующие элементы массива, еще больше ускоряя последовательные операции доступа.
Оптимизации на уровне JVM
JIT-компиляция:
HotSpot JVM может агрессивно оптимизировать операции доступа к массиву, включая elimination bounds checking в некоторых сценариях.
Inlining:
Частые вызовы get могут быть inline-ированы, уменьшая overhead вызова метода.
#Java #для_новичков #beginner #List #ArrayList #LinkedList #get
LinkedList: последовательный доступ через цепочку узлов
Архитектурные основы связного списка
LinkedList реализует список на основе двусвязного списка, где каждый элемент хранится в отдельном узле, содержащем ссылки на данные, предыдущий и следующий узлы.
Эта архитектура fundamentally меняет механизм доступа к элементам:
Последовательный доступ вместо прямого
Линейная временная сложность доступа по индексу
Отсутствие преимуществ пространственной локальности
Дополнительные затраты на обход цепочки
Структура узла и организация данных
Каждый узел LinkedList содержит три ключевых компонента:
Детальный процесс выполнения get(index)
Фаза валидации и стратегического выбора
Как и в ArrayList, первым шагом является проверка корректности индекса:
Проверка границ:
Убеждаются, что индекс находится в диапазоне [0, size-1].
Выбор стратегии обхода:
В зависимости от положения индекса выбирается оптимальная точка начала обхода:
Если индекс находится в первой половине списка (index < size / 2), обход начинается с головы (head)
Если индекс находится во второй половине, обход начинается с хвоста (tail)
Эта оптимизация уменьшает среднее количество шагов обхода с n/2 до n/4.
Фаза последовательного обхода
После выбора начальной точки начинается процесс пошагового перемещения по цепочке узлов:
Инициализация обхода:
Создается временная переменная-указатель, которая устанавливается на начальный узел (head или tail).
Последовательное перемещение:
Для каждого шага обхода:
Если движение от головы, указатель перемещается к следующему узлу (node.next)
Если движение от хвоста, указатель перемещается к предыдущему узлу (node.prev)
Счетчик текущей позиции обновляется
Достижение целевой позиции:
Процесс продолжается до тех пор, пока текущая позиция не совпадет с запрошенным индексом.
Фаза извлечения и возврата результата
Когда целевой узел найден:
Извлечение элемента:
Из поля item целевого узла извлекается хранимый объект.
Возврат результата:
Объект возвращается вызывающему коду. Как и в ArrayList, если узел содержит null, возвращается null.
Производительность и характеристики доступа
Временная сложность
Операция get в LinkedList имеет временную сложность O(n) в худшем случае, где n — количество элементов в списке. Однако благодаря двунаправленному обходу средняя сложность составляет O(n/4) = O(n).
Зависимость от паттерна доступа
Худший случай:
Доступ к элементу в середине большого списка требует обхода примерно n/2 узлов.
Лучший случай:
Доступ к первому или последнему элементу требует всего одного шага.
Средний случай:
При равномерном распределении запросов среднее количество шагов составляет n/4.
Влияние на производительность
Отсутствие кэширования:
Из-за разрозненного расположения узлов в памяти отсутствуют преимущества кэширования процессора.
Overhead обхода:
Каждый шаг обхода требует разыменования ссылки и проверки условий, что создает дополнительную нагрузку.
#Java #для_новичков #beginner #List #ArrayList #LinkedList #get
Архитектурные основы связного списка
LinkedList реализует список на основе двусвязного списка, где каждый элемент хранится в отдельном узле, содержащем ссылки на данные, предыдущий и следующий узлы.
Эта архитектура fundamentally меняет механизм доступа к элементам:
Последовательный доступ вместо прямого
Линейная временная сложность доступа по индексу
Отсутствие преимуществ пространственной локальности
Дополнительные затраты на обход цепочки
Структура узла и организация данных
Каждый узел LinkedList содержит три ключевых компонента:
Node {
E item; // хранимый элемент
Node<E> next; // ссылка на следующий узел
Node<E> prev; // ссылка на предыдущий узел
}
Список поддерживает ссылки на первый (head) и последний (tail) узлы, а также счетчик размера.Детальный процесс выполнения get(index)
Фаза валидации и стратегического выбора
Как и в ArrayList, первым шагом является проверка корректности индекса:
Проверка границ:
Убеждаются, что индекс находится в диапазоне [0, size-1].
Выбор стратегии обхода:
В зависимости от положения индекса выбирается оптимальная точка начала обхода:
Если индекс находится в первой половине списка (index < size / 2), обход начинается с головы (head)
Если индекс находится во второй половине, обход начинается с хвоста (tail)
Эта оптимизация уменьшает среднее количество шагов обхода с n/2 до n/4.
Фаза последовательного обхода
После выбора начальной точки начинается процесс пошагового перемещения по цепочке узлов:
Инициализация обхода:
Создается временная переменная-указатель, которая устанавливается на начальный узел (head или tail).
Последовательное перемещение:
Для каждого шага обхода:
Если движение от головы, указатель перемещается к следующему узлу (node.next)
Если движение от хвоста, указатель перемещается к предыдущему узлу (node.prev)
Счетчик текущей позиции обновляется
Достижение целевой позиции:
Процесс продолжается до тех пор, пока текущая позиция не совпадет с запрошенным индексом.
Фаза извлечения и возврата результата
Когда целевой узел найден:
Извлечение элемента:
Из поля item целевого узла извлекается хранимый объект.
Возврат результата:
Объект возвращается вызывающему коду. Как и в ArrayList, если узел содержит null, возвращается null.
Производительность и характеристики доступа
Временная сложность
Операция get в LinkedList имеет временную сложность O(n) в худшем случае, где n — количество элементов в списке. Однако благодаря двунаправленному обходу средняя сложность составляет O(n/4) = O(n).
Зависимость от паттерна доступа
Худший случай:
Доступ к элементу в середине большого списка требует обхода примерно n/2 узлов.
Лучший случай:
Доступ к первому или последнему элементу требует всего одного шага.
Средний случай:
При равномерном распределении запросов среднее количество шагов составляет n/4.
Влияние на производительность
Отсутствие кэширования:
Из-за разрозненного расположения узлов в памяти отсутствуют преимущества кэширования процессора.
Overhead обхода:
Каждый шаг обхода требует разыменования ссылки и проверки условий, что создает дополнительную нагрузку.
#Java #для_новичков #beginner #List #ArrayList #LinkedList #get
Сравнительный анализ производительности
Количественные характеристики
Время доступа:
ArrayList: 5-10 наносекунд на операцию (не зависит от размера)
LinkedList: 10-50 наносекунд × количество пройденных узлов
Потребление памяти:
ArrayList: ~4 байта на элемент (в плотно заполненном массиве)
LinkedList: ~24-32 байта на элемент (затраты на узел)
Качественные различия
Пространственная локальность:
ArrayList: Отличная — элементы расположены непрерывно
LinkedList: Плохая — элементы разбросаны по куче
Масштабируемость:
ArrayList: Идеальная — постоянное время независимо от размера
LinkedList: Линейная деградация — время растет пропорционально размеру
Специализированные реализации List
CopyOnWriteArrayList
Механизм доступа:
Использует snapshot массив, что обеспечивает thread-safe доступ без блокировок:
Операция get просто обращается к текущему snapshot массива
Отсутствие блокировок и contention между читателями
Гарантированная consistency во время итерации
Производительность:
Сопоставима с ArrayList для операций чтения, но с дополнительным уровнем indirection.
Vector
Устаревший synchronized доступ:
Все операции, включая get, синхронизированы, что создает излишний overhead в single-threaded сценариях.
Многопоточные аспекты доступа
Потокобезопасность операций чтения
Несинхронизированные реализации:
ArrayList и LinkedList не гарантируют корректность при concurrent модификациях:
Возможность чтения устаревших данных
Риск исключений при структурных изменениях во время доступа
Отсутствие happens-before отношений
Thread-safe альтернативы:
CopyOnWriteArrayList: Идеален для read-heavy workloads
Collections.synchronizedList(): Добавляет синхронизацию к стандартным реализациям
Vector: Устаревшая синхронизированная реализация
Практические рекомендации
Критерии выбора реализации
Выбор ArrayList когда:
Преобладает случайный доступ по индексу
Частые операции получения элементов
Известен или может быть оценен конечный размер списка
Критически важна производительность операций чтени
Память является ограниченным ресурсом
Выбор LinkedList когда:
Преобладают операции вставки/удаления в начала/конца списка
Основной паттерн доступа — последовательная итерация
Размер списка сильно варьируется
Операции доступа по индексу редки или предсказуемы
Влияние современных аппаратных архитектур
Иерархия памяти и кэширование
ArrayList:
Отличное использование L1/L2/L3 кэшей
Эффективный prefetching
Минимальные cache misses
LinkedList:
Частые cache misses из-за random access к памяти
Неэффективное использование prefetcher'а
Высокий penalty при промахах кэша
Влияние на реальную производительность
Разрыв в производительности между ArrayList и LinkedList для операций get может достигать 50-100 раз для больших списков и случайного доступа, что делает правильный выбор реализации критически важным для производительности приложения.
#Java #для_новичков #beginner #List #ArrayList #LinkedList #get
Количественные характеристики
Время доступа:
ArrayList: 5-10 наносекунд на операцию (не зависит от размера)
LinkedList: 10-50 наносекунд × количество пройденных узлов
Потребление памяти:
ArrayList: ~4 байта на элемент (в плотно заполненном массиве)
LinkedList: ~24-32 байта на элемент (затраты на узел)
Качественные различия
Пространственная локальность:
ArrayList: Отличная — элементы расположены непрерывно
LinkedList: Плохая — элементы разбросаны по куче
Масштабируемость:
ArrayList: Идеальная — постоянное время независимо от размера
LinkedList: Линейная деградация — время растет пропорционально размеру
Специализированные реализации List
CopyOnWriteArrayList
Механизм доступа:
Использует snapshot массив, что обеспечивает thread-safe доступ без блокировок:
Операция get просто обращается к текущему snapshot массива
Отсутствие блокировок и contention между читателями
Гарантированная consistency во время итерации
Производительность:
Сопоставима с ArrayList для операций чтения, но с дополнительным уровнем indirection.
Vector
Устаревший synchronized доступ:
Все операции, включая get, синхронизированы, что создает излишний overhead в single-threaded сценариях.
Многопоточные аспекты доступа
Потокобезопасность операций чтения
Несинхронизированные реализации:
ArrayList и LinkedList не гарантируют корректность при concurrent модификациях:
Возможность чтения устаревших данных
Риск исключений при структурных изменениях во время доступа
Отсутствие happens-before отношений
Thread-safe альтернативы:
CopyOnWriteArrayList: Идеален для read-heavy workloads
Collections.synchronizedList(): Добавляет синхронизацию к стандартным реализациям
Vector: Устаревшая синхронизированная реализация
Практические рекомендации
Критерии выбора реализации
Выбор ArrayList когда:
Преобладает случайный доступ по индексу
Частые операции получения элементов
Известен или может быть оценен конечный размер списка
Критически важна производительность операций чтени
Память является ограниченным ресурсом
Выбор LinkedList когда:
Преобладают операции вставки/удаления в начала/конца списка
Основной паттерн доступа — последовательная итерация
Размер списка сильно варьируется
Операции доступа по индексу редки или предсказуемы
Влияние современных аппаратных архитектур
Иерархия памяти и кэширование
ArrayList:
Отличное использование L1/L2/L3 кэшей
Эффективный prefetching
Минимальные cache misses
LinkedList:
Частые cache misses из-за random access к памяти
Неэффективное использование prefetcher'а
Высокий penalty при промахах кэша
Влияние на реальную производительность
Разрыв в производительности между ArrayList и LinkedList для операций get может достигать 50-100 раз для больших списков и случайного доступа, что делает правильный выбор реализации критически важным для производительности приложения.
#Java #для_новичков #beginner #List #ArrayList #LinkedList #get
Что выведет код?
#Tasks
import java.util.ArrayList;
import java.util.List;
public class Task281125 {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
List<Integer> subList = list.subList(1, 3);
list.add(4);
System.out.println(subList.get(0));
System.out.println(subList.get(1));
}
}
#Tasks