Easyelectronics.ru

Электроника для всех
Текущее время: 19 фев 2020, 13:26

Часовой пояс: UTC + 5 часов



JLCPCB – Прототипы печатных плат за $2/10pcs (Любой цвет!)
Крупнейший производитель печатных плат и прототипов. Более 600000 клиентов и свыше 10000 заказов в день!
Получите скидку на почтовую отправку при первом заказе в JLCPCB!

Начать новую тему Ответить на тему  [ Сообщений: 60 ]  На страницу 1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 24 янв 2018, 19:45 
Старожил
Аватара пользователя

Зарегистрирован: 27 мар 2015, 04:10
Сообщения: 1931
Откуда: Харьков
MC: STM32F1
Есть у меня примерно такая структура:
Код:
typedef struct Device *dLink;
typedef struct Device
{
  uint16_t Address;
  uint8_t Type;
  uint8_t Config;     //[0] - Confirmed, [1] - Online, [2] - Enabled
  uint32_t Salt;      //Random salt for CRC32 checksum
  dLink    Next;
  dLink    Prev;
} xDevice;

которая описывает некий девайс. Девайсов этих может быть переменное количество. Чтоб не создавать массив под них я при добавлении нового устройства выделаю память через malloc и потом связываю их в цепочки через указатели Next/Prev.
Дальше мне часто требуется делать поиск по полю Address ну и понятно что я пробегаюсь по всей цепочке пока не найду искомый.
Вот хочу спросить
1) является ли такой подход оптимальным для организации данных переменной длины в памяти или может есть лучшие способы как разместить данные переменной длинны в памяти и работать с ними?
2) как оптимальней искать по полю чтоб отделаться малыми затратами по расходу памяти и времени?


Последний раз редактировалось alexsam 25 янв 2018, 12:27, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 24 янв 2018, 20:14 
Старожил

Зарегистрирован: 05 фев 2015, 23:41
Сообщения: 376
Это у вас двусвязный список.
Всё зависит от количества элементов. Если элементов действительно много (сотни и более) и нужен быстрый поиск - гуглите сбалансированное дерево поиска. Минусы:
1. Расход памяти программ под организацию (код), ибо алгоритмы сложнее чем линейный поиск.
2. Вставка и удаление элемента, скажем так, несколько затратные по времени операции (связано с перестройкой дерева).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 24 янв 2018, 20:40 
Старожил
Аватара пользователя

Зарегистрирован: 27 мар 2015, 04:10
Сообщения: 1931
Откуда: Харьков
Да, я со списками дружу, тут проблем нет, просто хочется понимать - является ли такой подход оптимальный именно для МК?
Вот например по сути можно же писать напрямую в память за областью данных приложения, но там есть риски затереть другие данные или влезть в стек.
Так же можно сразу массив по максимум объявить, и к нему обращаться, но вроде тоже как-то не кошерно получается, хотя там уже меньше заморочек с выделением памяти и пр.
Вообщем ищу вариант что оптимальнее.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 24 янв 2018, 21:04 
Старожил
Аватара пользователя

Зарегистрирован: 11 апр 2016, 18:04
Сообщения: 2785
Откуда: Китай, Пекин
список для вашего случая не лучший выбор. оптимальнее использовать Hash. например такой я использовал и мне понравилось. начать знакомство можно отсюда

_________________
unirail.org


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 24 янв 2018, 21:49 
Старожил

Зарегистрирован: 05 фев 2015, 23:41
Сообщения: 376
cheblin, вы структуру ТС видели ?
Код:
typedef struct Device
{
  uint16_t Address;
  uint8_t Type;
  uint8_t Config;     //[0] - Confirmed, [1] - Online, [2] - Enabled
  uint32_t Salt;      //Random salt for CRC32 checksum
  dLink    Next;
  dLink    Prev;
} xDevice;

uthash User Guide писал(а):
Overhead
The hash handle consumes about 32 bytes per item on a 32-bit system, or 56 bytes per item on a 64-bit system.

Да и ТЗ, вообще говоря, озвучено не полностью. Сколько ожидается элементов максимум ? Каков доступный объем памяти ? Насколько быстро нужно искать/вставлять/удалять ? При малом количестве элементов и линейный поиск вполне себе решение.

alexsam писал(а):
..писать напрямую в память за областью данных приложения, но там есть риски затереть другие данные или влезть в стек.

Зачем самодеятельностью заниматься ? Определится нужно - либо статический массив, либо динамическая структура. Преимущество статики - скорость и отсутствие накладных расходов на организацию структуры (Prev, Next, etc.) А если динамическая структура, то без malloc (или её вариантов) не обойтись.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 24 янв 2018, 22:25 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2638
Откуда: Санкт-Петербург
alexsam, вроде связные списки сами по себе никто не любит - для пачки однотипных данных все предпочитают вектор (хотя бы для уменьшения количества malloc/free: если перевыделять память при удвоении массива - амортизированная сложность добавления элемента получается O(1)).
Поиск - можно хэш-таблицу, но в вашем случае (16-битный адрес) сойдёт и дерево: его глубина ограничена 16, а поиск элемента - просто последовательный выбор битов адреса и движение по дереву.
Впрочем, если значений мало, а добавляются они редко - можно вообще замутить сортированный массив с двоичным поиском по нему.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 24 янв 2018, 22:33 
Старожил
Аватара пользователя

Зарегистрирован: 11 апр 2016, 18:04
Сообщения: 2785
Откуда: Китай, Пекин
UnКаЙF писал(а):
cheblin, вы структуру ТС видели ?

uthash User Guide писал(а):
Overhead
The hash handle consumes about 32 bytes per item on a 32-bit system, or 56 bytes per item on a 64-bit system.


спасибо, как-то пропустил это место...работа была со строками, не обратил внимания. полезно.

_________________
unirail.org


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 24 янв 2018, 22:40 
Старожил

Зарегистрирован: 05 фев 2015, 23:41
Сообщения: 376
aamonster: Зы. Честно говоря, никогда не пробовал STL на микроконтроллерах :) Векторы, итераторы... Насколько оно там оптимально будет ?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 24 янв 2018, 22:53 
Старожил
Аватара пользователя

Зарегистрирован: 22 июл 2017, 11:48
Сообщения: 4039
UnКаЙF писал(а):
cheblin, вы структуру ТС видели ?.

:))))) хахаха, ну cheblin у нас в последнее время конкретно двинулся на идее смартфона, посему ничего акромя него и не видит :)))

alexsam писал(а):
MC:
uint16_t Address;

это поле содержит некие числа, которые и надо найти, так?
Заведите массив этих структур (или массив адресов-указателей на структуру, получаемые из malloc) и выполняйте поиск сравнением первого элемента структуры. А в отдельной переменной храните число использованных структур. Либо выполняйте просмотр до тех пор, пока очередной элемент не будет =0. Правда, массив структур должен быть инициализован нулями, а при удалении структуры - заменять ее нулями.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 24 янв 2018, 23:13 
Старожил
Аватара пользователя

Зарегистрирован: 11 апр 2016, 18:04
Сообщения: 2785
Откуда: Китай, Пекин
alexsam писал(а):
Вообщем ищу вариант что оптимальнее.

тогда массив (динамический/статический в зависимости от задачи), поддерживать элементы сортированными, и бинарный поиск.

_________________
unirail.org


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 24 янв 2018, 23:25 
Старожил
Аватара пользователя

Зарегистрирован: 22 июл 2017, 11:48
Сообщения: 4039
Сортировать лучше не элементы в виде структуры целиком, а лишь указатели на структуры.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 24 янв 2018, 23:29 
Старожил

Зарегистрирован: 05 фев 2015, 23:41
Сообщения: 376
cheblin, имхо, конечно, но уж лучше дерево, чем при вставке весь массив двигать. Хотя х.з...
ТС нужно определитья с максимальным количеством элементов. Я не думаю, что у stm32F1 есть память под 2^16 структур.
Кстати, народ, а кто что думает по поводу коллизий при использовании хэш-таблиц. Всё-ж таки с аппаратурой работаем, не в тексте ищем предложения...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 24 янв 2018, 23:49 
Старожил

Зарегистрирован: 28 дек 2010, 23:30
Сообщения: 340
Читай Вирта "Алгоритмы и структуры данных". Это основы, с этого вообще начинать следует.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 25 янв 2018, 01:31 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2638
Откуда: Санкт-Петербург
UnКаЙF, не-не-не, когда мало памяти - stl сразу идёт лесом, я просто терминологию использовал.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 25 янв 2018, 02:26 
Старожил
Аватара пользователя

Зарегистрирован: 27 мар 2015, 04:10
Сообщения: 1931
Откуда: Харьков
Цитата:
Сколько ожидается элементов максимум ? Каков доступный объем памяти ? Насколько быстро нужно искать/вставлять/удалять ? При малом количестве элементов и линейный поиск вполне себе решение.

Сколько элементов - ХЗ, на данный момент пока память не закончится. А вообще сейчас тестируется около 50 девайсов +/-.
Доступная память - сейчас примерно 10Кб
Искать нужно максимально быстро, потому и сделал двунаправленный список. т.е. приходит запрос - ищу от текущего элемента в минимальную сторону, если не нашел то тогда уже с начала и до того элемента где начал поиск (тут конечно есть еще куда оптимизоровать, но пока оставим).
Вот и я думаю что пока линейный поиск самое оно. Но мало ли, может для МК есть какие-то интересные варианты которые Д. Кнут не описывал ))


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 25 янв 2018, 03:17 
Старожил

Зарегистрирован: 10 окт 2014, 00:48
Сообщения: 6466
Делайте сразу список, упорядоченный по "адресам". Поля dLink нафиг не нужны.
Память выделять не надо (опять же, это не IBM PC с 32Gb), сделайте статический выделенный массив.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 25 янв 2018, 08:44 
Старожил
Аватара пользователя

Зарегистрирован: 11 апр 2016, 18:04
Сообщения: 2785
Откуда: Китай, Пекин
BusMaster писал(а):
Сортировать лучше не элементы в виде структуры целиком, а лишь указатели на структуры.

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

_________________
unirail.org


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 25 янв 2018, 08:54 
Старожил
Аватара пользователя

Зарегистрирован: 11 апр 2016, 18:04
Сообщения: 2785
Откуда: Китай, Пекин
alexsam писал(а):
пока память не закончится. А вообще сейчас тестируется около 50 девайсов +/-.
Доступная память - сейчас примерно 10Кб
Искать нужно максимально быстро, потому и

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

alexsam писал(а):

Искать нужно максимально быстро,

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

alexsam писал(а):

Вот и я думаю что пока линейный поиск самое оно.

однозначно нет.

_________________
unirail.org


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 25 янв 2018, 09:24 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2638
Откуда: Санкт-Петербург
Глянул повнимательней на данные... Однозначно список и дерево с выделением каждого элемента в куче идут лесом: на 8 байт данных - оверхед в виде 8 байт указателей + оверхед кучи (не помню точно, но минимум 1 счётчик или указатель + выравнивание). Итого объект вместо 8 байт займёт 20-32, и это не считая расходов на фрагментацию кучи. Плюс время на malloc/free.

Так что данные хранить однозначно в векторе (массиве). Дальше делится на варианты:
- по выделению (от простого к сложному)
1. Фиксированный (тупо, надёжно, размер ограничен)
2. При переполнении - выделить массив вдвое больше (цена - копирование массива изредка)
3. Массив массивов (сложнее код)
- по заполнению (опять от простого к сложному)
1. Несортированный (долгий поиск, быстрая вставка)
2. Сортированный (быстрый поиск, долгая вставка - по времени как у вас сейчас поиск)
3. Структура (дерево или ещё что) для поиска поверх (поиск и вставка быстрые, но оверхед по памяти).

Я бы выбрал 2-2, или даже 2-1, если поиск за O(n) годится.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 25 янв 2018, 09:28 
Старожил
Аватара пользователя

Зарегистрирован: 22 июл 2017, 11:48
Сообщения: 4039
cheblin писал(а):
BusMaster писал(а):
Сортировать лучше не элементы в виде структуры целиком, а лишь указатели на структуры.

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

Ну вы это ващщееее уже "тук-тук". Не подумавши брякнули. Размер той структуры как минимум (2+1+1+4 + 2*<как_минимум_1_байт>) = 10+ байт. А размер указателя, который суть адрес = 4 байта и может перемещаться за один раз, поскольку 32-битная архитектура. Адрес структуры - это адрес её первого элемента. Остальные элементы структуры идут друг за другом.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 25 янв 2018, 10:29 
Старожил
Аватара пользователя

Зарегистрирован: 11 апр 2016, 18:04
Сообщения: 2785
Откуда: Китай, Пекин
BusMaster писал(а):
cheblin писал(а):
BusMaster писал(а):
Сортировать лучше не элементы в виде структуры целиком, а лишь указатели на структуры.

у него размер структуры не на много длиней указателя, а судя по чипу даже короче.
Размер той структуры как минимум (2+1+1+4 + 2*<как_минимум_1_байт>) = 10+ байт. А размер указателя, который суть адрес = 4 байта и может перемещаться за один раз, поскольку 32-битная архитектура. Адрес структуры - это адрес её первого элемента. Остальные элементы структуры идут друг за другом.


2+1+1+4 - это понятно. окуда остальное, не понятно. + нужно добавить память на указатель в массиве.

BusMaster писал(а):
4 байта и может перемещаться за один раз,

в чём ценность этого если при вставки в сортированный массив иногда придется освобождая место и перемещать много указателей на структуры и делать это разумнее с memcpy?


ещё один минус с указателями - фрагментация памяти и тормоза на malloc каждого нового элемента
в статическом масиве структур нужная память уже отведена. нужно только иногда смещение жлементов.

так что .... только массив сортированных структур.

_________________
unirail.org


Последний раз редактировалось cheblin 25 янв 2018, 10:54, всего редактировалось 6 раз(а).

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 25 янв 2018, 10:32 
Старожил
Аватара пользователя

Зарегистрирован: 11 апр 2016, 18:04
Сообщения: 2785
Откуда: Китай, Пекин
aamonster писал(а):

2. Сортированный (быстрый поиск, долгая вставка - по времени как у вас сейчас поиск)

при варианте массива структур нет затрат времени на malloc/free каждого нового элемента.
только затраты на поиск и смешение элементов для отведения места.
иногда затраты при увеличении массива, если массив динамический

aamonster писал(а):
3. Структура (дерево или ещё что) для поиска поверх (поиск и вставка быстрые, но оверхед по памяти).


Sorted array with binary search
search: O(log(n))
Binary search tree
search: O(log(n))

+ при вставке элемента придется дерево обслуживать: создавать узел, искать ему место, вставлять... в контексте обсуждаемых данных это не айс.

_________________
unirail.org


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 25 янв 2018, 12:02 
Старожил
Аватара пользователя

Зарегистрирован: 22 июл 2017, 11:48
Сообщения: 4039
cheblin писал(а):
2+1+1+4 - это понятно. окуда остальное, не понятно. .

Слухайте, ну вы уже вааще в упор не видите или прикалываетесь
Вот это:
typedef struct Device
{
uint16_t Address;
uint8_t Type;
uint8_t Config; //[0] - Confirmed, [1] - Online, [2] - Enabled
uint32_t Salt; //Random salt for CRC32 checksum
dLink Next; // это переопределенный пользователем тип неизвестной для нас длины
dLink Prev; // это переопределенный пользователем тип неизвестной для нас длины
} xDevice;

Вот отсюдава и 10+. А вдруг тип dLink определен тоже как структура размером в "дохера" элементов? Про вложенные структуры не слыхивали разве ж...
Зато память под указатели на структуры - оверхедом всего по одному слову (4 байта) на каждую структуру в целом (а НЕ на каждый элемент структуры). Блин, вы чо, невкурсах, че такое структура и как она хранится?
Структуры можно добавлять как угодно, хоть последовательно в конец, хоть в перемешку с другими блоками malloc, а сортировке подвергается только лишь указатели на структуры. Массив указателей, внутри массива указатели можно переставлять по возрастанию значения в первом элементе структуры. И вот эти операции проводятся без физического копирования самой структуры. Блин, чуваки, это же, епт, прописные истины, ептыть а.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 25 янв 2018, 12:28 
Старожил
Аватара пользователя

Зарегистрирован: 27 мар 2015, 04:10
Сообщения: 1931
Откуда: Харьков
Добавил в первый пост, а то действительно как-то протупил
Код:
typedef struct Device *dLink;

чтоб вы не подрались :)

Цитата:
Структуры можно добавлять как угодно, хоть последовательно в конец, хоть в перемешку с другими блоками malloc, а сортировке подвергается только лишь указатели на структуры. Массив указателей, внутри массива указатели можно переставлять по возрастанию значения в первом элементе структуры. И вот эти операции проводятся без физического копирования самой структуры. Блин, чуваки, это же, епт, прописные истины, ептыть а.

Да, я так и делаю, сортирую только указатели. Копирование всей структуры не нужно.
Ну точнее я не сортирую, а просто вставляю новые данные куда malloc скажет, а потом сами указатели меняю в цепочке на эту структуру чтоб был список сортированный.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 25 янв 2018, 12:49 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2638
Откуда: Санкт-Петербург
BusMaster, если храним в массиве - Next/Prev не нужны.
Итого при хранении в массиве - 8 байт на элемент, вдвое больше размера указателя.
Конечно, переслать 8 байт при "раздвигании" массива структу медленнее, чем 4 при раздвигании массива указателей, зато при поиске не будет лишнего indirection - так что по скорости, скорей всего, выиграем. А уж по памяти в полтора раза - само собой.

(а связный список, особенно при выделении каждого объекта в куче - это вообще ахтунг, на ровном месте жрём в 2-4 раза больше памяти, ничего не выигрывая... Вообще rule of thumb: не выделять много мелких однотипных объектов в куче).


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 60 ]  На страницу 1, 2, 3  След.


Часовой пояс: UTC + 5 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: mChel


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Русская поддержка phpBB