ソートの基本的な基本操作を正しく測定する

Question

標準ライブラリのソート関数にテレメトリを追加しようとしています。スワップ、移動（スワップによって呼び出されるものを含む）の数、およびstd::sort()およびstd::stable_sort()関数の比較操作を数えたいと思います。

そうするためには、私は、次の手順を取っています：

1. は増分に比較関数オブジェクトのラッパーを作成し、私は
2. を測定する操作の数をカプセル化するための構造体を作成します。比較はstd::swap()機能を特化し、スワップ回数
3. は、カスタム移動機能を作成し、ステップ＃3
で作成し、専門のstd ::スワップ（）関数からそれを呼び出すインクリメント
4. を数えます
5. 最後に、私はstd::stable_sort()がどのスワップを起動する可能性はないので、正しいかもしれ次の出力を取得std::sort()とstd::stable_sort()を実行し、統計情報に

を収集します。

std::sort(): Moves: 68691, Swaps: 22897, Comparisons: 156959 
std::stable_sort(): Moves: 0, Swaps: 0, Comparisons: 183710 

しかし、私は交換した場合

• std::move()機能を特化し、移動カウント
をインクリメントする。これにより、上記＃4ステップ

出力は間違いなく右ではありませんstd::sort() 0移動し、持っている：さらに、私のコンパイラの（ダーウィン16.5.0にLLVM 8.1.0）がstd::stable_sort()の実装は移動して乗っている

std::sort(): Moves: 0, Swaps: 22897, Comparisons: 156959 
std::stable_sort(): Moves: 0, Swaps: 0, Comparisons: 183710 

を（）コール。だから、私はまた、出力で非ゼロの移動カウントを期待しています。

（/秒壊れた場合の抜粋に続く最初のケースのためのMVCE）以下の私のコードを見て、あなたはこれらの質問に答えることができるかどうかを確認してください：

1. がための私の全体的なアプローチですが合理的な統計情報の収集？
2. はなぜ第二ケースが壊れているとどのように私はそれを修正できますか？
3. （以下冗長作る）比較ファンクタのラッパー、少なくともSTD :: refの（）部分を簡素化する方法はありますか？（最初の場合）

基本コード：

namespace std { 
// Add specialization for std::move() 
template<> 
inline 
std::remove_reference<int>::type&& 
move<int>(int&& x) noexcept 
{ 
    test::__sort_stats.incr_count_moves(); 
    return static_cast<std::remove_reference<int>::type&&>(x); 
} 

// Invoke std::move() instead of test::move from the specialized std::swap() function 
template<> 
inline 
void 
swap<int>(int& a, int&b) noexcept(is_nothrow_move_constructible<int>::value 
            && is_nothrow_move_assignable<int>::value) 
{ 
    test::__sort_stats.incr_count_swaps(); 
    using std::move; 
    int temp(move(a)); 
    a = move(b); 
    b = move(temp); 
} 
} 

Answer 1

私はこの次のイゴールの提案を解決することができた：ここ

#include<iostream> 
#include<sstream> 
#include<vector> 
#include<cassert> 
#include<numeric> 
#include<algorithm> 

namespace test { 

// struct to store the count of swaps, moves, and comparisons 
struct sort_stats { 
    long long int __count_swaps; 
    long long int __count_moves; 
    long long int __count_comps; 

    void reset_stats() { __count_swaps = 0; __count_moves = 0; __count_comps = 0; } 

    void incr_count_swaps() { ++__count_swaps; } 
    void incr_count_moves() { ++__count_moves; } 
    void incr_count_comps() { ++__count_comps; } 

    std::string to_str() { 
     std::stringstream ss; 
     ss << "Moves: " << __count_moves 
      << ", Swaps: " << __count_swaps 
      << ", Comparisons: " << __count_comps; 
     return ss.str(); 
    } 
}; 

// static instance of stats 
static sort_stats __sort_stats; 

// my custom move template 
template<class T> 
inline 
typename std::remove_reference<T>::type&& 
move(T&& x) noexcept 
{ 
    test::__sort_stats.incr_count_moves(); 
    return static_cast<typename std::remove_reference<T>::type&&>(x); 
} 

// Wrapper for comparison functor 
template <class _Comp> 
class _WrapperComp 
{ 
    public: 
    typedef typename _Comp::result_type result_type; 
    typedef typename _Comp::first_argument_type arg_type; 

    _WrapperComp(_Comp comp) : __comp(comp) { } 
    result_type operator()(const arg_type& __x, const arg_type& __y) 
    { 
     test::__sort_stats.incr_count_comps(); 
     return __comp(__x, __y); 
    } 

    private: 
    _Comp __comp; 
}; 
} 

// Specialization of std::swap (for int type) 
namespace std { 
template<> 
inline 
void 
swap<int>(int& a, int&b) noexcept(is_nothrow_move_constructible<int>::value 
            && is_nothrow_move_assignable<int>::value) 
{ 
    test::__sort_stats.incr_count_swaps(); 
    using test::move; 
    int temp(move(a)); 
    a = move(b); 
    b = move(temp); 
} 
} 

using namespace test; 

int main() 
{ 
    const size_t SIZE = 10000; 
    auto v = std::vector<int>(SIZE); 
    std::iota(v.begin(), v.end(), 0); 

    auto wrapper_less = _WrapperComp<std::less<int>>(std::less<int>()); 
    auto ref_wrapper_less = std::ref(wrapper_less); 

    // Run std::sort() and gather stats 
    std::random_shuffle(v.begin(), v.end()); 
    std::cout << "std::sort(): "; 
    __sort_stats.reset_stats(); 
    std::sort(v.begin(), v.end(), ref_wrapper_less); 
    assert(std::is_sorted(v.begin(), v.end())); 
    std::cout << __sort_stats.to_str() << "\n"; 

    // Run std::stable_sort() and gather stats  
    std::random_shuffle(v.begin(), v.end()); 
    std::cout << "std::stable_sort(): "; 
    __sort_stats.reset_stats(); 
    std::stable_sort(v.begin(), v.end(), ref_wrapper_less); 
    assert(std::is_sorted(v.begin(), v.end())); 
    std::cout << __sort_stats.to_str() << "\n"; 

    return 0; 
} 

は、第二の場合の差分の抜粋であります（以前は使用していたintの代わりに）カスタムタイプを使用し、カスタムコピー/移動コンストラクタ/代入演算子をインスツルメントします。私はまた、機種指定のswap()関数を追加しました。これは、std::swap()関数テンプレートの特殊化を単純化しました。

は今、私は次のような出力が得られます。

std::sort(): Moves: 101606, Copies: 0, Swaps: 32821, Compares: 140451 
std::stable_sort(): Moves: 129687, Copies: 0, Swaps: 0, Compares: 121474 

移動コンストラクタ/代入演算子が定義されていない場合は、上記Moves数はCopiesの下に表示されます。

次のコードは動作します：

#include<iostream> 
#include<vector> 
#include<cassert> 
#include<numeric> 
#include<sstream> 
#include<algorithm> 

namespace test { 

struct sort_stats { 
    long long int __count_swaps; 
    long long int __count_moves; 
    long long int __count_copies; 
    long long int __count_comps; 

    void reset_stats() 
    { __count_swaps = __count_moves = __count_copies = __count_comps = 0; } 

    void incr_count_swaps() { ++__count_swaps; } 
    void incr_count_moves() { ++__count_moves; } 
    void incr_count_copies() { ++__count_copies; } 
    void incr_count_comps() { ++__count_comps; } 

    std::string to_str() { 
     std::stringstream ss; 
     ss << "Moves: " << __count_moves 
      << ", Copies: " << __count_copies 
      << ", Swaps: " << __count_swaps 
      << ", Compares: " << __count_comps; 
     return ss.str(); 
    } 
}; 

static sort_stats __sort_stats; 

struct my_type 
{ 
    int x; 

    // default constructor 
    my_type() = default; 

    // copy constructor 
    my_type(const my_type& other) : x (other.x) 
    { 
     __sort_stats.incr_count_copies(); 
    } 

    // move constructor 
    my_type(my_type&& other) noexcept : x (std::move(other.x)) 
    { 
     __sort_stats.incr_count_moves(); 
    } 

    // copy assignment operator 
    my_type& operator=(const my_type& other) 
    { 
     __sort_stats.incr_count_copies(); 
     x = other.x; 
     return *this; 
    } 

    // move assignment operator 
    my_type& operator=(my_type&& other) 
    { 
     __sort_stats.incr_count_moves(); 
     x = std::move(other.x); 
     return *this; 
    } 

    // '<' operator 
    bool operator<(const my_type& other) const 
    { 
     __sort_stats.incr_count_comps(); 
     return x < other.x; 
    } 

    // swap 
    void swap(my_type& other) 
    { 
     __sort_stats.incr_count_swaps(); 
     my_type temp(std::move(*this)); 
     *this = std::move(other); 
     other = std::move(temp); 
    } 

    // overload assignment operator for std::iota 
    my_type& operator=(const int& val) 
    { 
     x = val; 
     return *this; 
    } 

}; 

} // namespace test 

namespace std { 

using test::my_type; 

// std::swap specialized for test::my_type 
template<> 
inline 
void 
swap<my_type>(my_type& a, my_type& b) noexcept(is_nothrow_move_constructible<my_type>::value 
               && is_nothrow_move_assignable<my_type>::value) 
{ 
    a.swap(b); 
} 
} // namespace std 

using namespace test; 

int main() 
{ 
    const size_t SIZE = 10000; 

    auto v = std::vector<my_type>(SIZE); 
    std::iota(v.begin(), v.end(), 0); 

    std::random_shuffle(v.begin(), v.end()); 
    std::cout << "std::sort(): "; 
    __sort_stats.reset_stats(); 
    std::sort(v.begin(), v.end()); 
    std::cout << __sort_stats.to_str() << "\n"; 
    assert(std::is_sorted(v.begin(), v.end())); 

    std::random_shuffle(v.begin(), v.end()); 
    std::cout << "std::stable_sort(): "; 
    __sort_stats.reset_stats(); 
    std::stable_sort(v.begin(), v.end()); 
    std::cout << __sort_stats.to_str() << "\n"; 
    assert(std::is_sorted(v.begin(), v.end())); 

    return 0; 
}