当前位置:   article > 正文

寻找数组的最大值与最小值_数组找最大值和最小值

数组找最大值和最小值

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

 

一道很简单的题目,一般有下面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次比较,进行的所谓优化,得到的结果很可能与所期望的恰恰相反。

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

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/你好赵伟/article/detail/489182
推荐阅读
相关标签
  

闽ICP备14008679号