На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
Модераторы: Qraizer, Hsilgos
  
> кэширование файловых операций , Си (С89 или С90 не знаю, но точно кто-то из них!)
    Всем хай! Сходу к делу!
    Допустим, есть следующее описание сущности "Автомобиль":
    ExpandedWrap disabled
      typedef struct
      {
          char mark[ 30 ];
          double price;
          // и еще произвольное кол-во полей
      } Car;


    Есть ДВОИЧНЫЙ файл data.bin, хранящий информацию о 1000 машинах. Этот файл был создан независимой утилитой.
    Есть хеш-таблица (на цепочках). Есть хеш-функция, принимающая на вход "машину" и возвращающая номер слота хеш-таблицы. Все как обычно.
    Есть требование: хранить информацию о машинах в дин.памяти запрещено, но в элементах хеш-таблицы можно хранить указатели на соответствующие машины в бинарном файле. Здесь в целом проблем нет и все понятно + понятно как реализовать. Достаточно один раз прочитать данные из data.bin и заполнить элементы хеш-таблицы.
    Пусть это называется задание №1.
    ------------------------------------
    Теперь о проблеме.
    В общем надо сделать то же самое, что в задании №1, но применяя буферизацию файловых операций (читать и записывать по несколько записей(машин) одновременно) и кэшировать записи.
    Честно говоря - впал в ступор, хм..Что такое кэширование данных в целом понятно (в гугле не забанен), но как это все ГРАМОТНО применить к этой задаче...

    Кратко опишу некие мысли (возможно, полный бред). Например, делаем поиск ВСЕХ авто по марке "Jaguar". Таких машин 27 штук в базе данных (в бинарном файле). Поиск идет через хеш-таблицу и за время О(1) (хотя это при идеальной хеш-таблице) эти машины можно отбирать. И надо запомнить эти ягуары в памяти получается, чтобы при последующем поиске сразу их оттуда доставать без обращения к БД. Но, ведь нет гарантий, что эти машины в принципе потребуются при следующем запросе)
    В общем не выкупаю, что тут надо сделать. :wall:

    Подскажите, как быть-то, буду ооооооочень признателен?

    p.s. если есть возможность, то прошу тему продублировать в разделе "Алгоритмы", т к здесь и алгоритмы вроде замешаны, а с др.стороны все должно быть на чистом Си
    Сообщение отредактировано: FasterHarder -
      Не совсем понятно, с чем проблема (и с чем проблем нет).

      Проблема в том, что "выброс" пачки редкоиспользуемых записей может "отравить" кэш? Не знаю, как это обычно решается, но очевидный вариант - разделить кэш на две зоны: в одну пишем элементы, считанные из самого кэша, во вторую пишем элементы, считанные с диска. Если какой-то элемент переносится из второй зоны в первую, то самый "старый" элемент из первой зоны вытесняется во вторую.

      Реализовать это можно в виде двух упорядоченных списков элементов, в начале - самый "свежий" (последний считанный из кэша/с диска), в конце - самый "старый". Работать будет примерно так:
      ExpandedWrap disabled
        элемент кэш (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
        AVA12, вроде твою идею понял, спс
        0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
        0 пользователей:


        Рейтинг@Mail.ru
        [ Script execution time: 0,0238 ]   [ 18 queries used ]   [ Generated: 19.03.24, 06:17 GMT ]