上面这篇文章写得很详细了,以下是总结与代码实现。
- 数组有序与否影响的是CPU的动态预测,有序的数组动态预测准确度很高。
#include<iostream>
#include<vector>
#include<ctime>
#include<algorithm>
#define SIZE 1e8
int calc(const std::vector<int> &q){
int a = 0 , b = 0 , len = q.size() ;
for(int i = 0 ; i < len ; i++){
if(q[i] < 500) a++ ;
else b++ ;
}
return a - b ;
}
int main()
{
std::vector<int> q ;
for(int i = 0 ; i < SIZE ; i++){
q.push_back(rand() % 1000) ; //无序数组
// q.push_back(i) ; //有序数组
}
clock_t start = clock() ;
calc(q) ;
clock_t end = clock() ;
double cost = (double) (end - start) / CLOCKS_PER_SEC ;
std::printf("Time cost : %.3fs\n" , cost) ;
//After sort
std::sort(q.begin() , q.end() ) ;
clock_t start1 = clock() ;
calc(q) ;
clock_t end1 = clock() ;
double cost1 = (double) (end1 - start1) / CLOCKS_PER_SEC ;
std::printf("Time cost after sort : %.3fs\n" , cost1) ;
return 0 ;
}
Time cost : 0.570s
Time cost after sort : 0.129s