<< | к задаче | главная | печатать | обсудить(0 сообщений) >>
Задача: Оптимизация последовательного поиска
Исходник: Последовательный поиск, оптимизация вторая: добавление метки + сокращение циклов [C#, code #60, hits: 6213, рейтинг: 3/7,4.82(1929)] +
автор: this [добавлен: 21.02.2006] управление:
  1. public int SSearch3(int[] x, int t)
  2. {
  3. int size = x.Length;
  4.  
  5. // Временно сохраняем последний
  6. int hold = x[size - 1];
  7.  
  8. /* Если последний элемент искомый
  9. * то это нужно проверять сразу
  10. */
  11. if (hold == t) return size - 1;
  12.  
  13. x[size - 1] = t;
  14.  
  15. int i = 0;
  16. while (true)
  17. {
  18. if (x[i] == t) break;
  19. if (x[i + 1] == t) { i += 1; break; }
  20. if (x[i + 2] == t) { i += 2; break; }
  21. if (x[i + 3] == t) { i += 3; break; }
  22. if (x[i + 4] == t) { i += 4; break; }
  23. if (x[i + 5] == t) { i += 5; break; }
  24. if (x[i + 6] == t) { i += 6; break; }
  25. if (x[i + 7] == t) { i += 7; break; }
  26. i += 8;
  27. }
  28.  
  29. // Восстанавливаем значение последнего
  30. x[size - 1] = hold;
  31.  
  32. if (i == size-1)
  33. {
  34. return -1;
  35. }
  36. return i;
  37. }
Последовательный поиск, оптимизация вторая: добавление метки + сокращение циклов.

При поверхностном взгляде может сходу возникнуть вопрос: если длинна массива нечетна 8, то на последнем проходе мы выйдем за границу цикла если такого числа нет в массиве??? Этого не произойдет. Потому что благодаря введению метки - в массиве который просматривается в цикле - всегда будет содержаться искомый элемент. Просто если его нет в исходном массиве, то индекс его будет равен == (размер массива - 1), а это равносильно тому, что его нет!

При этом ситуацию, когда искомый элемент находится в конце исходного массива - нужно отфильтровывать в самом начале, т.к. потом присутствие искомого элемента в конце - приравнивается к отрицательному результату поиска.

+добавить реализацию
 
каталог | задачи | паттерны | исходники | стат | форумы | карта сайта | контакты | ссылки 
© 2000-2017 CodeLAB Group
  Все права защищены
Страница сгенерирована за 0.011396 секунд
Количество запросов к БД: 9, gzip: 3.5kb/12.9kb(73%)