For part one and likely part 2 you don't need to do all 499500 comparisons, you could split the grid into boxes and only search adjacent ones. E.g. z / 10 = which decile and look at z, z-1, z+1 (and the same for x and y). Less work for the processor, more work for you, and of course, sqrt (which you can also probably skip) is so efficient on modern chips that the overhead of this eats a chunk of the benefits (depending on how low-level your language is).
You're right, iterating through the pairs does seem to be the way. After doing some analyzing of what takes how long, it seems my issue is with (quickly) figuring out whether I've already connected all nodes or not.
4 Comments
owenfromcanada@lemmy.ca · 5 pts · 275d
Did you also try to implement a sort that ended up being magnitudes less efficient than calling
.sort(), or are you normal?dbx12@programming.dev · 4 pts · 275d
strlcpy@lemmy.sdf.org · 2 pts · 275d
What are we calling brute force here? Continuing to go through the pair list and merging groups? Is there any other way?
Deebster@programming.dev · 1 pts · 275d
For part one and likely part 2 you don't need to do all 499500 comparisons, you could split the grid into boxes and only search adjacent ones. E.g. z / 10 = which decile and look at z, z-1, z+1 (and the same for x and y). Less work for the processor, more work for you, and of course, sqrt (which you can also probably skip) is so efficient on modern chips that the overhead of this eats a chunk of the benefits (depending on how low-level your language is).
eco_game@discuss.tchncs.de · 1 pts · 275d
You're right, iterating through the pairs does seem to be the way. After doing some analyzing of what takes how long, it seems my issue is with (quickly) figuring out whether I've already connected all nodes or not.