[2022 Day 17] [Python] When optimization doesn't optimize
Anyone else occasionally clean the cave by identifying a highest path between the walls and truncating all rock below the bottom of that path, to speed up checks of new rocks against existing? And then write a __repr__ like Eric's examples but additionally showing how many rows have been truncated in total? It may or may not surprise you — I didn't think to check until a couple days ago — that the solution runs faster without this cleaning, even up to 50k rocks.
5 comments · 100% upvoted · other discussions
This is clearly a memory usage optimization, not execution time optimization. Why would you expect it to be faster?
EDIT: To clarify:
Most "optimizations", even ones that involve algorithm complexity reducion, are focused on making one aspect of program better at the cost of others. Caching is reducing execution time at the cost of memory. Purging (in this example) is reducing memory usage at expense of execution time. Some kinds of heuristics are reducing memory usage and execution time at the cost of precision/ chance to get correct result. Some optimizations make code mre efficient at the cost of code readability/maintainability even. You should identify which aspect is the one needing optimization, and what you can spare, and see relative magnitude of change (cost / result) before applying an optimization.
This one adds an expensive computation step, and unless your tower is so exceptionally big that it has to page to HDD, it's not gonna pay off. For Part 1, there are 2022 piece with maximum height of 4, and field if 9 cells wide with walls. So 9*(2022*4 + 3) is the biggest your field could ever become (actually even that size is unreachable). That's under 1MB. For Part 2, it could probably be a reasonable optimization under certain circumstances, but I'd expect execution time to be unreasonable even without this optimization at the point where mamory becomes an issue.
RobinFiveWords [OP] 1 points · Dec 2022
Agreed — I think I was still shook by day 16 part 2 (which I didn't complete until an hour after day 17 went up) and was looking to minimize everything.
Definitely a learning moment because while I've been focused on using the more efficient type of collection — if iterating through it, list or queue; if checking membership, set — I only recall thinking "sets fast" and not "sets are O(1)".
Perhaps what also pushed me in this direction — if it wasn't just reaction to day 16 — is that I had intended to visualize the test examples more this year, and this was one of the first times I really got into writing a __repr__ method. The yak wasn't going to shave itself. Also, graph traversal is still on my needs-more-study list, so when I got an idea involving DFS that I knew how to implement and could visualize the results, I just decided to dive in.