[jenya7 0]

Ну если реализация вменяема - то быстро. Худшие результаты там гарантированы, они все O(log n). Другое дело, что для небольших массивов (ну как у Вас, 512 элементов) всякие накладные расходы на дерево могут превысить по времени хорошо оптимизированный бинарный поиск плюс memmove.

я понял. 512 может превратиться в пару тысяч, это еще TBD. вы говорите на больших размерах можно подумать о красно-черном дереве?

[Rst7 5]

вы говорите на больших размерах можно подумать о красно-черном дереве?

 

Даже не можно, а нужно. Ну вот мне кажется, что как раз 512 - вот это близко к пределу, за которым дерево будет выгоднее.

[jenya7 0]

Даже не можно, а нужно. Ну вот мне кажется, что как раз 512 - вот это близко к пределу, за которым дерево будет выгоднее.

спасибо. так и сделаю.

[jenya7 0]

хотел уточнить такой вопрос

для вставки

memmove(a+(i+1), a+i, sizeof(int)*(N-1-i));

тогда для удаления так?

memmove(a+i, a+(i+1), sizeof(int)*(N-1-i));

и потом почему sizeof(int)? у меня массив чаров. наверно надо sizeof(char)

 

и вот еще такой вопрос

в примерах выше мы предполагаем, что а это линейный массив.

но у меня он определен так

typedef struct А_S
{
    int id;
    char message[128];
}А;

А а[512];

 

получается я должен добавить отступ?

memmove( a+(i*sizeof(A)+1),  a+(i*sizeof(A)),  sizeof(int)*(N-1-i));

Изменено 23 октября, 2017 пользователем Jenya7

[Rst7 5]

получается я должен добавить отступ?

 

Нет. Надо так

memmove( a+(i+1),  a+i,  sizeof(A)*(N-1-i));

[jenya7 0]

Нет. Надо так

memmove( a+(i+1),  a+i,  sizeof(A)*(N-1-i));

понял. спасибо.

 

ммм...и все таки. допустим есть три злемента N элеметов

a[0].id = 3;

a[1].id = 7;

a[2].id = 11;

пришел пакет с id = 10 - его надо вставить на индекс 2. но а+2 не будет адресом элемента a[2].

Изменено 23 октября, 2017 пользователем Jenya7

[Rst7 5]

но а+2 не будет адресом элемента a[2].

 

Что значит не будет? Вы бы почитали про адресную арифметику в Си, для начала.

 

&(a[2])==a+2, если что.

[jenya7 0]

Что значит не будет? Вы бы почитали про адресную арифметику в Си, для начала.

 

&(a[2])==a+2, если что.

ой. что то я туплю. вы правы.

 

ну вот я тут накропал. уж не знаю...

#define MESSAGE_ARR_SIZE 128

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

TEST_MESSAGE messages[MESSAGE_ARR_SIZE8];

int found;
int glob_pos;

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 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-1-idx);
        messages[idx].id = id;
        memcpy(messages[idx].data,  msg, sizeof(msg);

        
       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--;
    }
}

Изменено 23 октября, 2017 пользователем Jenya7

[xvr 12]

Советую отделить id от data и хранить id+индекс в массив data в отсортированном массиве, а сами data в отдельном кольцевом буфере (или пуле). Тогда при вставках/удалениях не надо будет по 20 лишних байтов на элемент таскать вперед назад

 

 

[jenya7 0]

Советую отделить id от data и хранить id+индекс в массив data в отсортированном массиве, а сами data в отдельном кольцевом буфере (или пуле). Тогда при вставках/удалениях не надо будет по 20 лишних байтов на элемент таскать вперед назад

в data я копирую пришедший пакет. а id просто чтоб знать какой пакет пришел. у пришедшего пакета тоже есть id. я их сравниваю.

индекс пакета в массиве может поменяться при вставке или удалении.

но id в принципе я зря таскаю вперед назад.

Изменено 24 октября, 2017 пользователем Jenya7

[ViKo 1]

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

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

[jenya7 0]

Результаты такие. При добавлении элемента я вылетал с исключением

Memory access error: Trying to write outside mapped memory at address 0x2000a000 when PC is 0x8001ef4. Check your memory configuration.

я поменял

memmove(messages+(idx+1), messages+idx, sizeof(TEST_MESSAGE)*glob_pos-1-idx);

на

memmove(messages+(idx+1), messages+idx, sizeof(TEST_MESSAGE)*glob_pos-idx);

то есть иместо sizeof(TEST_MESSAGE)*glob_pos-1-idx) - sizeof(TEST_MESSAGE)*glob_pos-idx)

и элементы начали добавляться.

но что странно. я инициализирую пришедший пакет - байт0 - ИД, байт1 - команда (1=вставка), и для проверки границ байт18 = 7, байт19 = 8.

После вставки я вижу байт0 = ИД, байт1 = 1 а байт18, байт19 - нули. Это memmove нам воду мутит или у меня где то ошибка?

 

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

так я при поиске заодно и сортирую вставкой.

Изменено 24 октября, 2017 пользователем Jenya7

[skripach 6]

массив 512 пакетов.

худший случай - каждую милисекунду поэтому время поиска элемента критично.

У вас там PIC 12 или at89c2081 ? За одну миллисекунду можно до канадской границы успеть добежать. :laughing:

[ViKo 1]

так я при поиске заодно и сортирую вставкой.

Получается и поиск и сортировка. Одно из них лишнее. :rolleyes:

Я предлагаю сортировать в свободное от досуга время. Если такое имеется.

[jenya7 0]

Нашел проблемку. Функция вставки в причесанном варианте выглядит так

void InsertElement(int id, char *msg)
{
    int idx;
    int size;
    
    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;

        size = sizeof(msg);
        memcpy(messages[idx].data, msg, size);
        
      if (glob_pos < MESSAGE_ARR_SIZE)
        glob_pos++;
    }
}

sizeof(msg) вычисляется как 4. sizeof не принимает указатель? это что размер указателя? но почему тогда 4?

 

а. ну да. что это я.

Изменено 24 октября, 2017 пользователем Jenya7