为什么处理有序数组比无序数组快?

2014-6-4 11:51| 发布者: joejoe0332| 查看: 4234| 评论: 0|原作者: Jerry|来自: 伯乐在线

摘要: 由于某些怪异的原因，下面这段C++代码表现的异乎寻常—-当这段代码作用于有序数据时其速度可以提高将近6倍，这真是令人惊奇。

　　GManNickG 提问：

　　由于某些怪异的原因，下面这段C++代码表现的异乎寻常—-当这段代码作用于有序数据时其速度可以提高将近6倍，这真是令人惊奇。

#include 
#include 
#include 
 
int _tmain (int argc , _TCHAR * argv [])
{
        //Generate data
        const unsigned arraySize = 32768;
        int data[arraySize];
 
        for ( unsigned c = 0; c < arraySize; ++c)
              data[c] = std::rand() % 256;
 
        //!!! With this, the next loop runs faster
       std::sort(data, data + arraySize);
 
        //Test
        clock_t start = clock();
        long long sum = 0;
        for ( unsigned i = 0; i < 100000; ++i){
               //Primary loop
               for ( unsigned c = 0; c < arraySize; ++c){
                      if (data[c] >= 128)
                           sum += data[c];
              }
       }
        double eclapsedTime = static_cast<double >(clock() - start) / CLOCKS_PER_SEC;
 
       std::cout << eclapsedTime << std::endl;
       std::cout << "sum = " << sum << std::endl;
        return 0;
}

如果把 std::sort(data, data+arraySize) 去掉，这段代码耗时11.54秒。
对于有序数据，这段代码耗时1.93秒

　　起初我以为这可能是某一种语言或某一个编译器发生的异常的事件，后来我在java语言写了个例子，如下：

import java.util.Arrays;
import java.util.Random;
 
public class Test_Sorted_UnSorted_Array {
       public static void main(String[] args) {
             //Generate data
             int arraySize = 32768;
             int data[] = new int[arraySize];
 
            Random rnd = new Random(0);
             for( int c = 0; c
                  data[c] = rnd.nextInt()%256;
 
             //!!! With this, the next loop runs faster
            Arrays. sort(data);
 
             //Test
             long start = System. nanoTime();
             long sum = 0;
 
             for( int i=0; i<100000; ++i){
                   //Primary loop
                   for( int c = 0; c
                         if(data[c] >=128)
                              sum += data[c];
                  }
            }
 
            System. out.println((System. nanoTime() - start) / 1000000000.0);
            System. out.println( "sum = " + sum);
      }
}