Задача: Последовательный поиск и его оптимизации
Исходник: Тест производительности разных версий последовательного поиска, язык: C# [code #61, hits: 10047]
автор: this [добавлен: 21.02.2006]
  1. using System;
  2. using System.Diagnostics;
  3. using System.Net;
  4.  
  5.  
  6. class SSearchTest
  7. {
  8. public int SSearch(int[] x, int t)
  9. {
  10. for (int i = 0; i < x.Length; i++)
  11. {
  12. if (x[i] == t)
  13. {
  14. return i;
  15. }
  16. }
  17. return -1;
  18. }
  19.  
  20. public int SSearch2(int[] x, int t)
  21. {
  22. int size = x.Length;
  23.  
  24. // Временно сохраняем последний
  25. int hold = x[size-1];
  26.  
  27. /* Если последний элемент искомый
  28. * то это нужно проверять сразу
  29. */
  30. if (hold == t) return size - 1;
  31.  
  32. x[size - 1] = t;
  33.  
  34. int i = 0;
  35. while (true)
  36. {
  37. if (x[i] == t) break;
  38. i++;
  39. }
  40.  
  41. // Восстанавливаем значение последнего
  42. x[size - 1] = hold;
  43.  
  44. if (i == size-1)
  45. {
  46. return -1;
  47. }
  48. return i;
  49. }
  50.  
  51. public int SSearch3(int[] x, int t)
  52. {
  53. int size = x.Length;
  54.  
  55. // Временно сохраняем последний
  56. int hold = x[size - 1];
  57.  
  58. /* Если последний элемент искомый
  59. * то это нужно проверять сразу
  60. */
  61. if (hold == t) return size - 1;
  62.  
  63. x[size - 1] = t;
  64.  
  65. int i = 0;
  66. while (true)
  67. {
  68. if (x[i] == t) break;
  69. if (x[i + 1] == t) { i += 1; break; }
  70. if (x[i + 2] == t) { i += 2; break; }
  71. if (x[i + 3] == t) { i += 3; break; }
  72. if (x[i + 4] == t) { i += 4; break; }
  73. if (x[i + 5] == t) { i += 5; break; }
  74. if (x[i + 6] == t) { i += 6; break; }
  75. if (x[i + 7] == t) { i += 7; break; }
  76. i += 8;
  77. }
  78.  
  79. // Восстанавливаем значение последнего
  80. x[size - 1] = hold;
  81.  
  82. if (i == size-1)
  83. {
  84. return -1;
  85. }
  86. return i;
  87. }
  88.  
  89. static void Main(string[] args)
  90. {
  91. // Генератор случайных чисел
  92. RandomGenerator gen = new RandomGenerator(2000000);
  93. // Счетчик времени с точностью до наносекунд
  94. Timer timerObj = new Timer(1);
  95. SSearchTest ssearch = new SSearchTest();
  96.  
  97. // Генерим случайные числа указанного диапазона
  98. int[] numberList = gen.Get(0, 1000000);
  99.  
  100. int needle = 2; // Число, которое будем искать
  101.  
  102. // Результат поисков и затраченное время
  103. int res;
  104. double sec;
  105.  
  106. // Результаты неоптимизированной версии
  107. timerObj.Start(0);
  108. res = ssearch.SSearch(numberList, needle);
  109. sec = timerObj.Get(0);
  110. Console.WriteLine("Res index: {0}, time: {1} seconds", res, sec);
  111.  
  112. // Результаты оптимизации #1
  113. timerObj.Start(0);
  114. res = ssearch.SSearch2(numberList, needle);
  115. sec = timerObj.Get(0);
  116. Console.WriteLine("Res index: {0}, time: {1} seconds", res, sec);
  117.  
  118. // Результаты оптимизации #2
  119. timerObj.Start(0);
  120. res = ssearch.SSearch3(numberList, needle);
  121. sec = timerObj.Get(0);
  122. Console.WriteLine("Res index: {0}, time: {1} seconds", res, sec);
  123. }
  124. }
  125.  
  126.  
Протестируем на реальном примере какой же выигрышь дают все эти навороты с последовательным поиском.
Генерится 2 миллиона случайных чисел от 0 до 1000000. И ищется число, заданное в переменной needle.

Время подсчитывается с точностью до наносекунд.
Файлы: RandomGenerator.cs, Timer.cs

Результаты от запуска к запуску немного отличались конечно, но в среднем оптимизация #1 была быстрее примерно на 10%, а оптимизация #2 - ~ на 20%.
Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

+добавить реализацию