Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[34.236.152.203] |
|
Сообщ.
#1
,
|
|
|
Всем хай! Сходу к делу!
Допустим, есть следующее описание сущности "Автомобиль": typedef struct { char mark[ 30 ]; double price; // и еще произвольное кол-во полей } Car; Есть ДВОИЧНЫЙ файл data.bin, хранящий информацию о 1000 машинах. Этот файл был создан независимой утилитой. Есть хеш-таблица (на цепочках). Есть хеш-функция, принимающая на вход "машину" и возвращающая номер слота хеш-таблицы. Все как обычно. Есть требование: хранить информацию о машинах в дин.памяти запрещено, но в элементах хеш-таблицы можно хранить указатели на соответствующие машины в бинарном файле. Здесь в целом проблем нет и все понятно + понятно как реализовать. Достаточно один раз прочитать данные из data.bin и заполнить элементы хеш-таблицы. Пусть это называется задание №1. ------------------------------------ Теперь о проблеме. В общем надо сделать то же самое, что в задании №1, но применяя буферизацию файловых операций (читать и записывать по несколько записей(машин) одновременно) и кэшировать записи. Честно говоря - впал в ступор, хм..Что такое кэширование данных в целом понятно (в гугле не забанен), но как это все ГРАМОТНО применить к этой задаче... Кратко опишу некие мысли (возможно, полный бред). Например, делаем поиск ВСЕХ авто по марке "Jaguar". Таких машин 27 штук в базе данных (в бинарном файле). Поиск идет через хеш-таблицу и за время О(1) (хотя это при идеальной хеш-таблице) эти машины можно отбирать. И надо запомнить эти ягуары в памяти получается, чтобы при последующем поиске сразу их оттуда доставать без обращения к БД. Но, ведь нет гарантий, что эти машины в принципе потребуются при следующем запросе) В общем не выкупаю, что тут надо сделать. Подскажите, как быть-то, буду ооооооочень признателен? p.s. если есть возможность, то прошу тему продублировать в разделе "Алгоритмы", т к здесь и алгоритмы вроде замешаны, а с др.стороны все должно быть на чистом Си |
Сообщ.
#2
,
|
|
|
Не совсем понятно, с чем проблема (и с чем проблем нет).
Проблема в том, что "выброс" пачки редкоиспользуемых записей может "отравить" кэш? Не знаю, как это обычно решается, но очевидный вариант - разделить кэш на две зоны: в одну пишем элементы, считанные из самого кэша, во вторую пишем элементы, считанные с диска. Если какой-то элемент переносится из второй зоны в первую, то самый "старый" элемент из первой зоны вытесняется во вторую. Реализовать это можно в виде двух упорядоченных списков элементов, в начале - самый "свежий" (последний считанный из кэша/с диска), в конце - самый "старый". Работать будет примерно так: элемент кэш (1з|2з) abc|defgh c -> cab|defgh d -> dca|befgh h -> hdc|abefg x -> hdc|xabef y -> hdc|yxabe z -> hdc|zyxab x -> xhd|czyab |
Сообщ.
#3
,
|
|
|
AVA12, вроде твою идею понял, спс
|