Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
Crast
70 / 70 / 5
Регистрация: 10.02.2013
Сообщений: 434
1

Структура данных для кэша

26.05.2013, 15:56. Просмотров 456. Ответов 5
Метки нет (Все метки)

Уже мозг себе сломал. Сначала хотел дерево, в котором наиболее используемые элементы сдвигаются в правую часть. Потом понял, что это операции вставки и удаления. Затем был список пропусков, но на деле он не отличается от дерева + постоянное удаление и вставка списка пропусков.
Сейчас думаю сделать связной список, на промежуточные элементы которого указывает массив размером = корень(размер списка). Может кто знает более приятные глазу реализации?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.05.2013, 15:56
Ответы с готовыми решениями:

Хитрая структура данных для быстрых операций
Добрый вечер! Знающие люди, подскажите, пожалуйста, идею для разрешения...

Наиболее подходящая структура данных для дерева
Какая наиболее подходящая структура данных для дерева (не обязательно...

Структура данных
Необходимо создать структуру данных. Эта структура данных - граф. В данном...

Чем отличаются два понятия: "Абстрактный тип данных" и "Структура данных"?
Чем отличаются два понятия: "Абстрактный тип данных" и "Структура данных"?

Структура представления данных, где у родителя могут существовать более двух потомков
Как представить структуру в виде двоичного дерева, где у родителя могут...

5
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
26.05.2013, 18:20 2
Увлекшись своими мыслями Вы забыли сформулировать задачу Если просто "кеш" то почему не hash или std::map сл стандартным LRU?
0
Crast
70 / 70 / 5
Регистрация: 10.02.2013
Сообщений: 434
26.05.2013, 23:13  [ТС] 3
Цитата Сообщение от Igor3D Посмотреть сообщение
Увлекшись своими мыслями Вы забыли сформулировать задачу Если просто "кеш" то почему не hash или std::map сл стандартным LRU?
Нужен алгоритм, по которому определять какие данные сохранять в кэше.
Есть дерево со всеми объектами, в том числе счетчиками. Каждый объект соответствуют кэшируемому элементу (не обязательно значение этого элемента в кэше). Для реального кэша уже есть только ограниченное количество других записей, в которых и сохраняются кэшированные значения.
Нужен алгоритм, который будет быстро перемещать данные внутри ограниченного множества элементов, быстро находить место для кэшируемого значения и вставлять его в это место, убирать из списка наименее используемый элемент при вставке, а запись с кэшируемым значением передавать новому элементу. КЛЮЧ В ТАКОМ ТИПЕ ДАННЫХ БУДЕТ СЧЕТЧИК ОБРАЩЕНИЙ К ЭЛЕМЕНТУ.

Почему не подходят:
а. Дерево
При каждом движении в дереве необходим доступ к корню дерева + список кэшируемых значений придется забивать в него полностью, чтобы определить какой элемент наиболее используем. Все это эквивалентно вставке и удалению элемента в дереве.
Но есть некоторые мысли по увеличению производительности.
б. Список пропусков
Хотя это и связной список, но по принципу нахождения элемента в нем представляет дерево. Поскольку у меня за значения берутся счетчики - нужно удалять элемент, заново вставлять и инициализировать к нему список пропусков, что не фонтан)).

На чем остановился:
Связной список с массивом элементов. Выглядит примерно так:
Массив - 1 3 6 9
Список - 1 2 3 4 5 6 7 8 9
В таком типе данных можно методом бинарного поиска в массиве найти первый элемент который больше, затем вставить в нужное место, и сдвинуть ветку массива на один элемент. Вроде бы самое то по скорости

А теперь вопрос: можно ли сделать все как-либо эффективней?

Добавлено через 40 секунд

Не по теме:

Или не дивлю ли я))

0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
27.05.2013, 11:42 4
Цитата Сообщение от Crast Посмотреть сообщение
А теперь вопрос: можно ли сделать все как-либо эффективней?
Думаю да если поместить часть данных в сам элемент.

Цитата Сообщение от Crast Посмотреть сообщение
КЛЮЧ В ТАКОМ ТИПЕ ДАННЫХ БУДЕТ СЧЕТЧИК ОБРАЩЕНИЙ К ЭЛЕМЕНТУ.
Это спорно, элементы с большим числом обращений возможно никогда не будут вытеснены, хотя уже давно не используются. Не лучше ли начать "от печки" - чем не устраивает стандартный LRU ?
0
Crast
70 / 70 / 5
Регистрация: 10.02.2013
Сообщений: 434
27.05.2013, 12:31  [ТС] 5
Цитата Сообщение от Igor3D Посмотреть сообщение
Не лучше ли начать "от печки" - чем не устраивает стандартный LRU ?
Можно по подробней - какой тип данных это стандартный LRU. Если такого нет, то где можно почитать про организацию на типе данных из стандартной библиотеке? Boost не подходит.
Цитата Сообщение от Igor3D Посмотреть сообщение
Это спорно, элементы с большим числом обращений возможно никогда не будут вытеснены, хотя уже давно не используются.
Раз в некоторый промежуток времени счетчики обнуляются или каким-либо другим образом сматываются, потому это не проблема.
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
27.05.2013, 13:18 6
Цитата Сообщение от Crast Посмотреть сообщение
Можно по подробней - какой тип данных это стандартный LRU. Если такого нет, то где можно почитать про организацию на типе данных из стандартной библиотеке? Boost не подходит.
Просто двусвязный список, указатели на предыдущий и последующий хранятся в самом элементе. При обращении элемент преносится в голову списка. Если места в кеше не хватает - отрубаем хвост списка.

Эту схему можно изменить для "числа обращений"
1
27.05.2013, 13:18
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.05.2013, 13:18

Логика и структура программы...для детей и блондинок
Товарищи! Подскажите, пожалуйста, как работает приложение Windows с...

Как сделать так, чтобы при нажатии 'Back' в браузере не показывалась предыдущая страница из кэша браузера?
Как сделать так, чтобы при нажатии 'Back' в браузере не показывалась предыдущая...

Алгоритм и структура для поиска большого количества строк в другом массиве строк
Здравствуйте! Я решаю следующую задачу: Есть файл со "строками" (средняя...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru