Последовательный поиск и его оптимизации, реализации на C#

Последовательный поиск и его оптимизации

Aвтор:this
Дата: 15.05.2003
Просмотров: 43893
реализации(C#: 4шт...) +добавить

Последовательный (или линейный) поиск - наверное одна из самых простых и наиболее использумых программистких задач, выполняющая повсеместно почти что в любой программе. Казалось бы - что вообще можно оптимизировать в таком элементарном алгоритме?
Оказывается и здесь есть достаточное поле для улучшения производительности...

По книге Джона Бентли:
"Жемчужины программирования"

"...Обратимся к последовательному поиску в таблице, которая может быть неотсортированной:

псевдокод: Последовательный поиск в массиве, исходная версия ссылка

int ssearch1(t)
  for i = 0 to n
    if x[i] == t
      return i
  return -1;

int ssearch1(t)
  for i = 0 to n
    if x[i] == t
      return i
  return -1;

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

Цикл выглядит достаточно стройным, но жирок с него все-таки срезать можно. Во внутреннем цикле выполняется две проверки. Сначала проверяется, достиг ли индекс i конца массива, а затем выясняется, не равен ли элемент x[i] искомому. Первую проверку можно исключить, добавив элемент-метку в конце массива:

псевдокод: Линейный поиск, оптимизированная версия, убрана 1 проверка ссылка

int ssearch2(t)
  hold = x[n]
  x[n] = t
  for (i = 0; ;i++)
    if x[i] == t
      break
 
  x[n] = hold
  if i == n
    return -1
  else
    return i;

int ssearch2(t)
  hold = x[n]
  x[n] = t
  for (i = 0; ;i++)
    if x[i] == t
      break
  
  x[n] = hold
  if i == n
    return -1
  else
    return i;

Время работы уменьшилось до 3,87n нc, то есть быстродействие возросло на 5%. Мы предполагаем, что массив уже выделен, поэтому имеется возможность временно затереть значение х[n]. Нужно быть аккуратным при сохранении значения х[n] и его восстановлении. В большинстве приложений этого не требуется, так что мы исключим эту операцию из следующей версии программы.

Теперь внутренний цикл содержит только операцию увеличения индекса, обращение к элементу массива и проверку. Можно ли еще что-нибудь урезать? В последней версии нашей программы количество повторов цикла сокращается в 8 раз. Дальнейшее сокращение не ускорило работу программы.

В итоге получаем такой последовательный поиск в массиве, оптимизированный практически до предела:

псевдокод: Алгоритм последовательного поиска ускоренный примерно в 8 раз ссылка

int ssearch3(t)
  x[n] = t
  for (i = 0; ;i += 8)
    if x[i] == t
      break
    if x[i+1] == t
      i += 1
      break
    if x[i+2] == t
      i += 2
      break
    if x[i+3] == t
      i += 3
      break
    if x[i+4] == t
      i += 4
      break
    if x[i+5] == t
      i += 5
      break
    if x[i+6] == t
      i += 6
      break
    if x[i+7] == t
      i += 7
      break
 
  if i == n
    return -1
  else
    return i;

int ssearch3(t)
  x[n] = t
  for (i = 0; ;i += 8)
    if x[i] == t
      break
    if x[i+1] == t
      i += 1
      break
    if x[i+2] == t
      i += 2
      break
    if x[i+3] == t
      i += 3
      break
    if x[i+4] == t
      i += 4
      break
    if x[i+5] == t
      i += 5
      break
    if x[i+6] == t
      i += 6
      break
    if x[i+7] == t
      i += 7
      break

  if i == n
    return -1
  else
    return i;

При этом время поиска сокращается до 1,07n нc, то есть наблюдается 56% ускорение. На старых компьютерах уменьшение дополнительных затрат может дать ускорение работы на 10 или 20%. На современных машинах раскрытие цикла позволяет избежать остановки конвейера, уменьшить количество ветвей и увеличить параллелизм на уровне инструкций.... "

При этом согласно проведенным примерным тестам производительности - оптимизация #1 быстрее базовой на процентов 10%, оптимизация #2 - процентов на 20%.

Реализации:

java(1), C#(4) +добавить

1) Последовательный поиск, версия #1 на C#, code #58[автор:this]
2) Последовательный поиск, версия #2 на C#, code #59[автор:this]

Последовательный поиск, оптимизация первая: добавление метки ссылка |режим:

public int SSearch2(int[] x, int t)
{
    int size = x.Length;
 
    // Временно сохраняем последний
    int hold = x[size-1];
 
    /* Если последний элемент искомый
     * то это нужно проверять сразу
     */
    if (hold == t) return size - 1;
 
    x[size - 1] = t;
 
    int i = 0;
    while (true)
    {
        if (x[i] == t)  break;
        i++;
    }
 
    // Восстанавливаем значение последнего
    x[size - 1] = hold;
 
    if (i == size-1)
    {
        return -1;
    }
    return i;
}

public int SSearch2(int[] x, int t)
{
    int size = x.Length;

    // Временно сохраняем последний
    int hold = x[size-1];

    /* Если последний элемент искомый
     * то это нужно проверять сразу
     */
    if (hold == t) return size - 1;

    x[size - 1] = t;

    int i = 0;
    while (true)
    {
        if (x[i] == t)  break;
        i++;
    }

    // Восстанавливаем значение последнего
    x[size - 1] = hold;

    if (i == size-1)
    {
        return -1;
    }
    return i;
}

Последовательный поиск, оптимизация первая: добавление метки.

Вместо последнего элемента - пишем искомый элемент. Благодаря этому цикл всегда будет находить наш элемент. Только если его действительно нет в исходном массиве - его индекс будет равен (size-1), что равносильно его отсутствию.

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

Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

3) Последовательный поиск, версия #3 на C#, code #60[автор:this]

Последовательный поиск, оптимизация вторая: добавление метки + сокращение циклов ссылка |режим:

public int SSearch3(int[] x, int t)
{
    int size = x.Length;
 
    // Временно сохраняем последний
    int hold = x[size - 1];
 
    /* Если последний элемент искомый
     * то это нужно проверять сразу
     */
    if (hold == t) return size - 1;
 
    x[size - 1] = t;
 
    int i = 0;
    while (true)
    {
        if (x[i] == t) break;
        if (x[i + 1] == t) { i += 1; break; }
        if (x[i + 2] == t) { i += 2; break; }
        if (x[i + 3] == t) { i += 3; break; }
        if (x[i + 4] == t) { i += 4; break; }
        if (x[i + 5] == t) { i += 5; break; }
        if (x[i + 6] == t) { i += 6; break; }
        if (x[i + 7] == t) { i += 7; break; }
        i += 8;
    }
 
    // Восстанавливаем значение последнего
    x[size - 1] = hold;
 
    if (i == size-1)
    {
        return -1;
    }
    return i;
}

public int SSearch3(int[] x, int t)
{
    int size = x.Length;

    // Временно сохраняем последний
    int hold = x[size - 1];

    /* Если последний элемент искомый
     * то это нужно проверять сразу
     */
    if (hold == t) return size - 1;

    x[size - 1] = t;

    int i = 0;
    while (true)
    {
        if (x[i] == t) break;
        if (x[i + 1] == t) { i += 1; break; }
        if (x[i + 2] == t) { i += 2; break; }
        if (x[i + 3] == t) { i += 3; break; }
        if (x[i + 4] == t) { i += 4; break; }
        if (x[i + 5] == t) { i += 5; break; }
        if (x[i + 6] == t) { i += 6; break; }
        if (x[i + 7] == t) { i += 7; break; }
        i += 8;
    }

    // Восстанавливаем значение последнего
    x[size - 1] = hold;

    if (i == size-1)
    {
        return -1;
    }
    return i;
}

Последовательный поиск, оптимизация вторая: добавление метки + сокращение циклов.

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

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

Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

4) Тест производительности разных версий последовательного поиска на C#, code #61[автор:this]

Тест производительности разных версий последовательного поиска ссылка |режим:

using System;
using System.Diagnostics;
using System.Net;
 
 
class SSearchTest
{
    public int SSearch(int[] x, int t)
    {
        for (int i = 0; i < x.Length; i++)
        {
            if (x[i] == t)
            {
                return i;
            }
        }
        return -1;
    }
 
    public int SSearch2(int[] x, int t)
    {
        int size = x.Length;
 
        // Временно сохраняем последний
        int hold = x[size-1];
 
        /* Если последний элемент искомый
         * то это нужно проверять сразу
         */
        if (hold == t) return size - 1;
 
        x[size - 1] = t;
 
        int i = 0;
        while (true)
        {
            if (x[i] == t)  break;
            i++;
        }
 
        // Восстанавливаем значение последнего
        x[size - 1] = hold;
 
        if (i == size-1)
        {
            return -1;
        }
        return i;
    }
 
    public int SSearch3(int[] x, int t)
    {
        int size = x.Length;
 
        // Временно сохраняем последний
        int hold = x[size - 1];
 
        /* Если последний элемент искомый
         * то это нужно проверять сразу
         */
        if (hold == t) return size - 1;
 
        x[size - 1] = t;
 
        int i = 0;
        while (true)
        {
            if (x[i] == t) break;
            if (x[i + 1] == t) { i += 1; break; }
            if (x[i + 2] == t) { i += 2; break; }
            if (x[i + 3] == t) { i += 3; break; }
            if (x[i + 4] == t) { i += 4; break; }
            if (x[i + 5] == t) { i += 5; break; }
            if (x[i + 6] == t) { i += 6; break; }
            if (x[i + 7] == t) { i += 7; break; }
            i += 8;
        }
 
        // Восстанавливаем значение последнего
        x[size - 1] = hold;
 
        if (i == size-1)
        {
            return -1;
        }
        return i;
    }
 
    static void Main(string[] args)
    {
        // Генератор случайных чисел
        RandomGenerator gen = new RandomGenerator(2000000);
        // Счетчик времени с точностью до наносекунд
        Timer timerObj = new Timer(1);
        SSearchTest ssearch = new SSearchTest();
 
        // Генерим случайные числа указанного диапазона
        int[] numberList = gen.Get(0, 1000000);
 
        int needle = 2; // Число, которое будем искать
 
        // Результат поисков и затраченное время
        int res;
        double sec;
 
        // Результаты неоптимизированной версии
        timerObj.Start(0);
        res = ssearch.SSearch(numberList, needle);
        sec = timerObj.Get(0);
        Console.WriteLine("Res index: {0}, time: {1} seconds", res, sec);
 
        // Результаты оптимизации #1
        timerObj.Start(0);
        res = ssearch.SSearch2(numberList, needle);
        sec = timerObj.Get(0);
        Console.WriteLine("Res index: {0}, time: {1} seconds", res, sec);
 
        // Результаты оптимизации #2
        timerObj.Start(0);
        res = ssearch.SSearch3(numberList, needle);
        sec = timerObj.Get(0);
        Console.WriteLine("Res index: {0}, time: {1} seconds", res, sec);
    }
}

using System;
using System.Diagnostics;
using System.Net;


class SSearchTest
{
    public int SSearch(int[] x, int t)
    {
        for (int i = 0; i < x.Length; i++)
        {
            if (x[i] == t)
            {
                return i;
            }
        }
        return -1;
    }

    public int SSearch2(int[] x, int t)
    {
        int size = x.Length;

        // Временно сохраняем последний
        int hold = x[size-1];

        /* Если последний элемент искомый
         * то это нужно проверять сразу
         */
        if (hold == t) return size - 1;

        x[size - 1] = t;

        int i = 0;
        while (true)
        {
            if (x[i] == t)  break;
            i++;
        }

        // Восстанавливаем значение последнего
        x[size - 1] = hold;

        if (i == size-1)
        {
            return -1;
        }
        return i;
    }

    public int SSearch3(int[] x, int t)
    {
        int size = x.Length;

        // Временно сохраняем последний
        int hold = x[size - 1];

        /* Если последний элемент искомый
         * то это нужно проверять сразу
         */
        if (hold == t) return size - 1;

        x[size - 1] = t;

        int i = 0;
        while (true)
        {
            if (x[i] == t) break;
            if (x[i + 1] == t) { i += 1; break; }
            if (x[i + 2] == t) { i += 2; break; }
            if (x[i + 3] == t) { i += 3; break; }
            if (x[i + 4] == t) { i += 4; break; }
            if (x[i + 5] == t) { i += 5; break; }
            if (x[i + 6] == t) { i += 6; break; }
            if (x[i + 7] == t) { i += 7; break; }
            i += 8;
        }

        // Восстанавливаем значение последнего
        x[size - 1] = hold;

        if (i == size-1)
        {
            return -1;
        }
        return i;
    }
     
    static void Main(string[] args)
    {
        // Генератор случайных чисел
        RandomGenerator gen = new RandomGenerator(2000000);
        // Счетчик времени с точностью до наносекунд
        Timer timerObj = new Timer(1);
        SSearchTest ssearch = new SSearchTest();
        
        // Генерим случайные числа указанного диапазона
        int[] numberList = gen.Get(0, 1000000);
        
        int needle = 2; // Число, которое будем искать

        // Результат поисков и затраченное время
        int res;
        double sec;

        // Результаты неоптимизированной версии
        timerObj.Start(0);
        res = ssearch.SSearch(numberList, needle);
        sec = timerObj.Get(0);
        Console.WriteLine("Res index: {0}, time: {1} seconds", res, sec);

        // Результаты оптимизации #1
        timerObj.Start(0);
        res = ssearch.SSearch2(numberList, needle);
        sec = timerObj.Get(0);
        Console.WriteLine("Res index: {0}, time: {1} seconds", res, sec);

        // Результаты оптимизации #2
        timerObj.Start(0);
        res = ssearch.SSearch3(numberList, needle);
        sec = timerObj.Get(0);
        Console.WriteLine("Res index: {0}, time: {1} seconds", res, sec);
    }
}

Протестируем на реальном примере какой же выигрышь дают все эти навороты с последовательным поиском.
Генерится 2 миллиона случайных чисел от 0 до 1000000. И ищется число, заданное в переменной needle.

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

Результаты от запуска к запуску немного отличались конечно, но в среднем оптимизация #1 была быстрее примерно на 10%, а оптимизация #2 - ~ на 20%.

Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

<< назад наверх

*	можно кириллицей (недопустимые символы:?&+=\/%#)
**	только для зарегистрированных пользователей

Популярные задачи:

Последовательный поиск и его оптимизации

Реализации: