Эффективный кеш в Delphi

Question

Я создаю кеш, который будет содержать записи в Delphi 2007.

Каждая запись содержит строку, 2 даты и значение.

Type MyRecord = Record
    Location : String;
    Date1 : TDateTime;
    Date2 : TDateTime;
    Value : Double;
End;

Нет никаких гарантий относительно того, каким будет максимальный размер кэша.

Весьма вероятно, что в Location будет несколько записей на разные даты
Здесь всего 13 локаций.

Кэш должен быть доступен для поиска и находиться в критическом месте.

Я думал о создании двумерного массива для этой структуры с отсортированным списком строк в качестве индекса. Поэтому при поиске я бы получил доступ к списку строк, чтобы найти нужный мне индекс в массиве с парами имя-значение. (Местоположение = Индекс) Затем мне нужно было бы перебрать элементы для каждого местоположения, чтобы увидеть, находится ли значение в кэше, совпадающее и с Date1, и с Date2. Если значение не находится в кеше, мне нужно пойти и получить его из базы данных и добавить его в кеш.

что-то вроде

Type MyRecord = Record
    Date1 : TDateTime;
    Date2 : TDateTime;
    Value : Double;
End;
...
Cache: Array[1..13] of Array of MyRecord
Locations: TStringList;

как местоположение будет в списке строк.

Будет ли это эффективная структура для кэширования?

Answer 1

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

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

Если бы я реализовал что-то подобное, я бы взял TList с указателями на записи. Список, который будет отсортирован с помощью TList.Sort, который я даю процедуру, которая сортирует список в соответствии с данными, содержащимися в записях. Сортировка будет производиться на полях с наибольшей «селективностью», затем на полях со второй по селективности и т. Д.

Если вы хотите найти запись, вы выполняете двоичный поиск в списке и получаете значение, если оно не существует, вы получаете его из базы данных и добавляете его в кеш.

Конечно, все это было бы красиво обернуто в классе, который заботится об этом и о проблемах выделения памяти.

Хеш-карта также возможна, но вы должны выполнить тесты, чтобы увидеть, что быстрее.

Answer 2

Ваша идея кажется здравой и должна работать эффективно.По сути, вы будете реализовывать простую таблицу базы данных с индексом.Он отделяет информацию индекса от данных, поэтому стоимость обновления индекса «мала» по сравнению с перемещением данных в отсортированной структуре.

Еще одна возможность - использовать базу данных в памяти.Есть несколько доступных для Delphi.Они многое сделают для вас и, возможно, обеспечат большую гибкость.

Answer 3

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

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