雁过无痕

下面是测试结果：（数组长度为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次比较，进行的所谓优化，得到的结果很可能与所期望的恰恰相反。

找出数组的最小值和最大值
  1
  2// www.cnblogs.com/flyinghearts     flyinghearts # qq.com
  3
  4#include <algorithm>
  5#include <limits>
  6#include <vector>
  7#include <cstdio>
  8
  9#define NOMINMAX 1
 10#include <windows.h>
 11
 12#define TEST_CASE 1                  // 第0组还是第1组测试
 13#define RANDOM_SHUFFLE 0             // 乱序是否通过随机洗牌获得
 14
 15
 16#define TEST_RAND_POS 0              
 17const unsigned Pack = 4;     // 对某组数据连续测试Pack次，取平均值
 18const unsigned Rand_M = 5;   // 测试某个乱序数组的 Rand_M个子数组
 19#if ! TEST_CASE                      
 20 const unsigned Fix_M = 3;      // 固定数组长度时，测试Fix_M个乱序数组
 21 const unsigned Length = 6e7;   // 固定数组长度
 22#else
 23 const unsigned Fix_M = 10;  
 24 const unsigned Length = 1e8;  
 25#endif
 26
 27#if _MSC_VER
 28  #pragma comment(lib, "winmm.lib")
 29#endif
 30
 31inline unsigned mclock() { return timeGetTime(); }
 32
 33void solve_1a(const int arr[], const size_t len, int& min_value, int& max_value)
 34{
 35  min_value = max_value = arr[0];
 36  for (const int *p = arr + 1; p < arr + len; ++p) 
 37    if (*p < min_value) min_value = *p;
 38  for (const int *p = arr + 1; p < arr + len; ++p) 
 39    if (*p > max_value) max_value = *p;
 40}
 41
 42
 43void solve_1b(const int arr[], const size_t len, int& min_value, int& max_value)
 44{
 45  int max_v = arr[0], min_v = arr[0];
 46  for (const int *p = arr + 1; p < arr + len; ++p) 
 47    if (*p < min_v) min_v = *p;
 48  for (const int *p = arr + 1; p < arr + len; ++p) 
 49    if (*p > max_v) max_v = *p;
 50  max_value = max_v;
 51  min_value = min_v;
 52}
 53
 54
 55void solve_2a(const int arr[], const size_t len, int& min_value, int& max_value)
 56{
 57  int max_v = arr[0], min_v = arr[0];
 58  for (const int *p = arr + 1; p < arr + len; ++p) {
 59    if (*p < min_v) min_v = *p;
 60    if (*p > max_v) max_v = *p;
 61  }
 62  max_value = max_v;
 63  min_value = min_v;
 64}
 65
 66void solve_2b(const int arr[], const size_t len, int& min_value, int& max_value)
 67{
 68  int max_v = arr[0], min_v = arr[0];
 69  for (const int *p = arr + 1; p < arr + len; ++p) {
 70    if (*p < min_v) min_v = *p;
 71    else if (*p > max_v) max_v = *p;
 72  }
 73  max_value = max_v;
 74  min_value = min_v;
 75}
 76
 77void solve_3a(const int arr[], const size_t len, int& min_value, int& max_value)
 78{
 79  // int min_v = std::numeric_limits<int>::max();
 80  // int max_v = std::numeric_limits<int>::min();
 81  // const int *low = arr - 1;
 82  // const int *high = arr + len;
 83  
 84  const int *low = arr;
 85  const int *high = arr + len - 1;
 86  int min_v, max_v;
 87  if (*low < *high) { min_v = *low; max_v = *high; }
 88  else { min_v = *high; max_v = *low; }
 89
 90  while (++low <= --high) {
 91    if (*low <= *high) {
 92      if (*low < min_v) min_v = *low;
 93      if (*high > max_v) max_v = *high;
 94    } else {
 95      if (*high < min_v) min_v = *high;      
 96      if (*low > max_v) max_v = *low;
 97    }
 98  }
 99  max_value = max_v;
100  min_value = min_v;
101}
102
103
104void solve_3b(const int arr[], const size_t len, int& min_value, int& max_value)
105{
106  // 长度为奇、偶数时，分别先取出1、2个元素。剩下的元素个数一定是偶数
107  int min_v, max_v;
108  size_t t = (len - 1u) % 2u;
109  if (arr[0] <= arr[t]) { min_v = arr[0];  max_v = arr[t]; }
110  else { min_v = arr[t];  max_v = arr[0]; }
111  
112  const int *p = arr + t + 1;
113  while (p < arr + len) {      // p 和 arr + len 奇偶性始终相同
114    int va = *p++;
115    int vb = *p++;
116    if (va <= vb) {
117      if (va < min_v) min_v = va; 
118      if (vb > max_v) max_v = vb;
119    } else {
120      if (vb < min_v) min_v = vb;
121      if (va > max_v) max_v = va;
122    }
123  }
124  
125  max_value = max_v;
126  min_value = min_v;
127}
128
129void solve_3c(const int arr[], const size_t len, int& min_value, int& max_value)
130{
131  // 长度为奇、偶数时，分别先取出1、2个元素。剩下的元素个数一定是偶数
132  int min_v, max_v;
133  size_t t = (len - 1u) % 2u;
134  if (arr[0] <= arr[t]) { min_v = arr[0];  max_v = arr[t]; }
135  else { min_v = arr[t];  max_v = arr[0]; }
136  
137  
138  for (const int *p = arr + t + 1; p < arr + len; p += 2) { // p 和 arr + len 奇偶性始终相同
139    int va = *p;
140    int vb = *(p + 1);
141    if (va <= vb) {
142      if (va < min_v) min_v = va; 
143      if (vb > max_v) max_v = vb;
144    } else {
145      if (vb < min_v) min_v = vb;
146      if (va > max_v) max_v = va;
147    }
148  }
149  
150  max_value = max_v;
151  min_value = min_v;
152}
153
154
155static void solve_4a_(const int arr[], size_t low, size_t high, int& min_value, int& max_value)
156{
157  if (high - low <= 1u) {
158    if (arr[low] <= arr[high]) { min_value = arr[low];  max_value = arr[high]; }
159    else { min_value = arr[high];  max_value = arr[low]; }
160    return;
161  }
162  
163  size_t mid = low + (high - low) / 2u;
164  int min_left, max_left;
165  solve_4a_(arr, low, mid, min_left, max_left);
166  
167  int min_right, max_right;
168  solve_4a_(arr, mid + 1, high, min_right, max_right);
169
170  min_value = std::min(min_left, min_right);
171  max_value = std::max(max_left, max_right);
172}
173
174
175void solve_4a(const int arr[], const size_t len, int& min_value, int& max_value)
176{
177  return solve_4a_(arr, 0, len - 1u, min_value, max_value);
178}
179
180
181struct Range{
182  int min_v, max_v;
183  Range(int x, int y):min_v(x), max_v(y) {}
184};
185
186
187static Range solve_4b_(const int arr[], size_t low, size_t high)
188{
189  if (high - low <= 1) {
190    if (arr[low] <= arr[high]) return Range(arr[low], arr[high]);
191    return Range(arr[high], arr[low]);
192  }
193  size_t mid = low + (high - low) / 2u;
194  Range left = solve_4b_(arr, low, mid);
195  Range right = solve_4b_(arr, mid + 1, high);
196  return Range(std::min(left.min_v, right.min_v),std::max(left.max_v, right.max_v));
197}
198
199void solve_4b(const int arr[], const size_t len, int& min_value, int& max_value)
200{
201  Range value =  solve_4b_(arr, 0, len - 1);
202  min_value = value.min_v;
203  max_value = value.max_v;
204}
205
206static void solve_4c_(const int *low, const int *high, int& min_value, int& max_value)
207{
208  if (high - low <= 1) {
209    if (*low <= *high)  { min_value = *low; max_value = *high; }
210    else { min_value = *high; max_value = *low; }
211    return;
212  }
213  const int *mid = low + (high - low) / 2u;
214  int min_left, max_left;
215  solve_4c_(low, mid, min_left, max_left);
216  
217  int min_right, max_right;
218  solve_4c_(mid + 1, high, min_right, max_right);
219  
220  min_value = std::min(min_left, min_right);
221  max_value = std::max(max_left, max_right);
222}
223
224
225void solve_4c(const int arr[], const size_t len, int& min_value, int& max_value)
226{
227  return solve_4c_(arr, arr + len - 1, min_value, max_value);
228}
229
230
231static Range solve_4d_(const int *low, const int *high)
232{
233  if (high - low <= 1) {
234    if (*low <= *high) return Range(*low, *high);
235    return Range(*high, *low);
236  }
237  const int* mid = low + (high - low) / 2u;
238  Range left = solve_4d_(low, mid);
239  Range right = solve_4d_(mid + 1, high);
240  return Range(std::min(left.min_v, right.min_v),std::max(left.max_v, right.max_v));
241}
242
243void solve_4d(const int arr[], const size_t len, int& min_value, int& max_value)
244{
245  Range value =  solve_4d_(arr, arr + len - 1);
246  min_value = value.min_v;
247  max_value = value.max_v;
248}
249
250
251
252
253template<typename T>
254void run_test(T arr[], size_t len, int input[], size_t input_len)
255{
256  int min_value, max_value;
257  for (size_t i = 0; i < len; ++i) {
258    printf("%d %-20s  ", i, arr[i].str);
259    unsigned ta = mclock();
260    for (size_t j = Pack; j != 0; --j)
261      arr[i].func(input, input_len, min_value, max_value);
262    ta = mclock() - ta;
263    printf("min/max: %d/%d   elapsed: %u ms\n", min_value, max_value, ta / Pack);
264  }
265  printf("\n");
266}
267
268struct Func {
269  void (*func)(const int arr[], const size_t len, int& min_value, int& max_value);
270  const char *str; 
271}; 
272  
273struct Generator {
274  int operator()() const { return (rand() << 15) + rand(); }
275};
276  
277void test()
278{
279  const size_t N = Length;
280  if (Fix_M == 0 || N < 100) return;
281  const Func func[] = {
282    { solve_1a, " 1a 两次遍历" },
283    { solve_1b, " 1b 两次遍历（优化）" },
284    { solve_2a, " 2a 一次遍历" },
285    { solve_2b, " 2b 一次遍历（优化）" },
286    { solve_3a, " 3a 取头尾两元素" },
287    { solve_3b, " 3b 取相邻两元素" },
288    // { solve_3c, " 3c 取相邻两元素2" },
289#if ! TEST_CASE    
290    { solve_4a, " 4a 分治法" },
291    { solve_4b, " 4b 分治法（优化）" }, 
292    // { solve_4c, " 4c 分治法2" },             //
293    // { solve_4d, " 4d 分治法（优化2）" },     // 用指针，速度会稍快点
294#endif
295
296  };
297  
298  const size_t func_len = sizeof(func) / sizeof(func[0]);
299  std::vector<int> src(N);
300  for (size_t i = 0; i < N; ++i) src[i] = i; 
301  
302#if ! TEST_CASE      
303  printf(" 递增  pos: 0  len:%u\n", N);
304  run_test(func, func_len, &src[0], N);
305  for (size_t i = 0; i < N; ++i) src[i] = N - i; 
306  printf(" 递减  pos: 0  len:%u\n", N);
307  run_test(func, func_len, &src[0], N);
308#endif  
309  
310  // srand(time(NULL));
311  
312  for (unsigned i = 0; i < Fix_M; ++i) {
313  #if RANDOM_SHUFFLE
314    std::random_shuffle(src.begin(), src.end());
315  #else    
316    std::generate(src.begin(), src.end(), Generator());
317  #endif    
318    printf (" 乱序%d pos: 0  len %u\n", i + 1, N);
319    run_test(func, func_len, &src[0], N);
320  }
321 
322#if TEST_RAND_POS 
323  const unsigned sub_len = N / 4u;
324  const unsigned max_pos = N  - sub_len;
325  for (unsigned i = 0; i < Rand_M; ++i) {
326    size_t pos = rand() % max_pos;
327    printf (" 乱序 pos: %u   len %u\n", pos, sub_len);
328    run_test(func, func_len, &src[pos], sub_len);  
329  }
330#endif  
331
332}
333
334
335int main()
336{
337  const HANDLE handle = GetCurrentProcess();
338  SetPriorityClass(handle, REALTIME_PRIORITY_CLASS);
339  SYSTEM_INFO info;
340  GetSystemInfo(&info);
341  const int num = info.dwNumberOfProcessors;
342  if (num > 1) SetProcessAffinityMask(handle, num); 
343  test();
344}
345
346