V Sun, 31 Aug 2014 10:55:31 +0000 bearophile via Digitalmars-d-learn <digitalmars-d-learn@puremagic.com> napsáno:
> This is C++ code that solves one Euler problem: > > -------------- > #include <stdio.h> > #include <map> > > const unsigned int H = 9, W = 12; > > const int g[6][3] = {{7, 0, H - 3}, > {1 + (1 << H) + (1 << (2 * H)), 0, H - 1}, > {3 + (1 << H), 0, H - 2}, > {3 + (2 << H), 0, H - 2}, > {1 + (1 << H) + (2 << H), 0, H - 2}, > {1 + (1 << H) + (1 << (H - 1)), 1, H - 1}}; > > int main() { > unsigned long long p, i, k; > unsigned int j, l; > std::map<unsigned int, unsigned long long> x, y; > x[0] = 1; > > for (i = 0; i < W; ++i) { > y.clear(); > while (!x.empty()) { > j = x.begin()->first; > p = x.begin()->second; > x.erase(x.begin()); > > for (k = 0; k < H; ++k) > if ((j & (1 << k)) == 0) > break; > > if (k == H) > y[j >> H] += p; > else > for (l = 0; l < 6; ++l) > if (k >= g[l][1] && k <= g[l][2]) > if ((j & (g[l][0] << k)) == 0) > x[j + (g[l][0] << k)] += p; > } > x = y; > } > > printf("%lld\n", y[0]); > return 0; > } > -------------- > > > I have translated it to D like this (I know in D there are nicer > ways to write it, but I have tried to keep the look of the code > as much similar as possible to the C++ code): > > > -------------- > import core.stdc.stdio; > > const uint H = 9, W = 12; > > const uint[3][6] g = [[7, 0, H - 3], > [1 + (1 << H) + (1 << (2 * H)), 0, H - 1], > [3 + (1 << H), 0, H - 2], > [3 + (2 << H), 0, H - 2], > [1 + (1 << H) + (2 << H), 0, H - 2], > [1 + (1 << H) + (1 << (H - 1)), 1, H - 1]]; > > int main() { > ulong p, i, k; > uint j, l; > ulong[uint] x, y; > x[0] = 1; > > for (i = 0; i < W; ++i) { > y = null; > while (x.length) { > j = x.byKey.front; > p = x.byValue.front; > x.remove(cast(int)j); > > for (k = 0; k < H; ++k) > if ((j & (1 << k)) == 0) > break; > > if (k == H) > y[j >> H] += p; > else > for (l = 0; l < 6; ++l) > if (k >= g[l][1] && k <= g[l][2]) > if ((j & (g[l][0] << k)) == 0) > x[j + (g[l][0] << k)] += p; > } > x = y; > } > > printf("%lld\n", y[0]); > return 0; > } > -------------- > > > The C++ code is much faster than the D code (I see the D code 30+ > times slower with dmd and about like 20 times with ldc2). One > difference between the C++ and D code is that the C++ map uses a > search tree (red-black probably), while the D code uses a hash. > > To test that algorithmic difference, if I replace the map in the > C++ code with a std::unordered_map (C++11): > > #include <unordered_map> > ... > std::unordered_map<unsigned int, unsigned long long> x, y; > > > then the run-time increases (more than two times) but it's still > much faster than the D code. > > Is it possible to fix the D code to increase its performance > (there are associative array libraries for D, but I have not > tried them in this program). > > Bye, > bearophile I think main problem is in calling delegates (x.byKey.front and x.byValue.front;). If I change x.byValue.front with x[j], It makes program a lot faster