101–110 of 115 posts
I'm not sure if I got the problem right, because it solves the hardest case almost instantly (2006 lions, 2055 wolves, 2017 goats -> 4023 lions), in 0.8s on my macbook air.
I used a general search algo that I've also used in the past for the missionaries and cannibals and snake cube puzzles.
It uses a set to store the past states seen, instead of deduping a list.
It is rather sad that none of the 49 comments (at this time of posting) have made a mention of the underlying math problem, which is super interesting, and instead focus on dubious speed metrics (dubious in the sense these metrics change with the chip/cache/RAM/compiler/lang/coding-style & aren't that relevant anyways, compared to the underlying problem) Lemme rephrase this rather interesting problem: There are 2055…
The code is very inefficient to say the least. I made some modifications (diverging further from the "functional" nature, if you could call it that) and as you can see it is much faster[0]. Output: $ node new-magicForest.js 2017 2055 2006 total forests: 6128 { goats: 0, wolves: 0, lions: 4023 } total time: 20ms [0] https://gist.github.com/chapel/1c038b2bf64b3037aaea
I was curious how a non-functional version would fare, so I wrote one in Nimrod and it's a lot faster than the functional C++: https://gist.github.com/def-/8187448ea7a5c8da8265 Goats Wolves Lions C++11 Nimrod 17 55 6 0.00 0.00 117 155 106 0.17 0.01 217 255 206 0.75 0.01 317 355 306 2.16 0.01 417 455 406 5.28 0.01 517 555 506 10.75 0.01 617 655 606 19.15 0.02 717 755 706 31.58 0.02 817 855 806 46.52 0.02 917 955 906 6…
The important word here is "functional" C++. This is not about "fastest" C++. What does your comparison tell us?
Earlier quoted context omitted.
Only computation-heavy code will show a difference. And the disparity is going to vary a lot. Some code will be easy for Java's optimizer and won't give C++ any advantage.
Some will even put C++ at a disadvantage.
Earlier quoted context omitted.
Supposedly, Java is going to be faster than native code any day now. It's been said for years. The case was somewhat credible at one time, because the opportunity exists to optimize using runtime information. I think the reason it didn't go that way is: 1. CPUs have gotten very good at doing runtime optimization kinds of things on their own, like predicting branches and reducing the cost of virtual function calls. 2.…
No, what happened is mainly that memory access has become a big bottleneck for most programs, and small footprint and cache-friendliness can easily mean a speed difference of 20x. For a number of reasons (such as Object overhead, UTF-16 strings, lack of true object arrays), it is very hard to write small-footprint cache-friendly code in Java.
Writing really cache friendly code in Java requires to look at the problem orthogonally and use int[]/long[] instead of a small Object with 3 small ints.
The Java version simply features some quite horrific code but can easily be run in parallel - no one mentions that. Using streams in pure functional way w/o the parallel in mind is a ritual suicide.
Finally, The CPU running benchmark has only 2 cores which is a disadvantage with tons of allocation and garbage.
In fact, the execution time is more than doubled.
Why is this so?
The Eclipse generated version of hashCode():
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + goats;
result = prime * result + lions;
result = prime * result + wolves;
return result;
}
@Override
public int hashCode() {
final int magic = 0x9e3779b9;
int seed = 0;
seed ^= this.goats + magic + (seed > 2);
seed ^= this.lions + magic + (seed > 2);
seed ^= this.wolves + magic + (seed > 2);
return seed;
}
Example:
Forest.makeForest(517, 555, 506)
With original hashCode(): 8.177 s
With Eclipse generated hashCode(): 19.237 s
(100% repeatable with only a few 100ms diff between executions)
I was curious how a non-functional version would fare, so I wrote one in Nimrod and it's a lot faster than the functional C++: https://gist.github.com/def-/8187448ea7a5c8da8265 Goats Wolves Lions C++11 Nimrod 17 55 6 0.00 0.00 117 155 106 0.17 0.01 217 255 206 0.75 0.01 317 355 306 2.16 0.01 417 455 406 5.28 0.01 517 555 506 10.75 0.01 617 655 606 19.15 0.02 717 755 706 31.58 0.02 817 855 806 46.52 0.02 917 955 906 6…
Goats Wolves Lions C++11 Nimrod
17 55 6 0.00 0.03
117 155 106 0.17 0.13
217 255 206 0.75 0.62
317 355 306 2.16 1.89
417 455 406 5.28 4.34
517 555 506 10.75 8.42
617 655 606 19.15 14.45
717 755 706 31.58 23.04
817 855 806 46.52 33.69
917 955 906 67.94 48.57
1017 1055 1006 93.75 65.25
2017 2055 2006 731.42 500.95Earlier quoted context omitted.
Supposedly, Java is going to be faster than native code any day now. It's been said for years. The case was somewhat credible at one time, because the opportunity exists to optimize using runtime information. I think the reason it didn't go that way is: 1. CPUs have gotten very good at doing runtime optimization kinds of things on their own, like predicting branches and reducing the cost of virtual function calls. 2.…
No, what happened is mainly that memory access has become a big bottleneck for most programs, and small footprint and cache-friendliness can easily mean a speed difference of 20x. For a number of reasons (such as Object overhead, UTF-16 strings, lack of true object arrays), it is very hard to write small-footprint cache-friendly code in Java.
Converting Object[] arrays into single chunks of packed members when they're all the same type would be a pretty big win by itself.