LINUX.ORG.RU

Посоветуйте структуру данных

 ,


1

3

Хочу структуру данных удовлетворяющую следующим условиям:

- Хранит в себе пары ключ-значение. Ключи - числа от 0 до 4095. Значения - uint32_t, но в целом вряд ли принципиально для алгоритма.

- Элементы отсортированы по возрастанию ключа - имея в каком-то виде указатель на элемент можно со сложностью O(1) получить указатель на следующий или на предыдущий (то есть возможна дешёвая итерация в обе стороны, полный обход списка в порядке сортировки и обратном имеет сложность O(N) - просто выполнить O(1) для каждого элемента) в порядке сортировки ключей.

- Существует операция поиска элемента по ключу со сложностью не более O(logN). При этом если элемента с таким ключом нет, должен находиться элемент с максимальным ключом меньше запрошенного. Функция поиска возвращает в каком-то виде указатель на элемент, который позволяет не только узнать его значение, но и выполнять итерирование, а также вставку и удаление элементов перед или после него.

- Операции добавления и удаления элементов - дешёвые, но выполняются значительно реже итерирования. Сложность не более O(logN).

- Эффективность по памяти. Требуется добавлять необходимый минимум служебной информации к элементам (так как сами элементы всего лишь 6 байт). Ну и само собой нельзя взять и выделить память сразу под 4096 возможных элементов, когда в реальности может лежать лишь пара сотен.

- Операции итерирования и поиска элементов не должны приводить к модификации структуры данных, чтобы можно было использовать RW блокировки и несколько потоков могли одновременно читать одну и ту же структуру (невозможность записи без эксклюзивной блокировки это нормально).

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

Как я понимаю, разумно использовать какой-нибудь std::vector, в который запихнуть элементы с обвязкой, а указатели между элементами (для построения какого-нибудь двоичного дерева) делать в виде 16-битных индексов (ведь максимальное число уникальных ключей всего 4096). Вопрос в том какую структуру данных построить поверх вектора.

★★★★★

Ответ на: комментарий от rupert

Операции добавления и удаления элементов … Сложность не более O(logN)

utf8nowhere ★★★ ()
Ответ на: комментарий от rupert

iterator erase(const_iterator p); Effects: Erases the element pointed to by p.

Returns: Returns an iterator pointing to the element immediately following q prior to the element being erased. If no such element exists, returns end().

Complexity: Linear to the elements with keys bigger than p

Note: Invalidates elements with keys not less than the erased element.

Complexity: Linear to the elements with keys bigger than p

Вставка и удаление O(N), а не O(1).

Вообще, меня, пожалуй устроило бы распухание контейнера (типа если положить туда 1000 элементов, а потом удалить, то контейнер уже никогда не станет прежним). Типа при удалении элемента не удалять его из вектора, а класть на его место однонаправленный связанный список свободных ячеек (uint16_t заведомо меньше хранимых данных, так что его легко хранить на месте ненужного элемента). Соответственно, при добавлении элемента увеличивать вектор только если не осталось свободных ячеек.

KivApple ★★★★★ ()

Т.е. у тебя всего 4096 элементов может быть в структуре, в максимуме? И храниться в ней будут только 32-битные числа? И ты паришься над компактностью структуры?)

menangen ★★★★★ ()

если все операции не более логарифма, то никаких вариантов кроме сбалансированного дерева (т.е. типа std::set) просто нет

Lrrr ★★★ ()

Как я понимаю, разумно использовать какой-нибудь std::vector, в который запихнуть элементы с обвязкой, а указатели между элементами (для построения какого-нибудь двоичного дерева) делать в виде 16-битных индексов (ведь максимальное число уникальных ключей всего 4096).

Почему бы и нет. Может быть (если значения < 2^20) получится упаковать туплы и в 4 байта.

Вопрос в том какую структуру данных построить поверх вектора.

А у тебя много вариантов? Очевидно что дерево или скиплист.

slovazap ★★★★★ ()
Ответ на: комментарий от Lrrr

если все операции не более логарифма, то никаких вариантов кроме сбалансированного дерева (т.е. типа std::set) просто нет

Скиплист.

slovazap ★★★★★ ()
Ответ на: комментарий от Lrrr

Там под капотом красно-черное дерево. Я не понимаю, можно ли его итерировать без введения пары дополнительных указателей в элемент (next, prev). А то это выходит нужно 5 указателей на элемент (parent, left, right, next, prev). Это 2 * 5 = 10 байт. Это значит, что данные увеличатся с 6 до 16 байт. Практически в 3 раза.

KivApple ★★★★★ ()

а указатели между элементами (для построения какого-нибудь двоичного дерева) делать в виде 16-битных индексов

А нулевым указателем что будет?

utf8nowhere ★★★ ()

нельзя взять и выделить память сразу под 4096 возможных элементов

обоснуй. 4096 * 6 = 24576 байт, и без всякого геморроя.

olelookoe ★★ ()
Последнее исправление: olelookoe (всего исправлений: 1 )
Ответ на: комментарий от utf8nowhere

Так как количество элементов заведомо не превышает 4096, можно взять любое число больше либо равное 4096 как некорректное значение. Например, 0xFFFF

KivApple ★★★★★ ()
Ответ на: комментарий от utf8nowhere

меня в школе, а тебя где?

сами элементы всего лишь 6 байт (c) ТС

Ключи - числа от 0 до 4095 (c) ТС

твои тараканы тебе какие-то неправильные числа подсказывают.

olelookoe ★★ ()
Ответ на: комментарий от utf8nowhere

Не понял вопроса.

Я имею ввиду, что вместо Element *parent, *left, *right использовать uint16_t задающий номер элемента в векторе. Таким образом и указатели не будут инвалидироваться при росте вектора, и размер структуры будет меньше.

В качестве NULL просто пихаем 0xFFFF, так как размер вектора заведомо не может превзойти 4096 (количество уникальных ключей).

KivApple ★★★★★ ()
Ответ на: комментарий от olelookoe

Учись читать:

Ключи - числа от 0 до 4095. Значения - uint32_t

Итого, 4096*4 байт под значения плюс 4096/8 под битмап.

сами элементы всего лишь 6 байт (c) ТС

Очевидно, это про реализацию когда мы не выделяем память под все 4096 элементов при любой заполненности, а организуем ключ+значение в одну структуру, плюс добавляем к ним всякие «указатели» для организации структур, например, в бинарное дерево.

utf8nowhere ★★★ ()
Ответ на: комментарий от KivApple

Тупанул, 16 бит это же от 0 до 65535 >_<

Ну тогда при твоих требованиях, наверное, std::set/std::map с кастомным аллокатором поверх вектора, где кастомными поинтерами будут 16-битные смещения.

Если бы у тебя было поменьше требований к обходу или вставке с итератором, то задача ложилась бы на что-нибудь типа https://en.wikipedia.org/wiki/Predecessor_problem, но там замороченные структуры данных. По крайней мере так выглядят.

utf8nowhere ★★★ ()
Ответ на: комментарий от KivApple

мущщина, у вас тут показания расходятся

Значения - uint32_t

сами элементы всего лишь 6 байт

olelookoe ★★ ()
Ответ на: комментарий от olelookoe

+100500. Остальные варинаты напоминают преждевременную оптимизацию. Даже если вдрук в структуре один актуальный элемнт это даст экомию всего лишь в три раза (4096*2 все равно выделять же). На самом деле выделять больше т.к. нужно поддеживать односвязный списко еще и косвенную адресацию при попытках экономить.

Из нетривиального тут только

  • Существует операция поиска элемента по ключу со сложностью не более O(logN). При этом если элемента с таким ключом нет, должен находиться элемент с максимальным ключом меньше запрошенного.

В дырках на месте ключа можно хранить ключ предыдущего валидного элемента (выделив один бит в ключе на пометку невалидности), но тогда ломается вот это

  • Операции добавления и удаления элементов - дешёвые, но выполняются значительно реже итерирования. Сложность не более O(logN).

При добавлении придется перебивать дырки, это O(N). Но КМК это не так страшно.

Всякие деревья на таком размере ИМНО будут хуже по совокупности характеристик.

AntonI ★★★ ()
Ответ на: комментарий от utf8nowhere

мы не выделяем память под все 4096 элементов при любой заполненности, а организуем ключ+значение в одну структуру, плюс добавляем к ним всякие «указатели» для организации структур, например, в бинарное дерево.

И это будет хуже чем просто вектор из 4096 пар 2+4 байта. Ваш К.О.

ЗЫ с т.з. выравнивания лучше отдельно вектор из ключей и вектор из значений конечно же.

AntonI ★★★ ()
Последнее исправление: AntonI (всего исправлений: 1 )
Ответ на: комментарий от utf8nowhere

необходимый минимум служебной информации к элементам

Готов услышать твои предложения как сделать что-то работающее как B+ дерево, но с меньшими затратами на «служебную информацию».

no-such-file ★★★★★ ()
Ответ на: комментарий от KivApple

Этих структур могут быть тысячи. Просто в каждой не более 4096 элементов. Но их много.

Что бы что то вменяемое тут предложить нужно знать:

  1. среднюю заполненность одной структуры

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

AntonI ★★★ ()

Просто массив от 4к элементов. Бинго

yoghurt ★★★★★ ()
Ответ на: комментарий от slovazap

список с пропусками - по сути то же самое сбалансированное дерево, только описанное в других терминах. Не проще в реализации и не быстрее в работе.

Lrrr ★★★ ()
Ответ на: комментарий от Lrrr

список с пропусками - по сути то же самое сбалансированное дерево, только описанное в других терминах

По сути да.

Не проще в реализации и не быстрее в работе.

Depends. Случайная балансировка сильно проще честной RB в реализации, и скиплист проще сделать с минимальным лок контеншн.

slovazap ★★★★★ ()
Ответ на: комментарий от slovazap

Случайная балансировка сильно проще честной RB в реализации

Немножко вклинюсь, есть же ещё и AA-tree [1] [2] .Сложность и скорость всё тоже, что и RB-tree (это в общем-то видоизменённое оно), но в реализации очень сильно проще.

SkyMaverick ★★★★ ()
Ответ на: комментарий от SkyMaverick

Самое простое в реализации, наверное, scapegoat tree. Правда, логарифмы получаются только амортизированные.

utf8nowhere ★★★ ()

По описанию очень похоже на связку std::vector<std::pair<uint16_t, uint32_t>> и std::upper_bound. Просто массив всегда поддерживать в отсортированном состоянии. Если элементы добавляются по одному, то проблем не будет. Удовлетворяет всем требованиям кроме инвалидации указателей при модификации структуры.

Vinick ★★ ()
Для того чтобы оставить комментарий войдите или зарегистрируйтесь.