Powers of 10のテーブル検索

Question

私は、計算速度が最も重要なC++プロジェクトに取り組んでいます。私が切ることができるときはいつでも、切るべきです。実行可能ファイルとメモリ使用量の最終的なサイズはであり、重要な意味はです。

言われているように、10の累乗の事前計算ルックアップテーブルを作成することは有益でしょうか？私はこの単純化機能持っているとしたら、例えば：

double powTen(int exponent) { 
    return pow(10, exponent); 
} 

を私はテーブルルックアップでpow()を交換した場合には、パフォーマンスの（小さな）の増加を持っていますか？それは価値があるのだろうか？ pow()関数はかなり複雑でなければならないようです。また、GCCはこれに対して特別な最適化をしていますか？

Answer 1

テーブルルックアップは、ほとんどの場合パフォーマンスが良いです。したがって、これをボトルネックと見なした場合、テーブルを生成するテンプレートを実装する際に時間を使います。しかし、測定します。パフォーマンスは、現代のコンピュータでは変な獣です。決して信じられない方向に進むことができます。

コンパイルタイムテーブルの生成を実装する時間が、実際には非常に短いと予想しました。しかし、Visual C++ 2015は少なくとも古いアップデート2の時点では、クラス内でconstexpr std::arrayと全く幸せではないことが判明しました。しかし、最終的には、生の配列が機能しました。 MinGWのgで++ 6.3.0およびVisual C++ 2015でコンパイル

コード、アップデート2：

#include <stddef.h>  // size_t, ptrdiff_t 
#include <utility>  // std::(make_index_sequence,) 

namespace my { 
    using std::make_index_sequence; 
    using std::index_sequence; 

    using Size = ptrdiff_t; 

    template< Size n, class Item > 
    using raw_array_of_ = Item[n]; 

    template< class Item, size_t n > 
    constexpr 
    auto n_items_of(raw_array_of_<n, Item>&) 
     -> Size 
    { return n; } 

    namespace impl { 
     constexpr 
     auto compile_time_pow_of_10(int const n) 
      -> double 
     { return (n == 0? 1.0 : 10.0*compile_time_pow_of_10(n - 1)); } 

     template< size_t... indices > 
     struct Powers_of_10_ 
     { 
      static constexpr size_t      n  = sizeof...(indices); 
      static constexpr raw_array_of_<n, double> table = 
      { 
       compile_time_pow_of_10(indices)... 
      }; 

      constexpr 
      Powers_of_10_() {} 
     }; 

     template< size_t... indices > 
     constexpr 
     raw_array_of_<Powers_of_10_<indices...>::n, double> 
      Powers_of_10_<indices...>::table; 

     template< size_t... indices, int n = sizeof...(indices) > 
     constexpr 
     auto power_of_10_table_helper(index_sequence<indices...>) 
      -> const raw_array_of_<n, double>& 
     { return Powers_of_10_<indices...>::table; } 
    } // namespace impl 

    template< int n > 
    constexpr 
    auto power_of_10_table() 
     -> const raw_array_of_<n, double>& 
    { return impl::power_of_10_table_helper(make_index_sequence<n>()); } 

} // namespace my 

#include <iostream> 
using namespace std; 
auto main() 
    -> int 
{ 
    int const n = 7; 
    constexpr auto& pow_10 = my::power_of_10_table<n>(); 

    cout << n << " powers of 10:\n"; 
    cout << fixed; cout.precision(0); 
    for(int i = 0; i < n; ++i) 
    { 
     cout << pow_10[i] << "\n"; 
    } 
} 

---

テンプレートコードがポートに困難であり得ます。ウィジェット：Visual C++ 2015は上記のコードでstd::arrayを受け入れないため、代わりにraw配列を使用するように書き直す必要があります。また、通常は過度に長くて暗号化されたコンパイル診断のために、維持することも困難です。

適度に速い積算電力機能は、フォームX^{（2 N）}の累乗の積として電力を発現することによって定義することができます。例えば、X = X ⋅X ⋅ X、及びX、すなわち2,8のこれらのより基本的な力、および32、缶繰り返し二乗することによって計算される。x。これにより、指数部の線形から指数部の対数への乗算回数が減少します。

コード：

#include <stddef.h>  // size_t, ptrdiff_t 

namespace my { 
    using Size = ptrdiff_t; 

    template< Size n, class Item > 
    using raw_array_of_ = Item[n]; 

    namespace impl { 
     auto positive_integral_power_of(const double x, const int n) 
     { 
      double result = 1.0; 
      double power = x; 
      for(unsigned exp = n; ;) 
      { 
       if((exp & 1) != 0) 
       { 
        result *= power; 
       } 
       exp >>= 1; 
       if(exp == 0) 
       { 
        break; 
       } 
       power *= power; 
      } 
      return result; 
     } 
    } // namespace impl 

    auto integral_power_of(const double x, const int n) 
     -> double 
    { 
     return 
      n > 0? 
       impl::positive_integral_power_of(x, n) : 
      n < 0? 
       1.0/impl::positive_integral_power_of(x, -n) : 
      1.0; 
    } 
} // namespace my 

#include <iostream> 
using namespace std; 
auto main() 
    -> int 
{ 
    int const n = 7; 
    cout << n << " powers of 10:\n"; 
    cout << fixed; cout.precision(0); 
    for(int i = 0; i < n; ++i) 
    { 
     cout << my::integral_power_of(10, i) << "\n"; 
    } 
} 

Answer 2

この機能はそれほど大丈夫ですか？そうであれば、期待値の事前計算が良いでしょう。

また、部分的にビルドされたテーブルを使用して、使用法でビルドすることもできます。最初に10^5を計算してテーブルに保存し、次回テーブルから取得するようにします。

テーブルの使用は、関数を呼び出すよりも優れていますが、最初に何度も呼び出すか、同じパラメータを何度も送信することで、最初に関数を呼び出すことになりません大きな時間を費やした後、まったく使用しないと、これは最も小さなビットで最適化するという最初の意図を崩してしまいます。

Answer 3

あなたはループを使って、もう少し効率的に機能させることができます：

double powerTen(int exponent) 
{ 
    double result = 1.0; 
    for (int i = 0; i < exponent; ++i) 
    { 
    result = result * 10.0; 
    } 
    return result; 
} 

ループの利点は、あなたがpow関数に関数呼び出しのオーバーヘッドを削除することです。それほど節約できない、IMO。

double powerTen(int exponent) 
{ 
    static const double values[] = {1.0, 10.0, 100.0, 1000.0}; 
    return values[exponent]; 
} 

あなたは、実行時間のためのメモリ空間を取引されています

代替は、テーブルルックアップです。
また、負の指数を扱うだけでなく、配列のオーバーフローチェックを追加することもできます。