All posts

遍历数组的背后

数组有序与否对遍历的影响

数组按行与按列遍历的差距

上面这篇文章写得很详细了,以下是总结与代码实现。

  • 数组有序与否影响的是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