我写了一些代码片段以便在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。它会告诉您所有您需要了解的有关该主题的知识,然后告诉您一些知识。