Using sort to filter duplicates is horribly worse compared to hashing (javascript for instance).
Java version has rather poor impl, it's interesting to see the GC+allocation cost and the GC type used.
C++ version does not use really use func. prog in find_stable_forests and meal...
Using sort to filter duplicates is horribly worse compared to hashing (javascript for instance).
Is this really true? A sort plus a linear scan has very low constant time factors, good cache locality (depending on the sorting algorithm used), and no need to allocate if you're sorting in place. I've seen good results using sort to filter duplicates in my own performance-sensitive code. Are you saying this technique is "horribly worse" based on your experience or intuition?
It will likely get faster the more duplicates you have, as it allows the CPU to predict a branch more reliably several times before being wrong and having to re-do some of its prediction stuff. (note that I'm not experienced with optimizing stuff, dealing with cache optimizations, etc., but I have read a decent amount, and I did take a class about CPU architecture) I would also suspect that hashing might end up messing with memory all over the place, causing the cache to be partly useless.
That question (and answer) is probably not relevant here. The important thing is likely cache locality, not branch prediction (as the test case is very different in that question, amplifying branch misprediction issues, which won't be the issue here).
In the case of the JS solution, it runs horribly and is highly inefficient.[0]
For non-hot code, it is perfectly fine, but in this case, inside of a main loop like this it is a waste of cpu cyles. Compare the amount of forests here:
$ node orig-magicForest.js 117 155 106
total forests: 1522899
{ goats: 0, wolves: 0, lions: 223 }
total time: 816ms
$ node new-magicForest.js 117 155 106
total forests: 428
{ goats: 0, wolves: 0, lions: 223 }
total time: 6ms
Using sort to filter duplicates is horribly worse compared to hashing (javascript for instance). Java version has rather poor impl, it's interesting to see the GC+allocation cost and the GC type used. C++ version does not use really use func. prog in find_stable_forests and meal...