Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: 1 2      [все]
 Бинарный поиск в С  [new]
jenya7
Member

Откуда:
Сообщений: 1063
Я хочу сделать бинарный поиск в сортированном массиве. Без рекурсии.
int BinarySearch(int arr[], int low, int high, int key)
{
     int mid; // = (low + high)/2;
     int  done = 0;
     
     if (high < low) 
           return -1;
       
     mid = (low + high)/2;
         
     while (!done)
     {
         if(key==arr[mid])
             return mid;
         else if (key > arr[mid])
             mid = ((mid+1) + high) / 2;
         else if (key < arr[mid])
            mid = (low + (mid-1)) / 2;
     }
     
     return -1;
}


Если искомый элемент (key) есть в массиве (arr) то все нормально, функция возвращает индекс массива. Но если элемента нет в массиве я кручусь все время в цикле (while (!done)).
Я что то никак не соображу по какому условию выйти из цикла.
23 окт 17, 10:00    [20891134]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
Vladimir Baskakov
Member

Откуда:
Сообщений: 1927
Надо сжимать интервал, если он сжался, а ничего не нашлось, тогда ой. шпаргалка под спойлером, лучше не подглядывать, без крайней нужды. а додумать. потому что все несложно. Главное не забыть менять done - а то же там константа, поэтому цикл будет вращаться до конца света.

+
int BinarySearch(int arr[], int low, int high, int key)
{
     int mid; // = (low + high)/2;
     int  done = 0;
     
     if (high < low) 
           return -1;
       
         
     while (1)
     {
         mid = (low + high)/2;

         if(key==arr[mid])  return mid;

         if (low==high) return -1;

         if (key > arr[mid])  low = (mid+1) 
         else  high =  (mid-1);
                
     }   
    
}


int BinarySearch_rec(int arr[], int low, int high, int key)
{
     int mid; // = (low + high)/2;
     int  done = 0;
     
     if (high < low) return -1;
       
     mid = (low + high)/2;

     if(key==arr[mid])
             return mid;
     if (low==high) return -1;
     if (key > arr[mid])
             low = (mid+1) ;
     else  high =  (mid-1);
     return BinarySearch_rec(arr, low, high, key);
}
23 окт 17, 10:26    [20891203]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
exp98
Member

Откуда:
Сообщений: 1610
По условию done = y, где у != 0
например внутри цикла
23 окт 17, 10:27    [20891205]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
jenya7
Member

Откуда:
Сообщений: 1063
Vladimir Baskakov
Надо сжимать интервал, если он сжался, а ничего не нашлось, тогда ой. шпаргалка под спойлером, лучше не подглядывать, без крайней нужды. а додумать. потому что все несложно. Главное не забыть менять done - а то же там константа, поэтому цикл будет вращаться до конца света.

большое спасибо. работает. но у меня тут еще одна проблема. я хочу вставлять элемент если он не найден. то есть я хочу вернуть не -1 а индекс на место которого я хочу вставить элемент. соответсвенно все элементы перед ним я сдвину вправо. как мне модифицировать функцию?
я думал ввести условие
 else if (key > arr[mid] && key <  arr[mid+1])

но что то в нем не так.
23 окт 17, 10:39    [20891254]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
jenya7
Member

Откуда:
Сообщений: 1063
а проблема в том что это недостаточное условие. нужен какой то флаг - элемент не найден. но тогда получается нужно делать еще один пробег?
23 окт 17, 10:48    [20891288]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
MBo
Member

Откуда:
Сообщений: 67
jenya7, пробег делать не надо, достаточно ещё одного сравнения. Вот из Вики:

 
   while (first < last) {
        size_t mid = first + (last - first) / 2;

        if (x <= a[mid])
            last = mid;
        else
            first = mid + 1;
    }

    /* Если условный оператор if (n == 0) и т.д. в начале опущен -
     * значит, тут раскомментировать!
     */
    if (/* last < n && */ a[last] == x) {
        /* Искомый элемент найден. last - искомый индекс */
        return FOUND(last);
    } else {
        /* Искомый элемент не найден. Но если вам вдруг надо его
         * вставить со сдвигом, то его место - last.
         */
        return NOTFOUND(last);
    }
23 окт 17, 11:07    [20891369]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
exp98
Member

Откуда:
Сообщений: 1610
jenya7, а done чем не флаг? в integer разных значений как грязи весной ...
23 окт 17, 11:10    [20891382]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
jenya7
Member

Откуда:
Сообщений: 1063
MBo
jenya7, пробег делать не надо, достаточно ещё одного сравнения. Вот из Вики:

 
   while (first < last) {
        size_t mid = first + (last - first) / 2;

        if (x <= a[mid])
            last = mid;
        else
            first = mid + 1;
    }

    /* Если условный оператор if (n == 0) и т.д. в начале опущен -
     * значит, тут раскомментировать!
     */
    if (/* last < n && */ a[last] == x) {
        /* Искомый элемент найден. last - искомый индекс */
        return FOUND(last);
    } else {
        /* Искомый элемент не найден. Но если вам вдруг надо его
         * вставить со сдвигом, то его место - last.
         */
        return NOTFOUND(last);
    }

а FOUND это что? дефайн?
23 окт 17, 11:24    [20891453]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
MBo
Member

Откуда:
Сообщений: 67
а FOUND это что? дефайн?

Да, там возвращается структура из двух членов - индекс и boolean признак. Достаточно нелепо.
Варианты:
- изменить прототип, индекс сделать аргументом, а результат - boolean
- возвращать положительный индекс при наличии, отрицательный при отсутствии.
- при использовании исключительно для поиска места для вставки - оставить обычный интерфейс
23 окт 17, 11:36    [20891515]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
jenya7
Member

Откуда:
Сообщений: 1063
а где изменяется n?
23 окт 17, 11:37    [20891525]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
jenya7
Member

Откуда:
Сообщений: 1063
не хватает условия. я могу вывести флаг аргументом наружу

int BinarySearch(int a[], int first, int last, int key, int *found)

но нужно еще одно условие
23 окт 17, 11:45    [20891566]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
MBo
Member

Откуда:
Сообщений: 67
jenya7, это длина массива, она, в общем-то, не нужна и закомментарена. Код https://ru.wikipedia.org/wiki/Двоичный_поиск
23 окт 17, 11:46    [20891570]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
MBo
Member

Откуда:
Сообщений: 67
jenya7,

какое ещё условие нужно?
23 окт 17, 11:47    [20891573]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
jenya7
Member

Откуда:
Сообщений: 1063
MBo
jenya7,

какое ещё условие нужно?

спасибо. сделал так
int BinarySearch(int a[], int pos, int key, int *found)
{
    int first = 0;
    int last = pos;
    int mid;
    
    if (pos == 0)  //empty array
    {
        *found = 0;
        return 0;
    }
    else if (a[0] > key) 
    {
        *found = 0;
        return 0;
    }
    else if (a[pos - 1] < key)
    {
        *found = 0;
        return pos;
    }
    
    while (first < last)
    {
        mid = first + (last - first) / 2;

        if (key <= a[mid])
            last = mid;
        else
            first = mid + 1;
    }

    if (a[last] == key)
    {
        *found = 1;
        return last;
    }
    else
    {
        *found = 0;
        return last;
    }
}

похоже что работает.
23 окт 17, 12:37    [20891847]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
Dima T
Member

Откуда:
Сообщений: 13553
jenya7
спасибо. сделал так
int BinarySearch(int a[], int pos, int key, int *found)

Я так понимаю found это найдено/не найдено.

Обычно наоборот делают, функция возвращает ошибку, а переменная под результат в параметрах, т.е.
int BinarySearch(int a[], int pos, int key, int *result)
23 окт 17, 12:53    [20891958]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 6111
http://www.cplusplus.com/reference/cstdlib/bsearch/

и не надо изобретать
23 окт 17, 12:55    [20891971]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
jenya7
Member

Откуда:
Сообщений: 1063
Dima T
jenya7
спасибо. сделал так
int BinarySearch(int a[], int pos, int key, int *found)

Я так понимаю found это найдено/не найдено.

Обычно наоборот делают, функция возвращает ошибку, а переменная под результат в параметрах, т.е.
int BinarySearch(int a[], int pos, int key, int *result)

понял. спасибо. переделаю.
23 окт 17, 12:57    [20891991]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
jenya7
Member

Откуда:
Сообщений: 1063
Siemargl
http://www.cplusplus.com/reference/cstdlib/bsearch/

и не надо изобретать

инетересно но сложно. вопрос что будет compar в моем случае?
23 окт 17, 13:03    [20892036]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
Dima T
Member

Откуда:
Сообщений: 13553
jenya7
Siemargl
http://www.cplusplus.com/reference/cstdlib/bsearch/

и не надо изобретать

инетересно но сложно. вопрос что будет compar в моем случае?

Там есть пример кода с твоим случаем, т.е. массивом int.
23 окт 17, 13:06    [20892058]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
jenya7
Member

Откуда:
Сообщений: 1063
Dima T
jenya7
пропущено...

инетересно но сложно. вопрос что будет compar в моем случае?

Там есть пример кода с твоим случаем, т.е. массивом int.


а где тут поиск середины?

int compareints (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}
23 окт 17, 13:17    [20892118]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
Dima T
Member

Откуда:
Сообщений: 13553
jenya7
Dima T
пропущено...

Там есть пример кода с твоим случаем, т.е. массивом int.


а где тут поиск середины?

int compareints (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

Тут нет поиска середины, т.к. это компаратор, т.е. функция сравнения двух элементов массива.
Сам алгоритм поиска внутри bsearch(), в которую передаются исходные данные, включая компаратор.
23 окт 17, 13:22    [20892145]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
Dima T
Member

Откуда:
Сообщений: 13553
Dima T
это компаратор, т.е. функция сравнения двух элементов массива

Неправильно выразился, это функция сравнения значений по двум указателям.
23 окт 17, 13:26    [20892165]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
jenya7
Member

Откуда:
Сообщений: 1063
Dima T
jenya7
пропущено...


а где тут поиск середины?

int compareints (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

Тут нет поиска середины, т.к. это компаратор, т.е. функция сравнения двух элементов массива.
Сам алгоритм поиска внутри bsearch(), в которую передаются исходные данные, включая компаратор.

а нам нужна эта функция для бинарного поиска? мне кажется я могу передать нулевой указатель в качестве аргумента. все аргументы для поиска присутствуют в bsearch а компаратор как мне кажется лишний элемент.
23 окт 17, 13:36    [20892228]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
Dima T
Member

Откуда:
Сообщений: 13553
jenya7
Dima T
пропущено...

Тут нет поиска середины, т.к. это компаратор, т.е. функция сравнения двух элементов массива.
Сам алгоритм поиска внутри bsearch(), в которую передаются исходные данные, включая компаратор.

а нам нужна эта функция для бинарного поиска? мне кажется я могу передать нулевой указатель в качестве аргумента. все аргументы для поиска присутствуют в bsearch а компаратор как мне кажется лишний элемент.

bsearch() универсальная функция для любых типов, на входе у нее void*. Компаратор нужен для того чтобы правильно сравнить два void*
23 окт 17, 13:54    [20892315]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
jenya7
Member

Откуда:
Сообщений: 1063
Dima T
jenya7
пропущено...

а нам нужна эта функция для бинарного поиска? мне кажется я могу передать нулевой указатель в качестве аргумента. все аргументы для поиска присутствуют в bsearch а компаратор как мне кажется лишний элемент.

bsearch() универсальная функция для любых типов, на входе у нее void*. Компаратор нужен для того чтобы правильно сравнить два void*

понял. спасибо. попробую.
23 окт 17, 14:23    [20892453]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
Vladimir Baskakov
Member

Откуда:
Сообщений: 1927
jenya7
MBo
jenya7,

какое ещё условие нужно?

спасибо. сделал так
int BinarySearch(int a[], int pos, int key, int *found)
{
    int first = 0;
    int last = pos;
    int mid;
    
    if (pos == 0)  //empty array
    {
        *found = 0;
        return 0;
    }
    else if (a[0] > key) 
    {
        *found = 0;
        return 0;
    }
    else if (a[pos - 1] < key)
    {
        *found = 0;
        return pos;
    }
    
    while (first < last)
    {
        mid = first + (last - first) / 2;

        if (key <= a[mid])
            last = mid;
        else
            first = mid + 1;
    }

    if (a[last] == key)
    {
        *found = 1;
        return last;
    }
    else
    {
        *found = 0;
        return last;
    }
}

похоже что работает.

....................................
а я бы возвращал положительное число, индекс+1 если найдено, а если не найдено - отрицательный индекс вставки - и параметр found тогда не нужен.

А чего изобретаете то? или так, язык поучить?
24 окт 17, 11:30    [20895039]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
Vladimir Baskakov
Member

Откуда:
Сообщений: 1927
плохо сказал.
можно задачу ф-ции переформулировать так - найти индекс первого элемента, который больше или равен ключу.

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

параметр found точно не нужен.
24 окт 17, 11:40    [20895073]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
jenya7
Member

Откуда:
Сообщений: 1063
[quot Vladimir Baskakov]
jenya7
пропущено...


....................................
а я бы возвращал положительное число, индекс+1 если найдено, а если не найдено - отрицательный индекс вставки - и параметр found тогда не нужен.

А чего изобретаете то? или так, язык поучить?

Задача такая. Есть массив пакетов приходящих по TCP, в принципе не важно откуда они приходят.
Я должен хранить эти пакеты, для этого я создал массив пакетов. Глубина хранения пока 512 хотя может вырасти до пару тысяч, это еще TBD. То есть размер массива пока 512.
В приходящем пакете есть ИД и команда - добавить пакет, удалить пакет, редактировать пакет.
Доступ к пакету должен быть максимально быстрым. Находить ИД пакета простым перебором в for долго. Поэтому решил находить бинарным поиском и если ИД не найден вставлять его на его место, чтоб массив всегда был сортирован по ИД.
24 окт 17, 13:47    [20895525]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
jenya7
Member

Откуда:
Сообщений: 1063
пока что сделал так.
#define MESSAGE_SIZE 20
#define MESSAGE_ARR_SIZE  20

typedef struct TEST_MESSAGE_S
{
    int id;
    char data[MESSAGE_SIZE];
}TEST_MESSAGE;

TEST_MESSAGE messages[MESSAGE_ARR_SIZE];

char spectra_packet[20];

int  spectra_id;
int spectra_command;

int BinarySearch(TEST_MESSAGE a[], int pos, int key, int *found);
void InsertElement(int id, char *msg);
void DeleteElement(int id);

int BinarySearch(TEST_MESSAGE a[], int pos, int key, int *found)
{
    int first = 0;
    int last = pos;
    int mid;
    
    if (pos == 0)  //empty array
    {
        *found = 0;
        return 0;
    }
    else if (a[0].id > key) 
    {
        *found = 0;
        return 0;
    }
    else if (a[pos - 1].id < key)
    {
        *found = 0;
        return pos;
    }
    
    while (first < last)
    {
        mid = first + (last - first) / 2;

        if (key <= a[mid].id)
            last = mid;
        else
            first = mid + 1;
    }

    if (a[last].id == key)
    {
        *found = 1;
        return last;
    }
    else
    {
       *found = 0;
        return last;
    }
}

void UpdateElement(int id[, char msg[])
{
}

void InsertElement(int id, char *msg)
{
    int idx;
    
    idx = BinarySearch(messages, glob_pos, id, &found);
    
    if (found)  //command NEW but the element exists - issue UPDATE
    {
        UpdateElement(idx, msg);
    }
    else //element not found - add one
    {
        memmove(messages+(idx+1), messages+idx, sizeof(TEST_MESSAGE)*(glob_pos-idx));   //glob_pos-1-idx
        
        messages[idx].id = id;
        memcpy(messages[idx].data, msg, sizeof(spectra_packet));
        
       //if (glob_pos < MESSAGE_ARR_SIZE)
        glob_pos++;
    }
}

void DeleteElement(int id)
{
     int idx;
    
    idx = BinarySearch(messages, glob_pos, id, &found);
    
    if (found) 
    {
       memmove(messages+idx, messages+(idx+1), sizeof(TEST_MESSAGE)*glob_pos-1-idx);
       
       if (glob_pos > 0)
           glob_pos--;
    }
}
24 окт 17, 13:53    [20895551]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
jenya7
Member

Откуда:
Сообщений: 1063
тестирую так
 /////////////////////////////TEST  AREA ///////////////////////////////////
  for (idx = 0; idx < 20; idx++)
  {
      messages[idx].id = -1;
  }
  
  while(1)
  {
      spectra_id = spectra_packet[0];
      spectra_command = spectra_packet[1];
      
      switch (spectra_command)
      {
            case 1:
                if (glob_pos < MESSAGE_ARR_SIZE)
                    InsertElement(spectra_id, spectra_packet);
            break;
            case 2:
                DeleteElement(spectra_id);
            break;
      }
  }
/////////////////////////////////////////////////////////////////////


пока вроде вставка и удаление проходят нормально.
24 окт 17, 13:57    [20895564]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
Vladimir Baskakov
Member

Откуда:
Сообщений: 1927
Задача такая. Есть массив пакетов приходящих по TCP, в принципе не важно откуда они приходят.
Я должен хранить эти пакеты, для этого я создал массив пакетов. Глубина хранения пока 512 хотя может вырасти до пару тысяч, это еще TBD. То есть размер массива пока 512.
В приходящем пакете есть ИД и команда - добавить пакет, удалить пакет, редактировать пакет.
Доступ к пакету должен быть максимально быстрым. Находить ИД пакета простым перебором в for долго. Поэтому решил находить бинарным поиском и если ИД не найден вставлять его на его место, чтоб массив всегда был сортирован по ИД.


чисто теоретически,
https://habrahabr.ru/post/65617/
https://ru.wikipedia.org/wiki/B-дерево
есть разные упорядоченные структуры данных для хранения сортированных данных
- всякие бинарные и сбалансированные деревья. может быть среди них поискать.

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

допустим, если храним 2000 значений - захешировали на сотню, и вот уже в каждом массивчике перебираемых 20 единиц (в среднем) - и вставлять быстро и искать нормально. А перерасход памяти для такого количества значений - мизернейший.


============================
всего доброго.

PS
а почему си, а не с++ с огромным массивом оптимизированных уже библиотек? ну дело хозяйское, в целом.
24 окт 17, 14:43    [20895756]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
jenya7
Member

Откуда:
Сообщений: 1063
Vladimir Baskakov
Задача такая. Есть массив пакетов приходящих по TCP, в принципе не важно откуда они приходят.
Я должен хранить эти пакеты, для этого я создал массив пакетов. Глубина хранения пока 512 хотя может вырасти до пару тысяч, это еще TBD. То есть размер массива пока 512.
В приходящем пакете есть ИД и команда - добавить пакет, удалить пакет, редактировать пакет.
Доступ к пакету должен быть максимально быстрым. Находить ИД пакета простым перебором в for долго. Поэтому решил находить бинарным поиском и если ИД не найден вставлять его на его место, чтоб массив всегда был сортирован по ИД.


чисто теоретически,
https://habrahabr.ru/post/65617/
https://ru.wikipedia.org/wiki/B-дерево
есть разные упорядоченные структуры данных для хранения сортированных данных
- всякие бинарные и сбалансированные деревья. может быть среди них поискать.

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

допустим, если храним 2000 значений - захешировали на сотню, и вот уже в каждом массивчике перебираемых 20 единиц (в среднем) - и вставлять быстро и искать нормально. А перерасход памяти для такого количества значений - мизернейший.


============================
всего доброго.

PS
а почему си, а не с++ с огромным массивом оптимизированных уже библиотек? ну дело хозяйское, в целом.

я думал про хэш. но пока остановились на бинарном поиске.
24 окт 17, 17:30    [20896390]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
Vladimir Baskakov
Member

Откуда:
Сообщений: 1927
а почему? может быть на макете сверить производительность?

от целого хэш-функция на 10 000 значений посчитается практически влет, и скорее всего в каждом из этих 10000 массивов будет сидеть ну три, ну пять ключей. если всего значений 2000.

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

но, не настаиваю. кому как удобнее.
24 окт 17, 17:45    [20896437]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
jenya7
Member

Откуда:
Сообщений: 1063
Vladimir Baskakov
а почему? может быть на макете сверить производительность?

от целого хэш-функция на 10 000 значений посчитается практически влет, и скорее всего в каждом из этих 10000 массивов будет сидеть ну три, ну пять ключей. если всего значений 2000.

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

но, не настаиваю. кому как удобнее.

я представил две опции. но народ выбрал бинарный поиск. я не стал спорить. если будем терять пакеты попробуем хэш. есть еще красно-черное дерево которое, как говорят, на больших массивах дает хорошие результаты.
24 окт 17, 17:49    [20896450]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
Vladimir Baskakov
Member

Откуда:
Сообщений: 1927
что еще по ходу подумалось (я уже давным-давно не сишник, по старой памяти)

char * strchr( const char * string, int symbol);

вроде бы эффективно задействует возможности процессора для поиска в области памяти.
вроде бы scas http://programm.ws/page.php?id=129

может быть не сортировать, а искать на уровне байт? найти первый байт искомого числа. проверить совпадение следующих.

мне кажется тут есть о чем подумать, если уж надо очень, очень быстро искать в сравнительно-небольших массивах, до 10-20 килобайт

вплоть до того, что весь массив в котором ищем держать в строковом виде 16-ричных чисел и искать там строковыми, высокооптимизированными ф-циями, которые были и есть в составе стандартной б-ки Си.

то есть, вариантов на попробовать, даже в самом простом случае, море.

Попробуйте, шутки ради, вдруг да выйдет....
24 окт 17, 18:11    [20896496]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
Dima T
Member

Откуда:
Сообщений: 13553
jenya7
я думал про хэш. но пока остановились на бинарном поиске.

Тут выбор между быстро искать и и быстро вставлять/удалять. Бинарный поиск ищет достаточно быстро, не факт что хэштаблица будет искать быстрее при нескольких тысячах элементов. Но вставка/удаление требует сдвига существенной части массива, что не быстро.
Если вставок/удалений относительно немного, то твой способ будет нормально работать. Надо просто затестить с нагрузкой похожей на реальную. Если производительность устроит, то можешь оставить как есть.
24 окт 17, 18:13    [20896501]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
Vladimir Baskakov
Member

Откуда:
Сообщений: 1927
jenya7
я представил две опции. но народ выбрал бинарный поиск. я не стал спорить. если будем терять пакеты попробуем хэш. есть еще красно-черное дерево которое, как говорят, на больших массивах дает хорошие результаты.


а время то меряли? профилировали? может и не пробежка по несортированному массиву его занимает? а какая-то предобработка, принятие пакетов, или постобработка?

ну, я против народа то не пойду.... народ сказал, значит так надо.
24 окт 17, 18:16    [20896513]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
Vladimir Baskakov
Member

Откуда:
Сообщений: 1927
Dima T
jenya7
я думал про хэш. но пока остановились на бинарном поиске.

Тут выбор между быстро искать и и быстро вставлять/удалять. Бинарный поиск ищет достаточно быстро, не факт что хэштаблица будет искать быстрее при нескольких тысячах элементов. Но вставка/удаление требует сдвига существенной части массива, что не быстро.
Если вставок/удалений относительно немного, то твой способ будет нормально работать. Надо просто затестить с нагрузкой похожей на реальную. Если производительность устроит, то можешь оставить как есть.


вот и я к тому, что надо понять где затыки сейчас, и где они могут быть, а уж потом выбор выбирать.

(шутка)надеюсь, это курсовичок, а не атомный ледокол с горячей заменой кода на проде. когда бесконечный цикл не даст опустить графитовый стерженек....(конец шутки)
24 окт 17, 18:21    [20896524]     Ответить | Цитировать Сообщить модератору
 Re: Бинарный поиск в С  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 6111
Vladimir Baskakov,

шутка про дельфи за 300 ?
24 окт 17, 22:31    [20897007]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2      [все]
Все форумы / Программирование Ответить