Правильная структура данных, чтобы использовать для (этого конкретного) устаревшего кэша?

Question

Мне нужно читать из набора данных, который очень большой, сильно взаимосвязанный, данные довольно локализованы, а чтения довольно дороги.В частности:

1. Наборы данных имеют размер от 2 до 30 гигабайт, поэтому я должен отобразить фрагменты файла в память для чтения.Это очень дорого по сравнению с остальной работой, которую я делаю в алгоритме.Из профилирования я обнаружил, что примерно 60% времени тратится на чтение памяти, поэтому это подходящее место для начала оптимизации.
2. При работе с частью этого набора данных мне нужно переходить по ссылкам внутриэто (представьте, что это похоже на связанный список), и хотя эти операции чтения не гарантированы почти последовательными, они довольно локализованы.Это означает:
3. Скажем, например, мы работаем с 2 мегабайтами памяти одновременно.Если вы прочитаете 2 мегабайта данных в память, примерно 40% операций чтения, которые мне придется впоследствии выполнить, будут в тех же 2 мегабайтах памяти.Примерно 20% операций чтения будут представлять собой чисто произвольный доступ к остальным данным, а остальные 40%, скорее всего, будут связаны с сегментом 2 мегабайта, который указывает на этот.

Из знанияПроблема и из профилирования, я считаю, что введение кэша в программу очень поможет.То, что я хочу сделать, - это создать кеш, который содержит N фрагментов X мегабайтов памяти (N и X настраиваются, чтобы я мог его настроить), и я могу сначала проверить его, прежде чем сопоставлять другой раздел памяти.Кроме того, чем дольше что-то было в кеше, тем меньше вероятность того, что мы будем запрашивать эту память в краткосрочной перспективе, и поэтому самые старые данные должны будут устареть.

После всего этого мой вопросочень просто: Какую структуру данных лучше всего реализовать для кеша такого типа?

Мне нужны очень быстрые поиски, чтобы увидеть, находится ли данный адрес в кеше.С каждым «промахом» кеша я захочу удалить его самый старый член и добавить нового.Однако я планирую попытаться настроить его (изменив объем кэшируемого объема) таким образом, чтобы 70% или более операций чтения были попаданиями.

В настоящее время я думаю использовать дерево AVL (LOG2 n для поиска /вставить / удалить) будет самым безопасным (без вырожденных случаев).Мой другой вариант - разреженная хеш-таблица, так что поиск будет в лучшем случае O (1).Теоретически это может выродиться в O (n), но на практике я мог бы снизить количество столкновений.Здесь возникает вопрос, сколько времени потребуется, чтобы найти и удалить самую старую запись в хеш-таблице.

Есть ли у кого-нибудь какие-либо мысли или предложения по поводу того, какая структура данных будет лучше здесь и почему?

Answer 1

Похоже, что вы ищете LRU (Наименее недавно использованный) кеш: Дизайн LRU кэш

Answer 2

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

Одно дерево должно сортироваться по позиции в файле. Это позволяет вам выполнять поиск в log (n), чтобы увидеть, есть ли там ваш кеш.

Другое дерево должно сортироваться по используемому времени (которое может быть представлено числом, которое увеличивается на единицу при каждом использовании). При использовании кэшированного блока вы удаляете его, обновляете время и вставляете его снова. Это также займет log (n). Если вы пропустите, удалите наименьший элемент дерева и добавьте новый блок как самый большой. (Не забудьте также удалить / добавить этот блок в дерево по позициям в файле.)

Если в вашем кеше не так много элементов, вам все равно будет лучше, если вы просто сохраните все в отсортированном массиве (используя сортировку вставками для добавления новых элементов). Перемещение 16 предметов вниз на одно место в массиве невероятно быстро.

Answer 3

Если 60% вашего алгоритма - это ввод-вывод, я полагаю, что фактическая структура кеша не имеет большого значения - любой вид кеша может существенно увеличить скорость.

ОднакоДизайн во многом зависит от того, какие данные вы используете для доступа к своим частям.String, int и т. Д. Если у вас есть int, вы можете создать хеш-карту в связанном списке, стереть пропущенную кеш-память, стереть и затем нажать сверху, если кеш попал.имена (чаще всего, неупорядоченная карта) во многих реализациях.Boost имеет один, есть один в TR1 и т. Д. Большим преимуществом hash_map является меньшая потеря производительности при растущих числах и большая гибкость в отношении ключевых значений.