ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Oleg I. Khovayko                     2:5020/400     07 Jan 2003  01:17:08
 To : Juriy Tikhomirov
 Subject : Re_вольвер: (  гpаф в линейкy)
 -------------------------------------------------------------------------------- 
 

 Juriy Tikhomirov wrote:
 
 >  JT>> кста, поясните особый смысл циклических списков.
 >  KA> А что в них такого особого? Беpем линейный список и конец связываем с
 >  KA> началом :)
 > 
 > дык, это ясно. не ясно, нахpена это нyжно.
 > 
 
 Hу, причины бывают разные.
 Hапример, одна из последних задач, где я применял цикл. список,
 была разработка подсистемы кеширования.
 
 Каков простейший алгоритм кеширования? Стопка книг!
 То есть, допустим, есть у тебя стопка книг. Ты произвольно берешь
 книгу из стопки. Почитал - и положил наверх.
 Самые часто используемые книги в ней будут всегда близко к вершине.
 
 В моей системе размер стопки ограничен. Когда стопка заполнена до 
 предела, и пришла новая книга, то надо выкинуть самую нижнюю книгу
 из стопки, а новую книгу положить наверх, сдвинув при этом всю стопку вниз.
 
 При этом просто напрашивается идея зациклить стопку
 (тут возникает аналогия с барабаном револьвера).
 То есть вместо удаления нижней книги (записи в памяти),
 сдвига стопки, создания новой книги (записи) - я просто
 откатываю указатель на вершину стопки на шаг назад,
 и модифицирую запись, указаную этим указателем. 
 
 Таким образом, эффективно удаляется старая запись в хвосте 
 "стопки", и добавляется новая в голову.
 
 При этом не делается освобождения/резервирования памяти,
 то есть же узел рециклится - как будто бы в книге стираем старое 
 содержимое, а вместо него вписываем новое.
 
 Таким образом, буфер кеша представляет собою револьверную 
 (от английского revolving) структуру, основаную на кольцевом списке.
 И при добавлении новой записи взамен старой, я фигурально выражаясь, 
 проворачиваю барабан в револьвере, и меняю патрон.
 
 Hу там, в реальной работающей подсистеме кеширования, 
 в револьвере не один барабан, а 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)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    гpаф в линейкy   Juriy Tikhomirov   05 Jan 2003 02:51:08   гpаф в линейкy   Konstantin Azarov   05 Jan 2003 04:23:23   гpаф в линейкy   Juriy Tikhomirov   06 Jan 2003 01:56:22   Re_вольвер: ( гpаф в линейкy)   Oleg I. Khovayko   07 Jan 2003 01:17:08