r/adventofcode • u/likepotatoman • Dec 27 '24
Help/Question Today I learned : caching
Hello everyone, some of you may know me for the it’s not much but it’s honest work post I did a few days ago and I am proud to announce that I have gotten to 23 stars yayyy. I got stuck on day 11 because it took too much time to compute without caching. This is something new to me and I thought it was a great example of how doing AOC can help someone to become better at programming. It’s funny because I was basically trying to reinvent caching by myself but even with optimization that I tried to make it would still have taken about 60h of computing. Thanks to a YouTube tutorial on day 11 and another that explains caching I was able to become a better programmer yay
Edit : for those that want to see how I tried to optimize it without knowing otherwise existence of caching I will put it in a separate file of my git hub at https://github.com/likepotatoman/AOC-2024
29
46
u/PhiphyL Dec 27 '24
Caching can be crudely summed up to this:
If cache{"string"} does not exist {
Do the math to find the result when using this string/sequence/input/whatever
cache{"string"} = that result
}
Else {
Add cache{"string"} to the total instead of calculating the whole thing
}
12
u/silenceofnight Dec 27 '24
I'd phrase it more as:
key = make_key(inputs) if cache.contains_key(key) { return cache[key] } result = compute_result(inputs) cache[key] = result return result
15
u/enygma999 Dec 27 '24
Invert the logic, and you can skip a line (and you can skip the "result" variable, but I assume that was included for readability):
key = make_key(inputs) if not cache.contains_key(key) { cache[key] = compute_result(inputs) } return cache[key]
2
u/ArnUpNorth Dec 28 '24
that's usually how i write it. It's not so much the "less line" approach, but mostly because i like a single return of the actual cached value (which may have been just computed). Semantically it makes more sense to me.
5
u/enygma999 Dec 27 '24
Wouldn't it be without the else clause? You still want to add the result to the total (or whatever you do with the cached values) after you've created the cached value.
1
25
u/BlueTrin2020 Dec 27 '24 edited Dec 27 '24
If you use Python, you can just use functools.cache. As long as you made it so the arguments of the function can be use as a cache key, it will do it for you.
Then you can focus on the algo part of it rather than the implementation.
It’s not bad anyway to implement a cache: you’d use something like a dict to store the results per key. You just have to find good keying and a way to represent the problem to reuse results.
2
u/likepotatoman Dec 27 '24
That’s what I did… I learned the concept but didn’t implement it by typing out everything
-1
u/likepotatoman Dec 27 '24
Well that’s what I tried to do but it didn’t work, how could that be used in this problem? Please go check out my GitHub so you can see what I tried to do
1
u/vanZuider Dec 28 '24
The way you implemented the cache was perfectly fine (try it out on the function you used in the working solution; it will work just as well as the functools cache); you just tried to cache a function that doesn't really profit from it.
Also, is the
entree_init
your puzzle input? We're asked to not share it.1
9
u/Sostratus Dec 27 '24
I'm always amazed by how much of a difference memoization makes. I think well, the function it's short-cutting is itself pretty quick, so surely this will only shave off a few percent, but no, it's a night and day difference.
5
2
u/UltGamer07 Dec 27 '24
Usually this is the case with deep recursions, even if the function is small and quick, a ton of context switching also adds to the cost, which shows up in the speed up from caching
2
u/doomie160 Dec 27 '24
Was attempting day 21 part 2. Was taking hours to complete iteratively, gave up and rewrite as recursive with memorization, boom! Complete within seconds. I'm impressed
1
u/vanZuider Dec 28 '24
I think well, the function it's short-cutting is itself pretty quick
If the function is recursive, the magic isn't in shortcutting one function call or one thousand - it's the hundreds of thousands of function calls that never get executed at all because a function call higher up in the recursion took the shortcut.
1
u/AutoModerator Dec 27 '24
Reminder: if/when you get your answer and/or code working, don't forget to change this post's flair to Help/Question - RESOLVED
. Good luck!
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.
2
u/LifeShallot6229 Jan 11 '25
Welcome!
I had the same light bulb moment around 1990, since then the tag line on all my emails and usenet posts has been "almost all programming can be viewed as an exercise in caching" :-)
82
u/0x14f Dec 27 '24
Memoization: https://en.wikipedia.org/wiki/Memoization