db/d32/PmergeMe__count__ver_8cpp_source.html

#include "PmergeMe.hpp"

#include <algorithm> // for std::distance

#include <climits>

#include <cstdlib>

#include <utility>


// --- Orthodox Canonical Form & Constructor ---

PmergeMe::PmergeMe() : _comparisonCount(0) {}

PmergeMe::~PmergeMe() {}

PmergeMe::PmergeMe(const PmergeMe &src) { (void)src; }

PmergeMe &PmergeMe::operator=(const PmergeMe &rhs) {

    (void)rhs;

    return *this;

}


// --- Counter Methods ---

void PmergeMe::resetCounter() { _comparisonCount = 0; }

long PmergeMe::getComparisonCount() const { return _comparisonCount; }


// --- Timing Helper ---

long PmergeMe::getTimeStamp() {

    struct timeval tv;

    gettimeofday(&tv, NULL);

    return tv.tv_sec * 1000000 + tv.tv_usec;

}


// --- Custom Binary Search with Counter ---

// vector

std::vector<int>::iterator PmergeMe::counting_lower_bound(std::vector<int> &vec, int value) {

    std::vector<int>::iterator first = vec.begin();

    std::vector<int>::iterator last = vec.end();

    std::vector<int>::iterator it;

    std::iterator_traits<std::vector<int>::iterator>::difference_type count, step;

    count = std::distance(first, last);


    while (count > 0) {

        it = first;

        step = count / 2;

        std::advance(it, step);


        // ここで比較を行う

        _comparisonCount++;

        if (*it < value) {

            first = ++it;

            count -= step + 1;

        } else {

            count = step;

        }

    }

    return first;

}


// deque

std::deque<int>::iterator PmergeMe::counting_lower_bound(std::deque<int> &deq, int value) {

    std::deque<int>::iterator first = deq.begin();

    std::deque<int>::iterator last = deq.end();

    std::deque<int>::iterator it;

    std::iterator_traits<std::deque<int>::iterator>::difference_type count, step;

    count = std::distance(first, last);


    while (count > 0) {

        it = first;

        step = count / 2;

        std::advance(it, step);


        // ここで比較を行う

        _comparisonCount++;

        if (*it < value) {

            first = ++it;

            count -= step + 1;

        } else {

            count = step;

        }

    }

    return first;

}


// --- Vector Implementation (with Counter) ---

// void PmergeMe::mergeInsertSort(std::vector<int> &vec) {

//    if (vec.size() <= 1)

//        return;

//

//    // 1. Create pair, sort in each pair.

//    std::vector<std::pair<int, int> > pairs;

//    int straggler = -1;

//    bool hasStraggler = vec.size() % 2 != 0;

//    if (hasStraggler) {

//        straggler = vec.back();

//        vec.pop_back();

//    }

//

//    for (size_t i = 0; i < vec.size(); i += 2) {

//        _comparisonCount++; // Compair in pair.

//        if (vec[i] < vec[i + 1]) {

//            pairs.push_back(std::make_pair(vec[i + 1], vec[i]));

//        } else {

//            pairs.push_back(std::make_pair(vec[i], vec[i + 1]));

//        }

//    }

//

//    // 2. Recursively sort the sequence of larger elements in pairs (main chain)

//    std::vector<int> mainChain;

//    for (size_t i = 0; i < pairs.size(); ++i) {

//        mainChain.push_back(pairs[i].first);

//    }

//    mergeInsertSort(mainChain); // recursive call

//

//    // ... (Insertion logic) ...

//    // ヤコブスタール数を使った挿入ロジック

//    // この部分は簡略化せず、元のロジックをそのまま使います

//    // ただし、std::lower_boundを自前のものに置き換えます

//

//    // Find the first pend element to insert

//    int first_pend = -1;

//    for (size_t i = 0; i < pairs.size(); ++i) {

//        if (pairs[i].first == mainChain[0]) {

//            first_pend = pairs[i].second;

//            break;

//        }

//    }

//    if (first_pend != -1) {

//        mainChain.insert(mainChain.begin(), first_pend);

//    }

//

//    size_t lastInserted = 1;

//    for (size_t k = 2;; ++k) {

//        long jacobsthal_k = (1L << k) - ((k % 2 == 0) ? 1 : -1);

//        jacobsthal_k /= 3;

//

//        size_t insertCount = jacobsthal_k - lastInserted;

//        if (static_cast<size_t>(jacobsthal_k) > pairs.size()) {

//            insertCount = pairs.size() - lastInserted;

//        }

//

//        for (size_t i = 0; i < insertCount; ++i) {

//            size_t pairIndex = jacobsthal_k - i - 1;

//            if (pairIndex >= pairs.size() || pairIndex < 1)

//                continue;

//

//            int valueToInsert = pairs[pairIndex].second;

//            // std::lower_boundの代わりに自前の関数を使用

//            std::vector<int>::iterator it = counting_lower_bound(mainChain, valueToInsert);

//            mainChain.insert(it, valueToInsert);

//        }

//

//        lastInserted += insertCount;

//        if (lastInserted >= pairs.size())

//            break;

//    }

//

//    if (hasStraggler) {

//        std::vector<int>::iterator it = counting_lower_bound(mainChain, straggler);

//        mainChain.insert(it, straggler);

//    }

//

//    vec = mainChain;

//}


// Deque implementation is omitted for brevity, but would be modified similarly.

// void PmergeMe::mergeInsertSort(std::deque<int> &deq) {

//    if (deq.size() <= 1)

//        return;

//

//    // 1. Create pair, sort in each pair.

//    std::deque<std::pair<int, int> > pairs;

//    int straggler = -1;

//    bool hasStraggler = deq.size() % 2 != 0;

//    if (hasStraggler) {

//        straggler = deq.back();

//        deq.pop_back();

//    }

//

//    for (size_t i = 0; i < deq.size(); i += 2) {

//        _comparisonCount++; // Compair in pair.

//        if (deq[i] < deq[i + 1]) {

//            pairs.push_back(std::make_pair(deq[i + 1], deq[i]));

//        } else {

//            pairs.push_back(std::make_pair(deq[i], deq[i + 1]));

//        }

//    }

//

//    // 2. Recursively sort the sequence of larger elements in pairs (main chain)

//    std::deque<int> mainChain;

//    for (size_t i = 0; i < pairs.size(); ++i) {

//        mainChain.push_back(pairs[i].first);

//    }

//    mergeInsertSort(mainChain); // recursive call

//

//    // ... (Insertion logic) ...

//    // ヤコブスタール数を使った挿入ロジック

//    // この部分は簡略化せず、元のロジックをそのまま使います

//    // ただし、std::lower_boundを自前のものに置き換えます

//

//    // Find the first pend element to insert

//    int first_pend = -1;

//    for (size_t i = 0; i < pairs.size(); ++i) {

//        if (pairs[i].first == mainChain[0]) {

//            first_pend = pairs[i].second;

//            break;

//        }

//    }

//    if (first_pend != -1) {

//        mainChain.insert(mainChain.begin(), first_pend);

//    }

//

//    size_t lastInserted = 1;

//    for (size_t k = 2;; ++k) {

//        long jacobsthal_k = (1L << k) - ((k % 2 == 0) ? 1 : -1);

//        jacobsthal_k /= 3;

//

//        size_t insertCount = jacobsthal_k - lastInserted;

//        if (static_cast<size_t>(jacobsthal_k) > pairs.size()) {

//            insertCount = pairs.size() - lastInserted;

//        }

//

//        for (size_t i = 0; i < insertCount; ++i) {

//            size_t pairIndex = jacobsthal_k - i - 1;

//            if (pairIndex >= pairs.size() || pairIndex < 1)

//                continue;

//

//            int valueToInsert = pairs[pairIndex].second;

//            // std::lower_boundの代わりに自前の関数を使用

//            std::deque<int>::iterator it = counting_lower_bound(mainChain, valueToInsert);

//            mainChain.insert(it, valueToInsert);

//        }

//

//        lastInserted += insertCount;

//        if (lastInserted >= pairs.size())

//            break;

//    }

//

//    if (hasStraggler) {

//        std::deque<int>::iterator it = counting_lower_bound(mainChain, straggler);

//        mainChain.insert(it, straggler);

//    }

//

//    deq = mainChain;

//}


// The original sortAndCompare is not needed for this specific test.

// void PmergeMe::sortAndCompare(int argc, char **argv) {

//    (void)argc;

//    (void)argv;

//}


// #include "PmergeMe.hpp"

// #include <climits> // for LONG_MAX

// #include <cstdlib> // for strtol

// #include <utility> // for std::pair

//

//

// PmergeMe::PmergeMe() {}

//

// PmergeMe::~PmergeMe() {}

//

// PmergeMe::PmergeMe(const PmergeMe &src) { (void)src; }

//

// PmergeMe &PmergeMe::operator=(const PmergeMe &rhs) {

//    (void)rhs;

//    return *this;

//}

//

//

// long PmergeMe::getTimeStamp() {

//    struct timeval tv;

//    gettimeofday(&tv, NULL);

//    return tv.tv_sec * 1000000 + tv.tv_usec;

//}

//

//

// vector用のマージ挿入ソート

void PmergeMe::mergeInsertSort(std::vector<int> &vec) {

    if (vec.size() <= 1)

        return;


    // 1. ペアを作成し、各ペア内をソート

    std::vector<std::pair<int, int> > pairs;

    int straggler = -1;

    bool hasStraggler = vec.size() % 2 != 0;

    if (hasStraggler) {

        straggler = vec.back();

        vec.pop_back();

    }


    for (size_t i = 0; i < vec.size(); i += 2) {

        if (vec[i] < vec[i + 1]) {

            pairs.push_back(std::make_pair(vec[i + 1], vec[i]));

        } else {

            pairs.push_back(std::make_pair(vec[i], vec[i + 1]));

        }

    }


    // 2. ペアの大きい要素のシーケンス（main chain）を再帰的にソート

    std::vector<int> mainChain;

    for (size_t i = 0; i < pairs.size(); ++i) {

        mainChain.push_back(pairs[i].first);

    }

    mergeInsertSort(mainChain);


    // 3. main chainに小さい要素（pend elements）を挿入

    // まず、最初のペアの小さい要素を先頭に挿入

    for (size_t i = 0; i < pairs.size(); ++i) {

        if (pairs[i].first == mainChain[0]) {

            mainChain.insert(mainChain.begin(), pairs[i].second);

            break;

        }

    }


    // ヤコブスタール数を利用して最適な順序で挿入

    // C++98ではラムダや複雑なイテレータ操作が使えないため、インデックスベースで処理

    size_t lastInserted = 1;

    for (size_t k = 2;; ++k) {

        // ヤコブスタール数 J(k) を計算 (簡易的な方法)

        long jacobsthal_k = (1L << k) - ((k % 2 == 0) ? 1 : -1);

        jacobsthal_k /= 3;


        size_t insertCount = jacobsthal_k - lastInserted;

        if (static_cast<size_t>(jacobsthal_k) > pairs.size()) {

            insertCount = pairs.size() - lastInserted;

        }


        for (size_t i = 0; i < insertCount; ++i) {

            size_t pairIndex = jacobsthal_k - i - 1;

            if (pairIndex >= pairs.size())

                continue;


            int valueToInsert = pairs[pairIndex].second;

            std::vector<int>::iterator it = std::lower_bound(mainChain.begin(), mainChain.end(), valueToInsert);

            mainChain.insert(it, valueToInsert);

        }


        lastInserted += insertCount;

        if (lastInserted >= pairs.size())

            break;

    }


    // 4. はぐれた要素（straggler）があれば挿入

    if (hasStraggler) {

        std::vector<int>::iterator it = std::lower_bound(mainChain.begin(), mainChain.end(), straggler);

        mainChain.insert(it, straggler);

    }


    vec = mainChain;

}

//

//

void PmergeMe::mergeInsertSort(std::deque<int> &deq) {

    if (deq.size() <= 1)

        return;


    std::deque<std::pair<int, int> > pairs;

    int straggler = -1;

    bool hasStraggler = deq.size() % 2 != 0;

    if (hasStraggler) {

        straggler = deq.back();

        deq.pop_back();

    }


    for (size_t i = 0; i < deq.size(); i += 2) {

        if (deq[i] < deq[i + 1]) {

            pairs.push_back(std::make_pair(deq[i + 1], deq[i]));

        } else {

            pairs.push_back(std::make_pair(deq[i], deq[i + 1]));

        }

    }


    std::deque<int> mainChain;

    for (size_t i = 0; i < pairs.size(); ++i) {

        mainChain.push_back(pairs[i].first);

    }

    mergeInsertSort(mainChain);


    for (size_t i = 0; i < pairs.size(); ++i) {

        if (pairs[i].first == mainChain[0]) {

            mainChain.insert(mainChain.begin(), pairs[i].second);

            break;

        }

    }


    size_t lastInserted = 1;

    for (size_t k = 2;; ++k) {

        long jacobsthal_k = (1L << k) - ((k % 2 == 0) ? 1 : -1);

        jacobsthal_k /= 3;


        size_t insertCount = jacobsthal_k - lastInserted;

        if (static_cast<size_t>(jacobsthal_k) > pairs.size()) {

            insertCount = pairs.size() - lastInserted;

        }


        for (size_t i = 0; i < insertCount; ++i) {

            size_t pairIndex = jacobsthal_k - i - 1;

            if (pairIndex >= pairs.size())

                continue;


            int valueToInsert = pairs[pairIndex].second;

            std::deque<int>::iterator it = std::lower_bound(mainChain.begin(), mainChain.end(), valueToInsert);

            mainChain.insert(it, valueToInsert);

        }


        lastInserted += insertCount;

        if (lastInserted >= pairs.size())

            break;

    }


    if (hasStraggler) {

        std::deque<int>::iterator it = std::lower_bound(mainChain.begin(), mainChain.end(), straggler);

        mainChain.insert(it, straggler);

    }


    deq = mainChain;

}

//

//

void PmergeMe::sortAndCompare(int argc, char **argv) {

    std::vector<int> vec;

    std::deque<int> deq;


    // 1. 引数のパースと検証

    for (int i = 1; i < argc; ++i) {

        char *end;

        long val = std::strtol(argv[i], &end, 10);

        if (*end != '\0' || val <= 0 || val > INT_MAX) {

            throw std::invalid_argument("Error: Invalid input.");

        }

        vec.push_back(static_cast<int>(val));

        deq.push_back(static_cast<int>(val));

    }


    // 2. ソート前のシーケンスを表示

    std::cout << "Before: ";

    for (size_t i = 0; i < vec.size(); ++i) {

        std::cout << vec[i] << (i == vec.size() - 1 ? "" : " ");

    }

    std::cout << std::endl;


    // 3. vectorのソートと時間計測

    long startVec = getTimeStamp();

    mergeInsertSort(vec);

    long endVec = getTimeStamp();

    double timeVec = static_cast<double>(endVec - startVec);


    // 4. ソート後のシーケンスを表示

    std::cout << "After:  ";

    for (size_t i = 0; i < vec.size(); ++i) {

        std::cout << vec[i] << (i == vec.size() - 1 ? "" : " ");

    }

    std::cout << std::endl;


    // 5. dequeのソートと時間計測

    long startDeq = getTimeStamp();

    mergeInsertSort(deq);

    long endDeq = getTimeStamp();

    double timeDeq = static_cast<double>(endDeq - startDeq);


    // 6. 結果の表示

    std::cout << "Time to process a range of " << argc - 1 << " elements with std::vector : " << timeVec << " us"

              << std::endl;

    std::cout << "Time to process a range of " << argc - 1 << " elements with std::deque  : " << timeDeq << " us"

              << std::endl;

}

PmergeMe.hpp
マージ挿入ソートアルゴリズムを実装し、異なるコンテナでのパフォーマンスを比較するPmergeMeクラスを提供します。

std::advance
T advance(T... args)

algorithm

std::vector::back
T back(T... args)

std::vector::begin
T begin(T... args)

PmergeMe
マージ挿入ソート（フォード・ジョンソンアルゴリズム）を用いて数値シーケンスをソートするクラス。
Definition PmergeMe.hpp:38

PmergeMe::sortAndCompare
void sortAndCompare(int argc, char **argv)
コマンドライン引数をパースし、ソートを実行して結果を比較・表示します。
Definition PmergeMe.cpp:190

PmergeMe::mergeInsertSort
void mergeInsertSort(std::vector< int > &arr)
std::vectorに対してマージ挿入ソートを実行します。
Definition PmergeMe.cpp:58

PmergeMe::PmergeMe
PmergeMe()
デフォルトコンストラクタ。
Definition PmergeMe.cpp:37

PmergeMe::~PmergeMe
~PmergeMe()
デストラクタ。
Definition PmergeMe.cpp:39

climits

std::count
T count(T... args)

std::cout

cstdlib

std::deque

std::distance
T distance(T... args)

std::vector::end
T end(T... args)

std::endl
T endl(T... args)

std::vector::insert
T insert(T... args)

std::invalid_argument

std::iterator_traits

std::lower_bound
T lower_bound(T... args)

std::make_pair
T make_pair(T... args)

std::vector::pop_back
T pop_back(T... args)

std::vector::push_back
T push_back(T... args)

std::vector::size
T size(T... args)

std::strtol
T strtol(T... args)

utility

std::vector