Jump to content
  • Advertisement
Sign in to follow this  
indigox3

pattern or strategy for comparing state?

This topic is 4058 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!