Easyelectronics.ru

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

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



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

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

Зарегистрирован: 11 апр 2016, 18:04
Сообщения: 2373
Откуда: Китай, Пекин
BusMaster писал(а):
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.


а так видно?

Next, Prev уходят при хранении в массиве.

_________________
unirail.org


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

Зарегистрирован: 22 июл 2017, 11:48
Сообщения: 3624
Куда уходят? Из структуры они никуда не уходят. Если объявлены они в ней, то место под них выделено последовательно сразу за предыдущим элементом. А если dLink - указатель, значит под него выделено по 4 байта (32-битное адресное пространство). Чтобы эти указатели не хранить вместе со структурой, надо структуру переписать, стерев лишний текст кнопочкой Backspace.
Слушайте, cheblin, вы уже совсем свихнулись на своем андроиде.
:) Дело не в "подрались/не подрались", а дело в том, что не надо выдумывать того, чего не написано было изначально.
Да черт с ним с Next Prev, не в этом суть. Суть в том, что размер структуры в несколько раз больше, чем размер адреса (указателя) структуры.

Malloc представляет собой уже готовый механизм на тот случай, когда заранее неизвестно число хранимых элементов. Несмотря на то, что он медленный, и у него оверхед по 8 байт для заголовка на каждый выделяемый блок, этот механизм в принципе довольно хорошщо подходит. Иначе вам придется вручную делать те же операции, что и стандартный malloc.

Тут кое-кто высказывался, что типа если статический массив, и если при добавлении очередного элемента не хватит размера статического массива, то надо его увеличить вдвое. Хочу спросить - КАК его увеличить вдвое во время работы МК? Как? За счет каких областей? Ведь для статических массивов распределением памяти занимается компилятор. Задумали вы увеличить стат.массив вдвое - а там - другие переменные, поставленные компилятором. Ну и как? Увеличить вы можете, МК и не возразит, да и Си сам по себе не имеет контроля за пересечением границы обозначенного массива. Но безропотно затрет все, что попало под увеличенную область. Это что касается статического распределения.

Для malloc же на этапе компиляции выделяется куча - банально диапазон памяти. Если во время работы МК при очередном запросе механизм malloc определит, что диапазон исчерпан, он не выделит память и вернет NULL. Ситуация NULL должна обрабатываться программно. Как именно - это уже проблема программиста.

ЗЫ. В заголовке malloc-блока уже присутствует указание на следующий блок, а так же флаги статуса блока (занят, свободен)


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

Зарегистрирован: 11 апр 2016, 18:04
Сообщения: 2373
Откуда: Китай, Пекин
BusMaster писал(а):
Куда уходят? Из структуры они никуда не уходят. Если объявлены они в ней, то...

ок. всем всё понятно.

_________________
unirail.org


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

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2619
Откуда: Санкт-Петербург
BusMaster, можете переспросить у alexsam, но imho довольно очевидно, что Next/Prev - это именно поля для создания связного списка. Так что да, для хранения в массиве "надо структуру переписать, стерев лишний текст кнопочкой Backspace" и уменьшить в 2 раза.

Насчёт увеличения вдвое - касалось не статического, а динамического массива (почему и использовал слово "вектор"; обратите внимание - в том моём комменте слова "статический" вообще нет).
Стандартная процедура - просто чтобы звать malloc/realloc/free как можно реже (дорогая операция) и только для больших блоков (чтобы уменьшить оверхед)


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

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

aamonster, бесполезно. есть такая "особая" категория... им главное не мешать.

_________________
unirail.org


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

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

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2619
Откуда: Санкт-Петербург
Кстати, не совсем по теме (тут вроде ни к чему и не окупится), но близкая "по духу" интересная структура данных - Splay-дерево (скошенное дерево): двоичное дерево, сбалансированное так, чтобы часто используемые данные искались быстрее.
https://habrahabr.ru/company/spbau/blog/210296/


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

Зарегистрирован: 24 июл 2012, 13:54
Сообщения: 849
Пять копеек в обсуждение.

Преимущество встроенного связного списка (когда поля линка находятся непосредственно в структуре данных объекта) еще в том, что такой объект может самостоятельно удалить себя из списка, не обращаясь к управляющему контейнером объекту. Это полезно, допустим, для организации списка процессов. Процесс просто переносит сам себя из списка run в список wait без каких либо накладных расходов.

Встроенная линковка также позволяет линковать объекты разной природы. Так в одном списке могут оказаться статические и динамические объекты (опять же пример про процессы, где часть системных процессов может быть создана статически).


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

Зарегистрирован: 24 июл 2012, 13:54
Сообщения: 849
ПС. В обсуждении выше использование связного списка противопоставляют хранению в массиве. И ссылаются на накладные расходы по выделению маллоком каждой ноды. Хочу заметить, что этой проблемы можно избежать при выделении объектов списка из специального пула.


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

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2619
Откуда: Санкт-Петербург
Mirmik, поддержу. Это правильный метод, когда таки нужен связный список (или дерево, или ещё что, состоящее из объектов фиксированного размера).
Собственно, я такой подобное называл, когда перечислял варианты - структура (дерево или ещё что) для поиска поверх массива.
Но в данном случае imho перебор.


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

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

в случае списка соседние элементы и есть тот самый "контейнер"

Mirmik писал(а):
Процесс просто переносит сам себя из списка run в список wait без каких либо накладных расходов.

накладными расходами являются ссылки на соседние элементами. в обсуждаемом варианте эти расходы равны 100%. и как он может перенести себя в другой список wait не имея сссылки на него?
на сой взнляд списки хороши только тогда, алгоритм требует последовательно проходить по всем элементам списка и очень частое добавление удаление элементов.

_________________
unirail.org


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

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2619
Откуда: Санкт-Петербург
Кстати, быстрое добавление/удаление в связном списке - иллюзия. Чтобы добавить/удалить объект - надо вначале найти его место за O(n). Так что списки примерно всегда сосут, в реальности их имеет смысл использовать только для того, чтобы "прошить" уже имеющуюся структуру (когда объект ищем не по списку)


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

Зарегистрирован: 24 июл 2012, 13:54
Сообщения: 849
cheblin писал(а):
в случае списка соседние элементы и есть тот самый "контейнер"

Имеется ввиду, что у контейнера обычно есть "голова". Обычно, для удаления себя из контейнера объекту приходится запросить метод "головы", который будет долго искать объект в своих потрохах. Объекты встроенных связных списков могут проводить операции над собой не ссылаясь на голову.

cheblin писал(а):

накладными расходами являются ссылки на соседние элементами. в обсуждаемом варианте эти расходы равны 100%. и как он может перенести себя в другой список wait не имея сссылки на него?

Опять же речь идёт не о том, чтобы встроиться в wait, а о том, чтобы удалиться из run. Что до ссылок, то без них, увы не будет списка.


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

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

Зарегистрирован: 24 июл 2012, 13:54
Сообщения: 849
aamonster писал(а):
Кстати, быстрое добавление/удаление в связном списке - иллюзия. Чтобы добавить/удалить объект - надо вначале найти его место за O(n). Так что списки примерно всегда сосут, в реальности их имеет смысл использовать только для того, чтобы "прошить" уже имеющуюся структуру (когда объект ищем не по списку)

Это если нужен поиск. Для очередей и группирования поиск не нужен.


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

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2619
Откуда: Санкт-Петербург
Ну да, я имел в виду быстрое добавление/удаление в произвольное место списка.
А вот если только в голову/хвост (те самые очереди) - то _в качестве контейнера_ кольцевой буфер уделывает список почти всегда.
Так что опять же - имеет смысл делать списки, когда объекты лежат где-то ещё (очередь для объектов, принадлежащих кому-то другому; группировка внутри большого массива объектов и т.п.)


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

Зарегистрирован: 22 июл 2017, 11:48
Сообщения: 3624
Слушайте, ну вы наворотили уже хуйни дикой. Ваша беда в том, что вы пытаетесь мыслить категориями "балшых кампутеров", а тут - мелкий МК.
Есть такая категория, китайско-индусский кодописатель для Андроида. Вот после таких писателей все эти андроид-приложения постоянно валятся, виснут, жрут ресурсы так, что 2-ГГцевого 4-ядерного смартфона с гигабайтами памяти уже не хватает. Че, не так чтоль? Да так, так. Еще и "обновления" с новыми косяками каждые 2 недели выходят. Горе-пейсатели, блин...


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

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2619
Откуда: Санкт-Петербург
BusMaster, чья бы корова мычала? Вы, кажется, предлагаете делать malloc на каждые 8 байт?


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

Зарегистрирован: 22 июл 2017, 11:48
Сообщения: 3624
У меня нет коров. Я malloc не предлагал, он у топикстартера сразу был. И я, кажется, объяснил, что стандартный malloc на заголовок выделяет по 8 байт.
А как вы полагаете выделять ДИНАМИЧЕСКИ массив во время работы МК, если распределением памяти без malloc занимается компилятор? Я вот это вот и спрашиваю - КАК увеличить массив вдвое, если исходный массив занимает адреса, допустим, с 0x2000 0100 по 0x2000 01FF, а с адреса 0x2000 0200 по 0x2000 02010 компилятор положил другой массив? Ну КАК?
Что, опять начинается сказка про динамическое выделение памяти, начатая еще Арсюшей-бредогенератором, так чтоль? Ну уж спасибо, того бреда от Арсюши хватило доталова, ётс...


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

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2619
Откуда: Санкт-Петербург
Ещё раз. Следите за руками. malloc делается один раз в самом начале и realloc на каждое увеличение (удобно - на увеличение вдвое). При этом данные в массиве должны быть relocatable - что у ТС выполняется.

Хотя, конечно, если можно запилить статический массив на максимальное количество элементов - то ну его нафиг, этот malloc-realloc. Более того: если нет каких-то ещё выделений-освобождений памяти (чтобы мы могли делать или много записей в списке девайсов, или в каком-то другом массиве) - то тоже нет смысла в динамическом выделении, можно брать статический массив (в который всё равно поместится вдвое больше записей, чем сейчас помещается в список). 9 из 10 - у топик-стартера именно этот случай, и единственный довод в пользу динамического выделения - упрощение поддержки кода (нет константы (число записей), о которой нужно помнить).


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

Зарегистрирован: 22 июл 2017, 11:48
Сообщения: 3624
:))) Следите за ногами еще раз: чтобы выделить, увеличить, переместить и т.д., должна быть сначала обозначена эта куча - диапазон свободных адресов. Ну а как иначе то - иначе получите "отказ в выделении по причине неимения". Причем, чтобы увеличить вдвое методом копирования - надо иметь тройной запас. Физическая память не материализуется из воздуха, и не берется из "файла подкачки на блинах" по предложению легендарного Арсюши :))))
Поэтому, один хрен - расчет должен быть четко на максимально возможное кол-во хранимых элементов.


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

Зарегистрирован: 24 июл 2012, 13:54
Сообщения: 849
Хорошо. Давайте вернемся к задаче. Абстрактно сравнивать структуры данных можно долго.

У топикстартера есть два требования к структуре данных.
Первое - размер данных. Второе - поиск по полю адреса выполняется часто.
Кроме того есть ограничение. Топик стартер не хочет задавать длину контейнера константой времени компиляции.

Анализируем.
Связный список не есть оптимальная в данных условиях структура (много служебной информации, низкая скорость поиска).

Если длина контейнера - не константа времени компиляции, без динамического выделения не обойтись.
Наименьшее количество места в памяти занимают последовательные контейнеры. Получаем структуры данных типа vector или unbounded_array (unbounded_array меньше на одно поле.).
Самая быструю скорость поиска имеет хэштаблица, но она резко проваливает по размеру.

Судя по контексту задачи данные будут формироваться один раз (Не факт, но точно не часто). Следовательно деревья рассматривать не имеет смысла.

Из всего вышесказанного следует, что нас может заинтересовать shrink flat vector или flat unbounded array.
Короче, динамически выделенный массив объектов, имеющий длину ровно по количеству устройств и отсортированный в порядке возрастания ключа для организации бинарного поиска.

Собственно я к чему. Человечество знает много структур данных, обладающих определенными преимуществами и недостатками. Выбор структуры данных должен быть результатом взвешенного анализа. Не стоит иметь любимую структуру данных так же как самураю не стоит иметь любимый вид оружия.

P.S. коментарий к постам выше - грамотное использование метода reserve позволяет избежать реллокации для стандартного vector.


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

Зарегистрирован: 05 фев 2015, 23:41
Сообщения: 376
Итак:
1. По сообщениям ТС теоретический максимум ~640 элементов.
2. Я не думаю, что столько надо [имхо].
3. под ТЗ подходит:
3.1 статический массив.
3.2 упорядоченный (стат./дин.) массив
3.3 сбалансированное дерево поиска.

Для выбора среди предоставленных вариантов необходимо определить необходимое время поиска/вставки/удаления.
При динамической модели: выделяем память блоками или по одному элементу ?
Учитываем издержки malloc и на организацию структуры [если есть].
зы ? Делаем осознанный выбор.
Mirmik опередил :)


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

Зарегистрирован: 30 мар 2015, 23:56
Сообщения: 737
Я не понимаю в чём проблема, неужели трудно пройтись по списку, вам-же всего один параметр из структуры нужен, не всё.
Прямой поиск будет быстрее чем предварительная сортировка в массив. Там сначала нужно посчитать количество списков, пройдя их все подряд, потом выделить необходимое количество памяти, ещё раз пройтись по списку, и уже потом искать в массиве.
И вся эта канитель только для того чтобы не переписывать имеющийся алгоритм поиска...

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

_________________
Потоковая OS


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

Зарегистрирован: 27 мар 2015, 04:10
Сообщения: 1931
Откуда: Харьков
640 элементов точно не будет, но думаю что реально около сотни. Причем для тестов сейчас гоняем полтос с хвостиком.
Почему массив быстрее чем список? В списке мы так же движемся по элементам в памяти.
Вот пример поиска от начала списка для поиска адреса.
Код:
        dLink Cur           = rfDevices;
        if (Address == Cur->Address)
            {
                //Found it at first place
            }
        while (Cur->Next != NULL)
        {
            Cur = Cur->Next;
            if (Address == Cur->Address)
            {
                //Found it at somewhere
                break;
            }
        };


AVI-crak А мне не нужно сортировать готовый список, я список формирую сам и при формировании вставляю в нужное место элемент.


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

Зарегистрирован: 27 мар 2015, 04:10
Сообщения: 1931
Откуда: Харьков
Тут вот еще что, возможно, в будущем придется расширить структуру дополнив полем с ключом ASE или RSA для шифровки данных к девайсам. Так что в принципе после этого оверхед по памяти будет уже и не такой страшный с malloc.

А сегодня в завтрашний день не все могут смотреть. Вернее, смотреть могут не только лишь все.


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

Зарегистрирован: 05 фев 2015, 23:41
Сообщения: 376
alexsam писал(а):
Почему массив быстрее чем список

Мы всегда знаем где элемент Element_max/2.
Соответственно, начинаем поиск в нужной subполовине массива. [Всё-таки изучите алгоритмы и структуры данных]


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

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


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

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


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

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

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