我写了一些代码片段以便在C ++中获得对quicksort的移动,交换和比较计数,但是它只给了我比较计数。在Google中找不到合适的答案。有人可以看看下面的代码并给我一些提示吗?非常感谢。

#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比较计数254998866,交换计数56669398,defaultctorcnt = 0,argctorcnt = 27611745,copyctorcnt = 0,assigncnt = 0,movecnt = 0,总数= 339280009 in 4794 ms

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

最佳答案

问题不在于您的计算方式。是这里:

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


您正在此处遍历dataset的值。这意味着您正在修改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。它会告诉您所有您需要了解的有关该主题的知识,然后告诉您一些知识。

09-10 04:57
查看更多