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

11

Я работаю над приложением .NET 4.0, которое выполняет довольно дорогие вычисления для двух двойных значений, возвращая двойное. Этот расчет выполняется для каждого из нескольких тысяч предметов . Эти вычисления выполняются в Taskпотоке потоков.

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

Чтобы реализовать это, я подумывал об использовании Dictionary<Input, double>(где Inputбудет мини-класс, хранящий два входных двойных значения) для хранения входных данных и кэшированных результатов. Однако мне также необходимо отслеживать, когда результат использовался в последний раз. Для этого я думаю, что мне понадобится вторая коллекция, в которой хранится информация, необходимая для удаления результата из диктонары, когда кэш заполняется. Я обеспокоен тем, что постоянное хранение этого списка негативно скажется на производительности.

Есть ли лучший (т.е. более производительный) способ сделать это, или, может быть, даже общая структура данных, о которой я не знаю? Какие вещи я должен профилировать / измерять, чтобы определить оптимальность моего решения?

PersonalNexus
источник

Ответы:

12

Если вы хотите использовать кэш исключения LRU (исключение наименьшее количество использовавшихся недавно), вероятно, хорошая комбинация структур данных:

  • Круговой связанный список (как приоритетная очередь)
  • Словарь

Вот почему:

  • Связанный список имеет время вставки и удаления O (1)
  • Узлы списка могут быть повторно использованы, когда список заполнен, и нет необходимости в дополнительных выделениях.

Вот как должен работать основной алгоритм:

Структуры данных

LinkedList<Node<KeyValuePair<Input,Double>>> list; Dictionary<Input,Node<KeyValuePair<Input,Double>>> dict;

  1. Вход получен
  2. Если словарь содержит ключ
    • вернуть значение, хранящееся в узле и переместить узел в начало списка
  3. Если словарь не содержит ключ
    • вычислить значение
    • сохранить значение в последнем узле списка
    • если последний не имеет значения, удалите предыдущий ключ из словаря
    • переместить последний узел в первую позицию.
    • сохранить в словаре пару значений ключа (input, node).

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

Поп-каталин
источник
Хорошие моменты, лучшая идея пока, ИМХО. Я реализовал кеш на основе этого сегодня, и мне придется профилировать и посмотреть, насколько хорошо он работает завтра.
PersonalNexus
3

Похоже, что нужно приложить немало усилий для одного вычисления, учитывая вычислительную мощность, которую вы имеете в своем распоряжении на среднем ПК. Кроме того, вы по-прежнему будете платить за первый вызов вашего вычисления для каждой уникальной пары значений, поэтому 100 000 уникальных пар значений по-прежнему будут стоить вам, как минимум, времени n * 100 000. Учтите, что доступ к значениям в вашем словаре, вероятно, станет медленнее по мере увеличения словаря. Можете ли вы гарантировать, что скорость доступа к вашему словарю компенсирует достаточную отдачу от скорости ваших расчетов?

В любом случае, звучит так, как будто вам, возможно, придется подумать о поиске средств для оптимизации вашего алгоритма. Для этого вам понадобится инструмент профилирования, например, Redgate Ants, чтобы увидеть узкие места, и помочь вам определить, есть ли способы уменьшить некоторые накладные расходы, которые могут у вас возникнуть в связи с созданием классов, обходами списков, базой данных. доступ или что-то, что стоит вам так много времени.

S.Robins
источник
1
К сожалению, в настоящее время алгоритм вычисления не может быть изменен, поскольку это сторонняя библиотека, которая использует некоторые сложные математические функции, которые, естественно, сильно нагружают процессор. Если позже это будет переработано, я обязательно проверю предложенные инструменты профилирования. Кроме того, вычисления будут выполняться довольно часто, иногда с одинаковыми входными данными, поэтому предварительное профилирование показало явное преимущество даже при очень наивной стратегии кэширования.
PersonalNexus
0

Одна мысль, почему только кешировать n результатов? Даже если n равно 300 000, вы будете использовать только 7,2 МБ памяти (плюс все, что нужно для структуры таблицы). Конечно, это предполагает три 64-битных дубли. Вы можете просто применить памятку к самой сложной процедуре вычисления, если вы не беспокоитесь о нехватке памяти.

Питер Смит
источник
Не будет только одного кэша, но по одному на «элемент», который я анализирую, и может быть несколько сотен тысяч этих элементов.
PersonalNexus
Каким образом имеет значение, из какого «элемента» поступает информация? есть ли побочные эффекты?
JK.
@jk. Различные элементы будут давать очень разные исходные данные для расчета. Так как это означает, что будет мало совпадений, я не думаю, что хранить их в одном кэше имеет смысл. Кроме того, разные элементы могут жить в разных потоках, поэтому, чтобы избежать общего состояния, я бы хотел хранить кеши отдельно.
PersonalNexus
@PersonalNexus Я так понимаю, что в расчет вовлечено более двух параметров? В противном случае у вас все еще есть f (x, y) = делать что-то еще. Плюс общее состояние кажется, что это будет способствовать производительности, а не мешать?
Питер Смит
@PeterSmith Два параметра являются основными входами. Есть и другие, но они редко меняются. Если они это сделают, я бы выбросил весь кеш. Под «общим состоянием» я подразумевал общий кэш для всех или группы элементов. Так как это нужно было бы заблокировать или синхронизировать каким-либо другим способом, это снизило бы производительность. Подробнее о влиянии производительности общего состояния .
PersonalNexus
0

Подход со второй коллекцией в порядке. Это должна быть очередь с приоритетами, которая позволяет быстро находить / удалять минимальные значения, а также изменять (увеличивать) приоритеты в очереди (последняя часть является сложной, не поддерживаемой большинством простых реализаций очереди prio). Библиотека C5 имеет такую ​​коллекцию, она называется IntervalHeap.

Или, конечно, вы можете попробовать создать свою собственную коллекцию, что-то вроде SortedDictionary<int, List<InputCount>>. ( InputCountдолжен быть класс, объединяющий ваши Inputданные с вашей Countценностью)

Обновление этой коллекции при изменении значения счетчика может быть реализовано путем удаления и повторной вставки элемента.

Док Браун
источник
0

Как указывается в ответе Питера Смита, шаблон, который вы пытаетесь реализовать, называется запоминанием . В C # довольно сложно реализовать запоминание прозрачным способом без побочных эффектов. Книга Оливера Штурма по функциональному программированию на C # дает решение (код доступен для скачивания, глава 10).

В F # было бы намного проще. Конечно, стоит начать использовать другой язык программирования, но стоит подумать. Особенно в сложных вычислениях, это должно облегчить программирование большего количества вещей, чем запоминание.

Герт Арнольд
источник