В предыдущих разделах мы изучили понятия «связный список» и «пространственная и временная сложность». время», чтобы разработать очень интересную стратегию устранения кеша: алгоритм устранения кеша LRU.
Концепция кругового связанного списка
Как показано на рисунке выше: указатель хвостового узла односвязного списка указывает на пустой адрес, указывая, что это последний узел. Указатель хвостового узла кольцевого связанного списка указывает на головной узел связанного списка.
Следовательно, циклический связанный список — это особый вид односвязного списка. ** Единственная разница между ним и односвязным списком — хвостовой узел. Он соединен встык, как кольцо, поэтому его называют «круговой связанный список».
Особенности кругового связанного списка
Преимущество кругового связанного списка по сравнению с односвязным списком состоит в том, что удобнее переходить от хвоста к началу цепочки.Когда обрабатываемые данные имеют характеристики кольцевой структуры, удобно использовать круговой связанный список.
Концепция двусвязного списка
Двусвязный список также называется двусвязным списком.Это тип связанного списка.Направление его связи является двунаправленным.Каждый из его узлов данных содержит два указателя, которые указывают на прямого преемника и прямого предшественника соответственно.
Поэтому, начиная с любого узла в двусвязном списке, легко получить доступ к его узлам-предшественникам и узлам-последователям.
В структуре данных двусвязного списка есть два важных параметра:preиnext.
-
preуказывает на предыдущую структуру данных -
nextуказать на следующую структуру данных
Особенности двусвязного списка.
-
По сравнению с односвязным списком, двусвязному списку требуется на один указатель больше, чтобы указать на предшествующий узел, поэтому, если сохраняется тот же объем данных, двусвязный список занимает больше места в памяти, чем односвязный список.
-
Вставка и удаление двусвязного списка должны одновременно поддерживать два указателя next и prev.
-
Доступ к элементам в двусвязном списке должен осуществляться последовательно и поддерживает двунаправленный обход, который является основой гибкости операций с двусвязным списком.
Основные операции двусвязного списка
1. Добавьте элементы.
По сравнению с односвязным списком двусвязный список может быть выполнен с временной сложностью O (1), в то время как односвязный список требует временной сложности O (n).
Добавленные элементы двусвязного списка включают вставку начала и конца.
**Метод вставки начала:** Левая часть связанного списка называется началом связанного списка, а правая часть называется хвостом связанного списка. Метод вставки заголовка заключается в фиксации правой стороны, и каждый новый элемент добавляется в левый заголовок.
**Метод вставки хвоста: **Левая часть связанного списка называется головой связанного списка, а правая часть называется хвостом связанного списка. Метод вставки хвоста заключается в фиксации левой стороны, и каждое новое добавление находится в конце правой части связанного списка.
2. Элемент запроса
Гибкость двусвязного списка заключается в том, чтоЗная структуру элементов в связанном списке, вы можете начать обход влево или вправо, чтобы найти нужную структуру элементов.. Следовательно, для упорядоченного связанного списка эффективность запроса по значению для двусвязного списка выше, чем для односвязного списка. Потому что мы можем записать позицию p последнего поиска, и каждый раз, когда мы запрашиваем, мы решаем, следует ли искать вперед или назад, в соответствии с отношением между искомым значением и p, поэтому в среднем требуется только половина данных. быть обысканным.
3. Удалить элементы
В реальной разработке программного обеспечения удаление данных из связанного списка представляет собой не что иное, как следующие две ситуации:
-
Удалить узлы со «значением, равным заданному значению» в узлах
-
удаляет узел, на который указывает данный указатель
Для двусвязного списка узлы в двусвязном списке сохранили указатель узла-предшественника, и его не нужно обходить, как односвязный список, при удалении. Следовательно, во втором случае операция удаления односвязного списка требует временной сложности O(n), а двусвязный список требует временной сложности O(1).
двусвязный список
Как показано на рисунке, концепция двусвязного списка хорошо понятна: комбинация «двусвязный список» + «циклический связанный список».
Политика удаления кеша
Кэширование — это технология повышения производительности чтения данных, которая широко используется при проектировании аппаратного обеспечения и разработке программного обеспечения, например, общий кеш процессора, кеш базы данных, кеш браузера и так далее.
Размер кеша ограничен. Когда кеш заполнен, какие данные нужно удалить, а какие оставить? Для этого требуется стратегия ликвидации кеша. Существует три общих стратегии: FIFO (первым пришел, первым обслужен), LFU (наименее часто используемый) и LRU (наименее недавно использованный).
Стратегия кэширования LRU широко используется в сторонних фреймворках на разных языках. Программист Сяо Ву вступил в контакт с «Mybatis» в Java, «YYCache» и «Lottie» в iOS и т. д.
Алгоритм устранения кеша LRU
LRU — это сокращение от наименее использовавшейся стратегии, которая заключается в удалении данных в соответствии с историческими записями доступа к данным.
Связанный список реализует LRU
Все позиции кеша связаны с двусвязным списком.При попадании в позицию позиция настраивается на позицию заголовка связанного списка путем корректировки точки связанного списка, а вновь добавленный кеш добавляется напрямую в заголовок связанного списка.
Таким образом, после многократного выполнения операций кэширования последнее попадание будет перемещено в начало связанного списка, а неиспользованные будут перемещены в конец связанного списка, а конец списка. связанный список будет указывать на последний использованный кэш.
Когда содержимое необходимо заменить, последняя позиция связанного списка является позицией с наименьшим количеством совпадений, и нам нужно удалить только последнюю часть связанного списка.
Связанный список реализует демонстрацию анимации LRU
- Если данные ранее кэшировались в связанном списке, узел, соответствующий данным, получается путем обхода, удаляется из исходной позиции, а затем вставляется в заголовок связанного списка.
- Если этих данных нет в связанном списке кеша, его можно разделить на два случая:
- Если к этому моменту кэш еще не заполнен, вставьте этот узел прямо в начало связанного списка;
- Если в это время кеш заполнен, хвостовой узел связанного списка удаляется, а новый узел данных вставляется в начало связанного списка.
Из анимации видно, что если пространство кеша достаточно велико, будет храниться достаточно данных, и вероятность попадания данных в кеш будет выше, что улучшит скорость выполнения кода. ЭтоИдея дизайна пространства для времени.
Для разработки программы временная сложность и пространственная сложность могут быть преобразованы друг в друга. Проще говоря, это:
-
Для выполнения медленных программ их можно оптимизировать за счет потребления памяти (то есть создания новых структур данных);
-
Программы, которые потребляют память, могут уменьшить потребление памяти, потребляя время.
На обработку анимации и движущихся картинок этой статьи ушло много времени и сил.
Удачного обучения :)