c++ - 如何在 C++ 中移动、交换和比较快速排序的计数

Question

我写了一些代码片段，以便在 C++ 中获取快速排序的移动、交换和比较计数，但它只给了我比较计数。在谷歌中没有找到好的答案。有人可以看看下面的代码并给我一些线索吗？非常感谢。

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <random>
#include <utility>
#include <iterator>
#include <cstdlib>
#include <chrono>
#include <inttypes.h>
#include <unistd.h>
uint64_t swapcnt, cmpcnt, defaultctorcnt, argctorcnt, copyctorcnt, assigncnt, movecnt;
std::chrono::high_resolution_clock::time_point start, end;

class MyData {
public:
    MyData();
    MyData(int n);
    MyData(const MyData& rhs) {argctorcnt++; data = rhs.data; }
    MyData(MyData&& rhs) {movecnt++; data = rhs.data; }
    MyData& operator=(const MyData& rhs) {copyctorcnt++; if(this==&rhs) return *this; data=rhs.data; return *this;}
    MyData& operator=(const MyData&& rhs) {movecnt++; if(this==&rhs) return *this; data=rhs.data; return *this;}
  bool operator==(const MyData& ohs) const {cmpcnt++; return data==ohs.data;}
    ~MyData();
    bool operator<(const MyData& oh) const;
    void set(int n){data=n;}
    void swap(MyData& rhs) {
        int tmp = data;
        data = rhs.data;
        rhs.data = tmp;
        swapcnt++;
    }
private:
    int data;
};

namespace std{
template<>
void swap(MyData& lhs, MyData& rhs) {
    swapcnt++;
    lhs.swap(rhs);
}
}

MyData::MyData() {
    data=0;defaultctorcnt++;
}

MyData::MyData(int n) {
    data=n; argctorcnt++;
}
MyData::~MyData() {

}
bool MyData::operator<(const MyData& rhs) const {
    cmpcnt++;
    return data<rhs.data;
}

template <class ForwardIt>
 void quicksort(ForwardIt first, ForwardIt last)
 {
    if(first == last) return;
    auto pivot = *std::next(first, std::distance(first,last)/2);
    ForwardIt middle1 = std::partition(first, last,
                         [pivot](const auto& em){ return em < pivot; });
    ForwardIt middle2 = std::partition(middle1, last,
                         [pivot](const auto& em){ return !(pivot < em); });
    quicksort(first, middle1);
    quicksort(middle2, last);
 }

void clearcnts() {
    swapcnt=0, cmpcnt=0; defaultctorcnt=0, argctorcnt=0, copyctorcnt=0, assigncnt=0; movecnt=0;
}

template<typename T>
void checkresult(std::string name, T& datasorted, T&  dataset2) {
    if(!std::equal(datasorted.begin(), datasorted.end(), dataset2.begin(), dataset2.end()))
        std::cout <<name << " sort result " << "not equal"<< std::endl;
    std::cout << name <<"\t compare count "
            <<std::dec<<std::setfill(' ')<<std::setw(10)<< cmpcnt
            << ", swap count " <<std::dec<<std::setfill(' ')<<std::setw(10)<< swapcnt
            <<", defaultctorcnt="<<std::dec<<std::setfill(' ')<<std::setw(2)<< defaultctorcnt
            <<", argctorcnt="<<std::dec<<std::setfill(' ')<<std::setw(10)<<argctorcnt
            <<", copyctorcnt=" <<std::dec<<std::setfill(' ')<<std::setw(10)<<copyctorcnt
            <<", assigncnt="<<std::dec<<std::setfill(' ')<<std::setw(2)<<assigncnt
            <<", movecnt="<<std::dec<<std::setfill(' ')<<std::setw(10)<<movecnt
            <<", total="<<std::dec<<std::setfill(' ')<<std::setw(10)<<swapcnt + cmpcnt + defaultctorcnt + argctorcnt + copyctorcnt + assigncnt+movecnt
            <<" in " <<std::setfill(' ')<<std::setw(6)<< std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " ms"<<std::endl;
}
void sortn(int cnt) {
    std::vector<MyData> dataset(cnt);
    srand (time(NULL));
    for(auto& data:dataset) // thanks to the answer from Rumburak
        data.set( rand());
    std::vector<MyData> datasorted=dataset;
    std::sort(datasorted.begin(), datasorted.end());
    {
        std::vector<MyData> dataset2=dataset;
        clearcnts();
    start = std::chrono::high_resolution_clock::now();
        quicksort(dataset2.begin(), dataset2.end());
    end = std::chrono::high_resolution_clock::now();
        checkresult("quicksort", datasorted, dataset2);
    }
}

int main(int argc, char* argv[]) {
    int cnt = 102400*54;
    if(argc>1)
        cnt=atoi(argv[1]);
    std::cout << "check compare and swap when sorting " <<cnt << " objects" << std::endl; //
    for(int i=0; i<1; i++) {
        std::cout << i << "th execution\n";
        sortn(cnt);
        usleep(rand()%37+5);
    }
    return 0;
}

构建代码:g++ -o qsortcnt -std=c++1y qsortcnt.cpp

在 Rumburak 的帮助下，现在程序似乎产生了合理的输出:程序输出:quicksort compare count 254998866, swap count 56669398, defaultctoctorcnt= 0, argtorcnt= 27611745, copytorcnt= 0, assigncnt= 0, movecnt= 0, total= 339280009 in 4794 ms

我在 Windows 7 上的 Cygwin 中使用 gcc 版本 5.2.0 (GCC)。

Answer 1

问题不在于你的计数方式。它在这里:

for(auto data:dataset) // This line is incorrect
    data.set( rand()); // dataset is not affected by this line

您在此处迭代数据集 的值。这意味着您正在修改 dataset 中值的拷贝。而 dataset 本身保持不变。

因此，您的quicksort 无事可做。所有值都是默认构造的并且相等。因此，dataset 已经排序。无需交换。

通过将 data 转换为引用，您可以得到想要的:

for(auto& data:dataset) // The & is required to take references
    data.set( rand());  // Now dataset is affected by this line

现在您将看到计数的合理值。

如果您不确定为什么需要 &，可以使用 great talk by Scott Meyers .它会告诉您有关该主题的所有信息，然后再告诉您一些。