Sign in to follow this  
indigox3

pattern or strategy for comparing state?

Recommended Posts

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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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:
  1. You ask an object for a result given some parameters.
  2. The object looks in its cache to see if the result is already there (using the parameters as a key).
  3. 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.

Share this post


Link to post
Share on other sites
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:
  1. You ask an object for a result given some parameters.
  2. The object looks in its cache to see if the result is already there (using the parameters as a key).
  3. 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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this