копирование трех элементов плюс запись нового не получиться - таки надо раздвинуть.


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

наверно это все равно будет быстрее чем с несортированным массивом.

Сообщение отредактировал Jenya7 - Oct 22 2017, 10:09

А вообще-то для полной универсальности топикстартеру надо сюда - https://ru.wikipedia.org/wiki/%D0%9A%D1%80%...%B5%D0%B2%D0%BE



Вы прикалываетесь? В конкретно данном случае раздвижка и есть копирование трех элементов.

это как? допустим есть элементы 3 5 7 9. я хочу вставить 6. он встанет на место 7. а семь куда встанет?

Я уже несколько раз написал - это можно сделать за одну операцию memmove(): сдвиг элементов в массиве поиска от добавляемого до удаляемого. Всего одна memmove.

но сама функция memmove внутри наверняка сдвигает N элементов. чудес не бывает.

Это зависит от платформы ? - в смысле содержимого memmove() - аппаратная или программная реализация пересылки ?

memmove() применяется к массиву в РАМ. Тут уж какя бы ни была платформа а функция должна взять каждый элемент и сдвинуть.

Еще раз.




После этого массив имеет вид 3,5,6,7,9.

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

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

Вставка элемента - допустим случай *как всегда* - memmove не оптимальна - сдвиг N элементов. Удаление - сдвиг N элементов. Это сопоставимо с перебором элементов в форе.
Идем дальше. Массив пустой. Пришел первый элемент 100. Пришел элемент 90 - сдвинь вправо, вставь элемент. Пришел элемент 80 - сдвинь вправо, вставь элемент.
И так далее.
И все таки это будет быстрее простого перебора?

Посмотрел красно-черное дерево. пишут конечно красиво. маслом. вопрос так ли он быстЁр как кажется.

Сообщение отредактировал Jenya7 - Oct 22 2017, 11:00

Ну смотрите. Поиск будет занимать 9 сравнений. Считайте, что это бесплатно. Теперь memmove. Ну при хорошей реализации для ARM он примерно два байта за такт процессора пересылает (ну чуть меньше, чем два, но сейчас это пофиг). Итого максимум будет 8*512=4к/2=2000 тактов. Ну пусть будет среднепотолочная тактовая в 100МГц, т.е. 20мкс. Да даже, если и один байт на такт, все равно 40мкс. Много или мало - решать Вам.



memmove куда быстрее, чем перебор элементов в цикле.

Я говорю о том, что не нужно дважды вызывать memmove(): сначала для удаления старой записи из массива поиска (и сжатия массива), а потом для раздвижки этого массива и вставки нового значения. Достаточно одного вызова memmove() для диапазона элементов от удаляемого до вставляемого.


Если разговор о платформе Cortex-M и IAR, то внутри библиотечной memcpy() (и думаю что и memmove() тоже), копирование может идти с использованием нескольких регистров процессора (читается-пишется сразу по несколько 32-битных слов). См. дизасм.


Да ладно! Какой компилятор? IAR-овский memcpy() может использовать до 4х или даже 8и регистров (точно не помню) процессора для копирования.
Посчитайте сколько это байт. Конечно он предварительно смотрит на размер пересылки и, в зависимости от него, выбирает тот или иной цикл копирования.
Побайтно будет для ОЧЕНЬ маленьких размеров.

Вы не поняли. Комбинация из LDM и STM занимает 1+N+1+N тактов, где N - количество регистров, по 4 байта на регистр. Грубо говоря 2N тактов на 4N байт. Итого за один такт пересылается 2 байта. На самом деле ситуация хуже из-за накладных расходов.

Rst7, jcxz.
Большое вам спасибо. Сделаю так.
Вообще это пишется под Colibri PXA320 на vxWorks. Тактовая там 104 мега, что удивительно, может удвою на PLL, не знаю, еще не смотрел. Но что хорошо много РАМ. Поэтому думал замутить базу данных раз место позволяет, но вижу мы и так хорошо справляемся.

Ок. Итого в случае ТСа:
имеем среднюю длину пересылки внутри массива поиска при добавлении нового кадра == 512*4/2 байт.
Или 512*4/2/2=512 тактов. Ну немного больше (из-за тактов декодирования LDM/STM, счётчиков цикла и команд перехода), пускай даже в 1.5 раза. Но всё равно это == несколько мкс на современном CM3/4.

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