36
SOLUTION MEGATHREAD-🎄- 2022 Day 14 Solutions -🎄-(self.adventofcode)
submitted 3 years, 1 month ago* (edited 13 minutes after) by daggerdragon to /r/adventofcode (134.8k)
SUBREDDIT NEWS
Livehas been renamed toStreamingfor realz this time.- I had updated th...
since 3 years, 1 month ago
8 of 8
Tip Reveddit Real-Time can notify you when your content is removed.
your account history
Tip Check if your account has any removed comments.
view my removed comments you are viewing a single comment's thread.
view all comments
I mean the hash table is going to make it way slower.
My hacky dumb JS implementation using 2D arrays solves it in 21ms (26 including parsing the input) in the chrome console on a 2021 MBP.
The problem isn't really big enough for a more efficient algorithm to make a difference.
[removed] content loading...
So I tried both out in cpp.
Both seem to have a major impact / the 2D array is still significantly faster for this problem size.
Saying that I was wrong in that the algorithm outweighs it / the better algorithm with the hashmap beats the dumb approach with the array.
[removed] content loading...
Its not the only reason, but it alone would get it to the point where /u/BrianDead wouldn't have called it slow in the first place - assuming a similar difference to the C++ code it would have it down to under half a second. In practice significantly less again because it would also get rid of the string keys (not needed for arrays and in my C++ hashmap implementation I was using bit shifting y then bitwise or with x).
If getting rid of the hashmap gets it from 3.2s -> sub 100ms (im assuming it'd be same ballpark as JS) then I'd say it has made it way slower, its not just a tiny constant factor difference and its more than measurable.
If I get time tomorrow guess its time to touch perl for the first time in years to prove it!
I switched it to use an array instead of a hash. It halves the time. Still nowhere close to u/ProfONeill's algorithm, of course, but it certainly makes a difference when you're doing as many lookups as I am in my crappy method.
With a hash (code):
% time cat in.d14r | perl d14b.plminx=474 maxx=527 miny=0 maxy=165Answer is 26358cat in.d14r 0.00s user 0.00s system 43% cpu 0.009 totalperl d14b.pl 2.38s user 0.01s system 99% cpu 2.411 totalWith an array (code:
% time cat in.d14r | perl d14b-array.plminx=474 maxx=527 miny=0 maxy=165Answer is 26358cat in.d14r 0.00s user 0.00s system 42% cpu 0.009 totalperl d14b-array.pl 1.14s user 0.01s system 98% cpu 1.177 totalThe amount of computation on each iteration is trivial. You'd expect the lookups if nothing else because of having to bring data in/out of the CPU caches to be by far the bulk of the time.
With a 2D array you're pulling data from a contiguous block of memory so you'll minimise I/O to the CPU. To do so you're indexing into it which is a multiply then add. You may even find the compiler recognises the loop and optimises the multiplies away to two adds.
With the hash table you've got to combine multiple values, obtain a hash which is at minimum xoring them together, modulo it, do a similar array lookup then deal with collisions. Thats going to work out a large multiple of the array lookups. You'll also be jumping all over the bucket array causing more cache misses and collisions mean its not necessarily a constant factor.
If you're timing over the logic / after the parsing then I'd be shocked if there wasn't a difference. If you try it and im wrong please do link the code / will take a look once I'm back in front of a keyboard tomorrow.
*Got curious, converted my JS with the dumb approach to C for a fairer comparison. Solving part 2 (after parsing logic) now takes 2-3ms on a 2021 MBP / compiled with -Ofast. May uplift to C++ and compare to a hashmap tomorrow if I get time.
It makes a difference when the original implementation is as inefficient as mine. Running u/ProfONeill's method takes around 100ms on my system instead of 3.83s for mine. I just got carried away watching the grains fall one by one.