Я работаю над приложением .NET 4.0, которое выполняет довольно дорогие вычисления для двух двойных значений, возвращая двойное. Этот расчет выполняется для каждого из нескольких тысяч предметов . Эти вычисления выполняются в Task
потоке потоков.
Некоторые предварительные тесты показали, что одни и те же вычисления выполняются снова и снова, поэтому я бы хотел кешировать n результатов. Когда кеш заполнен, я бы хотел выбросить наименее часто используемый элемент. ( Правка: я понял, что реже-менее часто это не имеет смысла, потому что, когда кэш заполнен, и я заменил бы результат на недавно вычисленный, он будет реже использоваться и сразу же заменен при следующем вычислении нового результата и добавил в кеш)
Чтобы реализовать это, я подумывал об использовании Dictionary<Input, double>
(где Input
будет мини-класс, хранящий два входных двойных значения) для хранения входных данных и кэшированных результатов. Однако мне также необходимо отслеживать, когда результат использовался в последний раз. Для этого я думаю, что мне понадобится вторая коллекция, в которой хранится информация, необходимая для удаления результата из диктонары, когда кэш заполняется. Я обеспокоен тем, что постоянное хранение этого списка негативно скажется на производительности.
Есть ли лучший (т.е. более производительный) способ сделать это, или, может быть, даже общая структура данных, о которой я не знаю? Какие вещи я должен профилировать / измерять, чтобы определить оптимальность моего решения?
источник
Похоже, что нужно приложить немало усилий для одного вычисления, учитывая вычислительную мощность, которую вы имеете в своем распоряжении на среднем ПК. Кроме того, вы по-прежнему будете платить за первый вызов вашего вычисления для каждой уникальной пары значений, поэтому 100 000 уникальных пар значений по-прежнему будут стоить вам, как минимум, времени n * 100 000. Учтите, что доступ к значениям в вашем словаре, вероятно, станет медленнее по мере увеличения словаря. Можете ли вы гарантировать, что скорость доступа к вашему словарю компенсирует достаточную отдачу от скорости ваших расчетов?
В любом случае, звучит так, как будто вам, возможно, придется подумать о поиске средств для оптимизации вашего алгоритма. Для этого вам понадобится инструмент профилирования, например, Redgate Ants, чтобы увидеть узкие места, и помочь вам определить, есть ли способы уменьшить некоторые накладные расходы, которые могут у вас возникнуть в связи с созданием классов, обходами списков, базой данных. доступ или что-то, что стоит вам так много времени.
источник
Одна мысль, почему только кешировать n результатов? Даже если n равно 300 000, вы будете использовать только 7,2 МБ памяти (плюс все, что нужно для структуры таблицы). Конечно, это предполагает три 64-битных дубли. Вы можете просто применить памятку к самой сложной процедуре вычисления, если вы не беспокоитесь о нехватке памяти.
источник
Подход со второй коллекцией в порядке. Это должна быть очередь с приоритетами, которая позволяет быстро находить / удалять минимальные значения, а также изменять (увеличивать) приоритеты в очереди (последняя часть является сложной, не поддерживаемой большинством простых реализаций очереди prio). Библиотека C5 имеет такую коллекцию, она называется
IntervalHeap
.Или, конечно, вы можете попробовать создать свою собственную коллекцию, что-то вроде
SortedDictionary<int, List<InputCount>>
. (InputCount
должен быть класс, объединяющий вашиInput
данные с вашейCount
ценностью)Обновление этой коллекции при изменении значения счетчика может быть реализовано путем удаления и повторной вставки элемента.
источник
Как указывается в ответе Питера Смита, шаблон, который вы пытаетесь реализовать, называется запоминанием . В C # довольно сложно реализовать запоминание прозрачным способом без побочных эффектов. Книга Оливера Штурма по функциональному программированию на C # дает решение (код доступен для скачивания, глава 10).
В F # было бы намного проще. Конечно, стоит начать использовать другой язык программирования, но стоит подумать. Особенно в сложных вычислениях, это должно облегчить программирование большего количества вещей, чем запоминание.
источник