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