寻找数组中的最小值和最大值——编程之美2.10

转自：http://blog.csdn.net/flyinghearts/article/details/6388834#

问题：寻找数组中的最小值和最大值。

 

一道很简单的题目，一般有下面4种解法：

1  遍历两次，每次分别找出最小值和最大值。

2  只遍历一次，每次取出的元素先与已找到的最小值比较，再与已找到的最大值比较。

3  每次取两个元素，将较小者与已找到的最小值比较，将较大者与已找到的最大值比较。

4  分治：将数组划分成两半，分别找出两边的最小值、最大值，则最小值、最大值分别是两边最小值的较小者、两边最大值的较大者。

 

这4种算法，哪种效率最高，哪种最低？

后两种算法只要进行1.5*N次比较，因而网上有不少解答都将它们列为最佳答案。但是，算法4用到了递归，而递归法函数调用的开销是很大的，这就注定了该算法的效率肯定不高。那么，算法3就是最高效的吗？还是用代码来验证吧。

 

后面的代码，对每种算法都实现了两个函数（假设数组长度为N）：

算法1：solve_1a与solve_1b，后者加入两个临时变量，编译器可以将变量储存在寄存器中，不用每次循环都要写内存。比较次数为2*N次。

算法2：solve_2a与solve_2b，前者每次循环必比较2次，后者最好情况下(递减数组)只要比较1次，但最差情况下（递增数组）则要比较2次，比较次数为：N到2 * N次。

算法3：solve_3a与solve_3b，前者每次循环取头尾两元素（从两头往中间取），后者取相邻两元素。比较次数为1.5 * N次。

算法4：solve_4a与solve_4b，后者返回一个结构（只有两个元素），编译器优化可以通过两个寄存器返回该结构，减少写内存次数。（检查gcc产生的汇编，确认有进行该优化）。比较次数为1.5 * N次。

 

下面是测试结果：（数组长度为6e7，每种算法测4次取平均值）

 

	所用时间（毫秒，GCC 4.5）					所用时间（毫秒，VC 2010）
函数名	递增	递减	乱序1	乱序2	乱序3	递增	递减	乱序1	乱序2	乱序3
1a 两次遍历	175	183	187	179	179	199	203	176	187	175
1b 两次遍历（优化）	175	179	171	171	172	183	234	175	187	172
2a 一次遍历	105	105	105	129	105	105	132	105	109	105
2b 一次遍历（优化）	105	90	105	109	105	109	109	105	113	105
3a 取头尾两元素	85	85	246	246	246	86	82	261	261	261
3b 取相邻两元素	93	101	238	242	238	93	101	258	257	253
4a 分治法	316	359	867	863	867	773	777	1554	1558	1558
4b 分治法（优化）	273	289	824	824	828	648	656	1347	1340	1339

编译参数：tdm-gcc 4.5.2-dw2:  g++ -O3 -s -Wextra –Wall     VC 2010:  cl /Ox /EHsc /nologo /W3

 

很明显，“分治”法的效率远低于其它3种算法。对前3种算法，将数组长度增加到1e8，并对十组随机数组进行测试，得到结果：

 

 

 

 

 

 

 

从上面的表和图可以看出，算法3在数组有序时，运行效率很高（但与算法2相差不大），而在乱序时，甚至比两次遍历都慢。乱序时：算法2效率最高，算法1次之，算法3效率最低。

算法2a和算法2b的效率差不多，有时算法2a的效率还略高。算法2a，每次循环都要比较2次，算法2b每次循环要比较1到2次，但由于前者的两次比较是无关的，后者的比较是相关的（第一次比较的结果决定是否进行第二次比较），在现代CPU“指令预测”等技术前，算法2a在某些情况下能比较算法2b更高效。

算法3的效率也不是绝对最差的，上面的随机数组是通过随机产生一些数得到，如果把它改为对数组的元素进行 “随机洗牌”，就得到下面的结果（所得的新数据与上面的数据和并，下图中第一、三列是上面的数据，第二、四列是改用“随机洗牌”后得到的新数据）：

 

 

 

 

 

 

从图可以看出，改用“随机洗牌”法得到乱序数组后，VC的结果没发生改变，GCC除了函数3a，结果也没改变，但是“3a一次取头尾两元素”却成为最高效的算法，但其效率和 “一次遍历取一个元素” 法，相差并不是太大。因而可以说，在单线程环境下，“一次遍历取一个元素”这个最容易想到的方法，反而是本题的最佳解法。

   

算法上的最优，并不一定是实际上的最优，快排和堆排序就是一个典型的例子，虽然快排最坏情况下的复杂度是O(N^2)，而堆排序始终是O(N lgN)，但实际运用中，一个好的快排实现一般都比堆排序快很多。何况这4种算法的复杂度还都是O(N)。为了在最坏情况下节省0.5 * N次比较，进行的所谓优化，得到的结果很可能与所期望的恰恰相反。

 

测试代码：

 

// by flyinghearts # qq.com

#include <algorithm>
#include <limits>
#include <vector>
#include <cstdio>

#define NOMINMAX 1
#include <windows.h>

#define TEST_CASE 1                  // 第0组还是第1组测试
#define RANDOM_SHUFFLE 0             // 乱序是否通过随机洗牌获得


#define TEST_RAND_POS 0              
const unsigned Pack = 4;     // 对某组数据连续测试Pack次，取平均值
const unsigned Rand_M = 5;   // 测试某个乱序数组的 Rand_M个子数组
#if ! TEST_CASE                      
 const unsigned Fix_M = 3;      // 固定数组长度时，测试Fix_M个乱序数组
 const unsigned Length = 6e7;   // 固定数组长度
#else
 const unsigned Fix_M = 10;  
 const unsigned Length = 1e8;  
#endif

#if _MSC_VER
  #pragma comment(lib, "winmm.lib")
#endif

inline unsigned mclock() { return timeGetTime(); }

void solve_1a(const int arr[], const size_t len, int& min_value, int& max_value)
{
  min_value = max_value = arr[0];
  for (const int *p = arr + 1; p < arr + len; ++p) 
    if (*p < min_value) min_value = *p;
  for (const int *p = arr + 1; p < arr + len; ++p) 
    if (*p > max_value) max_value = *p;
}


void solve_1b(const int arr[], const size_t len, int& min_value, int& max_value)
{
  int max_v = arr[0], min_v = arr[0];
  for (const int *p = arr + 1; p < arr + len; ++p) 
    if (*p < min_v) min_v = *p;
  for (const int *p = arr + 1; p < arr + len; ++p) 
    if (*p > max_v) max_v = *p;
  max_value = max_v;
  min_value = min_v;
}


void solve_2a(const int arr[], const size_t len, int& min_value, int& max_value)
{
  int max_v = arr[0], min_v = arr[0];
  for (const int *p = arr + 1; p < arr + len; ++p) {
    if (*p < min_v) min_v = *p;
    if (*p > max_v) max_v = *p;
  }
  max_value = max_v;
  min_value = min_v;
}

void solve_2b(const int arr[], const size_t len, int& min_value, int& max_value)
{
  int max_v = arr[0], min_v = arr[0];
  for (const int *p = arr + 1; p < arr + len; ++p) {
    if (*p < min_v) min_v = *p;
    else if (*p > max_v) max_v = *p;
  }
  max_value = max_v;
  min_value = min_v;
}

void solve_3a(const int arr[], const size_t len, int& min_value, int& max_value)
{
  // int min_v = std::numeric_limits<int>::max();
  // int max_v = std::numeric_limits<int>::min();
  // const int *low = arr - 1;
  // const int *high = arr + len;
  
  const int *low = arr;
  const int *high = arr + len - 1;
  int min_v, max_v;
  if (*low < *high) { min_v = *low; max_v = *high; }
  else { min_v = *high; max_v = *low; }

  while (++low <= --high) {
    if (*low <= *high) {
      if (*low < min_v) min_v = *low;
      if (*high > max_v) max_v = *high;
    } else {
      if (*high < min_v) min_v = *high;      
      if (*low > max_v) max_v = *low;
    }
  }
  max_value = max_v;
  min_value = min_v;
}


void solve_3b(const int arr[], const size_t len, int& min_value, int& max_value)
{
  // 长度为奇、偶数时，分别先取出1、2个元素。剩下的元素个数一定是偶数
  int min_v, max_v;
  size_t t = (len - 1u) % 2u;
  if (arr[0] <= arr[t]) { min_v = arr[0];  max_v = arr[t]; }
  else { min_v = arr[t];  max_v = arr[0]; }
  
  const int *p = arr + t + 1;
  while (p < arr + len) {      // p 和 arr + len 奇偶性始终相同
    int va = *p++;
    int vb = *p++;
    if (va <= vb) {
      if (va < min_v) min_v = va; 
      if (vb > max_v) max_v = vb;
    } else {
      if (vb < min_v) min_v = vb;
      if (va > max_v) max_v = va;
    }
  }
  
  max_value = max_v;
  min_value = min_v;
}

void solve_3c(const int arr[], const size_t len, int& min_value, int& max_value)
{
  // 长度为奇、偶数时，分别先取出1、2个元素。剩下的元素个数一定是偶数
  int min_v, max_v;
  size_t t = (len - 1u) % 2u;
  if (arr[0] <= arr[t]) { min_v = arr[0];  max_v = arr[t]; }
  else { min_v = arr[t];  max_v = arr[0]; }
  
  
  for (const int *p = arr + t + 1; p < arr + len; p += 2) { // p 和 arr + len 奇偶性始终相同
    int va = *p;
    int vb = *(p + 1);
    if (va <= vb) {
      if (va < min_v) min_v = va; 
      if (vb > max_v) max_v = vb;
    } else {
      if (vb < min_v) min_v = vb;
      if (va > max_v) max_v = va;
    }
  }
  
  max_value = max_v;
  min_value = min_v;
}


static void solve_4a_(const int arr[], size_t low, size_t high, int& min_value, int& max_value)
{
  if (high - low <= 1u) {
    if (arr[low] <= arr[high]) { min_value = arr[low];  max_value = arr[high]; }
    else { min_value = arr[high];  max_value = arr[low]; }
    return;
  }
  
  size_t mid = low + (high - low) / 2u;
  int min_left, max_left;
  solve_4a_(arr, low, mid, min_left, max_left);
  
  int min_right, max_right;
  solve_4a_(arr, mid + 1, high, min_right, max_right);

  min_value = std::min(min_left, min_right);
  max_value = std::max(max_left, max_right);
}


void solve_4a(const int arr[], const size_t len, int& min_value, int& max_value)
{
  return solve_4a_(arr, 0, len - 1u, min_value, max_value);
}


struct Range{
  int min_v, max_v;
  Range(int x, int y):min_v(x), max_v(y) {}
};


static Range solve_4b_(const int arr[], size_t low, size_t high)
{
  if (high - low <= 1) {
    if (arr[low] <= arr[high]) return Range(arr[low], arr[high]);
    return Range(arr[high], arr[low]);
  }
  size_t mid = low + (high - low) / 2u;
  Range left = solve_4b_(arr, low, mid);
  Range right = solve_4b_(arr, mid + 1, high);
  return Range(std::min(left.min_v, right.min_v),std::max(left.max_v, right.max_v));
}

void solve_4b(const int arr[], const size_t len, int& min_value, int& max_value)
{
  Range value =  solve_4b_(arr, 0, len - 1);
  min_value = value.min_v;
  max_value = value.max_v;
}

static void solve_4c_(const int *low, const int *high, int& min_value, int& max_value)
{
  if (high - low <= 1) {
    if (*low <= *high)  { min_value = *low; max_value = *high; }
    else { min_value = *high; max_value = *low; }
return;
  }
  const int *mid = low + (high - low) / 2u;
  int min_left, max_left;
  solve_4c_(low, mid, min_left, max_left);
  
  int min_right, max_right;
  solve_4c_(mid + 1, high, min_right, max_right);
  
  min_value = std::min(min_left, min_right);
  max_value = std::max(max_left, max_right);
}


void solve_4c(const int arr[], const size_t len, int& min_value, int& max_value)
{
  return solve_4c_(arr, arr + len - 1, min_value, max_value);
}


static Range solve_4d_(const int *low, const int *high)
{
  if (high - low <= 1) {
    if (*low <= *high) return Range(*low, *high);
    return Range(*high, *low);
  }
  const int* mid = low + (high - low) / 2u;
  Range left = solve_4d_(low, mid);
  Range right = solve_4d_(mid + 1, high);
  return Range(std::min(left.min_v, right.min_v),std::max(left.max_v, right.max_v));
}

void solve_4d(const int arr[], const size_t len, int& min_value, int& max_value)
{
  Range value =  solve_4d_(arr, arr + len - 1);
  min_value = value.min_v;
  max_value = value.max_v;
}




template<typename T>
void run_test(T arr[], size_t len, int input[], size_t input_len)
{
  int min_value, max_value;
  for (size_t i = 0; i < len; ++i) {
    printf("%d %-20s  ", i, arr[i].str);
    unsigned ta = mclock();
    for (size_t j = Pack; j != 0; --j)
      arr[i].func(input, input_len, min_value, max_value);
    ta = mclock() - ta;
    printf("min/max: %d/%d   elapsed: %u ms/n", min_value, max_value, ta / Pack);
  }
  printf("/n");
}

struct Func {
  void (*func)(const int arr[], const size_t len, int& min_value, int& max_value);
  const char *str; 
}; 
  
struct Generator {
  int operator()() const { return (rand() << 15) + rand(); }
};
  
void test()
{
  const size_t N = Length;
  if (Fix_M == 0 || N < 100) return;
  const Func func[] = {
    { solve_1a, " 1a 两次遍历" },
    { solve_1b, " 1b 两次遍历（优化）" },
    { solve_2a, " 2a 一次遍历" },
    { solve_2b, " 2b 一次遍历（优化）" },
    { solve_3a, " 3a 取头尾两元素" },
    { solve_3b, " 3b 取相邻两元素" },
    // { solve_3c, " 3c 取相邻两元素2" },
#if ! TEST_CASE
    { solve_4a, " 4a 分治法" },
    { solve_4b, " 4b 分治法（优化）" }, 
    // { solve_4c, " 4c 分治法2" },             //
    // { solve_4d, " 4d 分治法（优化2）" },     // 用指针，速度会稍快点
#endif

  };
  
  const size_t func_len = sizeof(func) / sizeof(func[0]);
  std::vector<int> src(N);
  for (size_t i = 0; i < N; ++i) src[i] = i; 
  
#if ! TEST_CASE  
  printf(" 递增  pos: 0  len:%u/n", N);
  run_test(func, func_len, &src[0], N);
  for (size_t i = 0; i < N; ++i) src[i] = N - i; 
  printf(" 递减  pos: 0  len:%u/n", N);
  run_test(func, func_len, &src[0], N);
#endif  
  
  // srand(time(NULL));
  
  for (unsigned i = 0; i < Fix_M; ++i) {
  #if RANDOM_SHUFFLE
    std::random_shuffle(src.begin(), src.end());
  #else
    std::generate(src.begin(), src.end(), Generator());
  #endif
    printf (" 乱序%d pos: 0  len %u/n", i + 1, N);
    run_test(func, func_len, &src[0], N);
  }
 
#if TEST_RAND_POS 
  const unsigned sub_len = N / 4u;
  const unsigned max_pos = N  - sub_len;
  for (unsigned i = 0; i < Rand_M; ++i) {
    size_t pos = rand() % max_pos;
    printf (" 乱序 pos: %u   len %u/n", pos, sub_len);
    run_test(func, func_len, &src[pos], sub_len);  
  }
#endif  

}


int main()
{
  const HANDLE handle = GetCurrentProcess();
  SetPriorityClass(handle, REALTIME_PRIORITY_CLASS);
  SYSTEM_INFO info;
  GetSystemInfo(&info);
  const int num = info.dwNumberOfProcessors;
  if (num > 1) SetProcessAffinityMask(handle, num); 
  test();
}