Re_вольвер: ( гpаф в линейкy)

From

Oleg I. Khovayko ()

To

Juriy Tikhomirov

Date

2003-01-07T00:17:08Z

Area

RU.ALGORITHMS

From: "Oleg I. Khovayko" <olegh@ncbi.nlm.nih.gov>

Juriy Tikhomirov wrote:
>  JT>> кста, поясните особый смысл циклических списков.
>  KA> А что в них такого особого? Беpем линейный список и конец связываем с
>  KA> началом :)
> 
> дык, это ясно. не ясно, нахpена это нyжно.
> 

Ну, причины бывают разные.
Например, одна из последних задач, где я применял цикл. список,
была разработка подсистемы кеширования.

Каков простейший алгоритм кеширования? Стопка книг!
То есть, допустим, есть у тебя стопка книг. Ты произвольно берешь
книгу из стопки. Почитал - и положил наверх.
Самые часто используемые книги в ней будут всегда близко к вершине.

В моей системе размер стопки ограничен. Когда стопка заполнена до 
предела, и пришла новая книга, то надо выкинуть самую нижнюю книгу
из стопки, а новую книгу положить наверх, сдвинув при этом всю стопку вниз.

При этом просто напрашивается идея зациклить стопку
(тут возникает аналогия с барабаном револьвера).
То есть вместо удаления нижней книги (записи в памяти),
сдвига стопки, создания новой книги (записи) - я просто
откатываю указатель на вершину стопки на шаг назад,
и модифицирую запись, указаную этим указателем. 

Таким образом, эффективно удаляется старая запись в хвосте 
"стопки", и добавляется новая в голову.

При этом не делается освобождения/резервирования памяти,
то есть же узел рециклится - как будто бы в книге стираем старое 
содержимое, а вместо него вписываем новое.

Таким образом, буфер кеша представляет собою револьверную 
(от английского revolving) структуру, основаную на кольцевом списке.
И при добавлении новой записи взамен старой, я фигурально выражаясь, 
проворачиваю барабан в револьвере, и меняю патрон.

Ну там, в реальной работающей подсистеме кеширования, 
в револьвере не один барабан, а 4096, вход в которые идет через 
хеш-таблицу. Каждый барабан содержит примерно 64 патрона.
Работает на ура.

-- 
#include <best/regards.hpp>
Oleg I. KHOVAYKO  
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
 * Origin: National Center for Biotechnology Information (2:5020/400)