2

この関数のベンチマークを行ったとき、私は驚きました:

int f(int N = 999) {  
  int nMax = 0;

  for (int i = 1; i <= N; ++i)
    for (int j = i; j <= N; ++j) {
      string digits  = to_string(i*j);
      string rDigits = digits;

      reverse(rDigits.begin(), rDigits.end());

      if (digits == rDigits)
        nMax = max(i*j, nMax);
    }

  return nMax;
}

Windows 7 32 ビットおよび 64 ビットで VS2012、VS2013 (リリース、/O2)、および MinGW 4.8.0、4.8.1 (-Ofast) を使用。MinGW でビルドされたバージョンは、VS のものよりも約 13 倍遅いことに気付きました。これは と の実装に問題がto_string()ありreverse()ますか? 他の理由はありますか？

私が使用したコードはこちらです: https://github.com/pauljurczak/Benchmark-2/blob/master/benchmark.cpp

編集

問題を機能するように絞り込みましたstd::to_string()。MinGW では VS よりも約 16 倍遅くなります。テストには次のスニペットを使用しました。

int f(int N = 100000) {  
  int len = 0;

  for (int i = 0; i <= N; ++i) 
    len += to_string(i).length();

  return len;
}

Ubuntu で g++ 4.7.3 でコンパイルすると、パフォーマンスは VS2012 とほぼ同じです。

4

2 に答える 2

1

Visual Studio はif-condition を逆にすることができました:

if (digits != rDigits)
    continue;
else
    nMax = max(i*j, nMax);

しかし、それは推測にすぎません...

ちなみに、私はむしろ次のように書きます：

string rDigits(digits.rbegin(), digits.rend());

また、https://stackoverflow.com/a/17909430/1689664もご覧ください。アルゴリズムを最適化するためのアイデアが得られるかもしれません。

于 2013-07-28T22:43:59.337 に答える