Easyelectronics.ru

Электроника для всех
Текущее время: 19 сен 2019, 01:29

Часовой пояс: 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
Сообщения: 2367
Откуда: Китай, Пекин
список для вашего случая не лучший выбор. оптимальнее использовать 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
Сообщения: 2619
Откуда: Санкт-Петербург
alexsam, вроде связные списки сами по себе никто не любит - для пачки однотипных данных все предпочитают вектор (хотя бы для уменьшения количества malloc/free: если перевыделять память при удвоении массива - амортизированная сложность добавления элемента получается O(1)).
Поиск - можно хэш-таблицу, но в вашем случае (16-битный адрес) сойдёт и дерево: его глубина ограничена 16, а поиск элемента - просто последовательный выбор битов адреса и движение по дереву.
Впрочем, если значений мало, а добавляются они редко - можно вообще замутить сортированный массив с двоичным поиском по нему.


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

Зарегистрирован: 11 апр 2016, 18:04
Сообщения: 2367
Откуда: Китай, Пекин
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
Сообщения: 3618
UnКаЙF писал(а):
cheblin, вы структуру ТС видели ?.

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

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

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


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

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

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

_________________
unirail.org


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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: 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
Сообщения: 2619
Откуда: Санкт-Петербург
UnКаЙF, не-не-не, когда мало памяти - stl сразу идёт лесом, я просто терминологию использовал.


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

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

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


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

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


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

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

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

_________________
unirail.org


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

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

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

alexsam писал(а):

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

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

alexsam писал(а):

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

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

_________________
unirail.org


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

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2619
Откуда: Санкт-Петербург
Глянул повнимательней на данные... Однозначно список и дерево с выделением каждого элемента в куче идут лесом: на 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
Сообщения: 3618
cheblin писал(а):
BusMaster писал(а):
Сортировать лучше не элементы в виде структуры целиком, а лишь указатели на структуры.

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

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


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

Зарегистрирован: 11 апр 2016, 18:04
Сообщения: 2367
Откуда: Китай, Пекин
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
Сообщения: 2367
Откуда: Китай, Пекин
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
Сообщения: 3618
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
Сообщения: 2619
Откуда: Санкт-Петербург
BusMaster, если храним в массиве - Next/Prev не нужны.
Итого при хранении в массиве - 8 байт на элемент, вдвое больше размера указателя.
Конечно, переслать 8 байт при "раздвигании" массива структу медленнее, чем 4 при раздвигании массива указателей, зато при поиске не будет лишнего indirection - так что по скорости, скорей всего, выиграем. А уж по памяти в полтора раза - само собой.

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


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

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


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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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

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