Estou trabalhando em um aplicativo .NET 4.0, que executa um cálculo bastante caro em duas duplas retornando uma dupla. Este cálculo é realizado para cada um dos vários milhares de itens . Esses cálculos são realizados em um Task
encadeamento em um conjunto de encadeamentos.
Alguns testes preliminares mostraram que os mesmos cálculos são realizados repetidamente, então eu gostaria de armazenar n resultados em cache . Quando o cache está cheio, eu gostaria de jogar fora os menos frequentemente artigo recentemente utilizado. ( Editar: percebi que com menos frequência não faz sentido, porque quando o cache está cheio e eu substituía um resultado por um recém-calculado, esse seria menos usado e substituído imediatamente na próxima vez que um novo resultado fosse calculado e adicionado ao cache)
Para implementar isso, eu estava pensando em usar um Dictionary<Input, double>
(onde Input
seria uma mini-classe armazenando os dois valores duplos de entrada) para armazenar as entradas e os resultados armazenados em cache. No entanto, eu também precisaria acompanhar quando um resultado foi usado pela última vez. Para isso, acho que precisaria de uma segunda coleção para armazenar as informações necessárias para remover um resultado do dictonário quando o cache estivesse ficando cheio. Preocupa-me que a manutenção constante dessa lista tenha um impacto negativo no desempenho.
Existe uma maneira melhor (ou seja, mais eficiente) de fazer isso, ou talvez até uma estrutura de dados comum que eu desconheça? Que tipos de coisas devo analisar / medir para determinar a otimização da minha solução?
fonte
Parece muito esforço para um único cálculo, considerando o poder de processamento que você tem à disposição no PC comum. Além disso, você ainda terá as despesas da primeira chamada do seu cálculo para cada par de valores exclusivo; portanto, 100.000 pares de valores únicos ainda custarão o tempo n * 100.000, no mínimo. Considere que o acesso a valores no seu dicionário provavelmente se tornará mais lento à medida que o dicionário aumentar. Você pode garantir que a velocidade de acesso ao seu dicionário compense o suficiente para fornecer um retorno razoável em relação à velocidade do seu cálculo?
Independentemente disso, parece que você provavelmente precisará considerar um meio de otimizar seu algoritmo. Para isso, você precisará de uma ferramenta de criação de perfil, como o Redgate Ants , para ver onde estão os gargalos e para ajudá-lo a determinar se existem maneiras de reduzir algumas das despesas gerais que você possa ter em relação às instanciações de classe, percursos de lista, banco de dados acessos ou o que quer que esteja custando tanto tempo.
fonte
Um pensamento é por que apenas cache n resulta? Mesmo que n seja 300.000, você usaria apenas 7,2 MB de memória (mais qualquer valor extra para a estrutura da tabela). Isso pressupõe três duplos de 64 bits, é claro. Você pode simplesmente aplicar a memorização à própria rotina de cálculo complexa se não estiver preocupado com a falta de espaço na memória.
fonte
A abordagem com a segunda coleção é boa. Deve ser uma fila de prioridades que permita localizar / excluir valores mínimos rapidamente e também alterar (aumentar) prioridades dentro da fila (a última parte é difícil, não suportada pela maioria das implementações simples de fila de espera). A biblioteca C5 tem essa coleção, é chamada
IntervalHeap
.Ou, é claro, você pode tentar criar sua própria coleção, algo como a
SortedDictionary<int, List<InputCount>>
. (InputCount
deve ser uma classe que combina seusInput
dados com seuCount
valor)A atualização dessa coleção ao alterar seu valor de contagem pode ser implementada removendo e reinserindo um elemento.
fonte
Conforme apontado na resposta de Peter Smith, o padrão que você está tentando implementar é chamado de memorização . No C #, é muito difícil implementar a memorização de maneira transparente, sem efeitos colaterais. O livro de Oliver Sturm sobre programação funcional em C # fornece uma solução (o código está disponível para download, capítulo 10).
Em F #, seria muito mais fácil. Obviamente, é uma grande decisão começar a usar outra linguagem de programação, mas pode valer a pena considerar. Especialmente em cálculos complexos, é mais fácil programar do que memorizar.
fonte