How to best translate this C++ algorithm into D?
logicchains via Digitalmars-d
digitalmars-d at puremagic.com
Fri Jun 6 20:50:16 PDT 2014
I came across an interesting C++ program[1] in a blog post[2]
that I wanted to try and translate into D. My attempt[3] is
however still significantly slower than the C++ version; with
input 100 100 100, for instance, it runs in around 200 ms,
compared to 60 ms for the C++ version (it however nevertheless
much faster than my naive C implementation, which runs in around
2 seconds for that input). That's using the LLVM compiler for
each language, btw.
The C++ algorithm is:
std::vector<forest_t> meal(const std::vector<forest_t>&
forests) {
static const std::array<forest_t,3> possible_meals = {{
forest_t{{-1,-1,+1}},
forest_t{{-1,+1,-1}},
forest_t{{+1,-1,-1}}
}};
// apply possible meals to all forests
std::vector<forest_t> next_forests;
next_forests.reserve(forests.size() * possible_meals.size());
for (auto meal: possible_meals) {
forest_t next_forest;
std::transform(std::begin(forests), std::end(forests),
std::back_inserter(next_forests),
[&](const forest_t& forest) {
std::transform(std::begin(forest), std::end(forest),
std::begin(meal), std::begin(next_forest),
std::plus<int>());
return next_forest;
});
}
// filter valid forests
auto valid_end = std::remove_if(std::begin(next_forests),
std::end(next_forests),
forest_invalid);
// delete duplicates
std::stable_sort(std::begin(next_forests), valid_end);
next_forests.erase(
std::unique(std::begin(next_forests), valid_end),
std::end(next_forests));
return next_forests;
}
While my (much more concise; thanks D!) attempt at implementing
it is:
forest_t[] meal(in forest_t[] forests) {
forest_t[3] possible_meals = [{-1, -1, +1}, {-1, +1, -1}, {+1,
-1, -1}];
return map!(a => [possible_meals[0]+a, possible_meals[1]+a,
possible_meals[2]+a])(forests)
.join
.filter!(a => !forest_invalid(a)).array
.sort.uniq.array;
}
Any suggestions for how I could make the D code do the same as
the C++ standard transform? Some sort of flatmap could be useful,
to avoid the need for a join. It'd also be nice if there was a
way to sort/uniq the filterresults directly without having to
convert to an array first.
1.
http://www.unisoftwareplus.com/download/blog/2014-06/magic_forest.cpp
2.
http://unriskinsight.blogspot.com.au/2014/06/fast-functional-goats-lions-and-wolves.html
3. https://gist.github.com/logicchains/2442dfca5d517f1e4bab
More information about the Digitalmars-d
mailing list