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

Question

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

Но порядок этих элементов важен, а то задачу можно было бы просто решить 3-мя битами.
Представить в битах такой контейнер можно так: первые 3 бита определяют первый элемент (или 000 если контейнер пуст), вторые 2 бита определяют второй элемент. Именно 2 оставшихся бита, т.к. один бит уже исключен. Ну и соответственно, если 00, то контейнер закончился. Ну и последний 1 бит определяет наличие последнего элемента, или 0.
Соответственно для реализации такого контейнера нужно 3+2+1==6 бит.
Алгоритм хорошо обобщается на N уникальных элементов.

Вопрос - кто то где то видел реализацию такого контейнера, или что-то аналогичное или похожее?

#c++ #embedded #programming #russian

0

23.05.2023

5 ответов

29 просмотров

Int Unsigned Автор вопроса

Evgeny Sh.
Всего возможно 3! = 3*2*1 = 6 перестановок элемент...

Не перестановок, т.е. не N!, а суммирования от N до 1. То есть в моей схеме для 4 элементов нужно 10 бит, а не 4!==24. На каждом следующем шаге мы можем сжимать последовательность на один использованный бит.

0

23.05.2023

Т

Int Unsigned
Не перестановок, т.е. не N!, а суммирования от N д...

Ах, ну тоесть всё что больше ~16 элементов = оверхед? Я всё ещё не понимаю для чего и зачем это и при чём тут поля с битами

0

23.05.2023

Int Unsigned Автор вопроса

Т
Ах, ну тоесть всё что больше ~16 элементов = оверх...

Достаточно много приложений, когда возможно не более N элементов. Индексы по полям, например. 16 в этом случае это овердохрена.

0

23.05.2023

Т

Int Unsigned
Достаточно много приложений, когда возможно не бол...

Ну это долбёжка в битовые оптимизации. Силами компилятора делать такое сложно + там всёравно будет много логики-инструкций. Это если у вас RAM пару килобайт, а ROM под сотни, может и имеет смысл. А в остальном это мусор. Экономить пару байтов там где у тебя память в мегабайтах исчисляется, ну такое

0

23.05.2023

Evgeny Sh. · Accepted Answer

Всего возможно 3! = 3*2*1 = 6 перестановок элементов. 6 значений влезут в 3 бита. Ни моя схема, ни ваша схема на N элементов с большим N не скейлятся, потому что объем N!/8 битов (у меня) или N*(N+1)/2 битов (у вас) это слишком много Если совершенно точно известно что элементов не больше N, то используют static_vector. Там из доп памяти только 4 байта = размер вектора

170 похожих чатов

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

5 ответов

Похожие вопросы