pattern or strategy for comparing state?
Author
I've got a data producer, which internally stores some parameters and is able to generate some result from them.
When the data is requested multiple times, I'd like to be able to avoid re-generating the data again, if the parameters are the same.
Both the producer and the result are classes in C++.
My current thinking is to just override the copy constructor and equality operator on the producer, so that each time a result is generated, a copy of the producer is saved with it. Then when the data is requested again, I could just look through a global list of already generated results, and use the producer's equality operator to compare parameters with which the results were generated.
The biggest problem I see with this, is that it could use a lot of memory to keep all of the producers around for each result.
Just wondering if there is some design pattern or strategy for handling this type of problem?
Sounds like you may want to look up the term "dynamic programming" used to speed up some recursive functions.
The idea is that the "producer" is not stored, but there is a global lookup table of inputs->result
that is used, so if a result exists in the table it is returned instead of recalculating it.
The idea is that the "producer" is not stored, but there is a global lookup table of inputs->result
that is used, so if a result exists in the table it is returned instead of recalculating it.
Author
Quote:Original post by KulSeran
Sounds like you may want to look up the term "dynamic programming" used to speed up some recursive functions.
The idea is that the "producer" is not stored, but there is a global lookup table of inputs->result
that is used, so if a result exists in the table it is returned instead of recalculating it.
It looks like an efficient implementation of memoization is what I'm looking for, thanks!
What you are looking for is called a "cache". It is not clear from your description how it would be applied, but it generally works like this:
- You ask an object for a result given some parameters.
- The object looks in its cache to see if the result is already there (using the parameters as a key).
- If it is, you return the result and you are done. If it is not, then you compute the result and return it, and also store it in the cache. If the cache is full, then you eject an entry first in order to make room. There are various strategies that determine which entry to eject.
Quote:Original post by JohnBolton
What you are looking for is called a "cache". It is not clear from your description how it would be applied, but it generally works like this:
- You ask an object for a result given some parameters.
- The object looks in its cache to see if the result is already there (using the parameters as a key).
- If it is, you return the result and you are done. If it is not, then you compute the result and return it, and also store it in the cache. If the cache is full, then you eject an entry first in order to make room. There are various strategies that determine which entry to eject.
Of course this only works if the cached result is either returned by value (or as a copy) or is strictly read-only.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
