У меня есть дерево. То есть нулевой узел с дочерними узлами и каждый дочерний содержит свои дочерние и так далее
При создании ноды пользователю отдается unsigned int ID. И вот по этому ID нужен доступ за константное время. Идеально было бы как-то отразить дерево в вектор и чтоб ID был номером элемента в векторе. Но как-то криво выходит. Две структуры для одного и того же. Криво.
Еще вариант, что ID — это собственно сам указатель, но не нравится он мне
Какие есть варианты?

Здравствуйте, Hоmunculus, Вы писали:

H>У меня есть дерево. То есть нулевой узел с дочерними узлами и каждый дочерний содержит свои дочерние и так далее
H>При создании ноды пользователю отдается unsigned int ID. И вот по этому ID нужен доступ за константное время. Идеально было бы как-то отразить дерево в вектор и чтоб ID был номером элемента в векторе. Но как-то криво выходит. Две структуры для одного и того же. Криво.
H>Еще вариант, что ID — это собственно сам указатель, но не нравится он мне
H>Какие есть варианты?

std::unordered_map?

Здравствуйте, Marty, Вы писали:

M>std::unordered_map?

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

Здравствуйте, Hоmunculus, Вы писали:

H>Здравствуйте, Marty, Вы писали:

M>>std::unordered_map?

H>ну там константа не всегда.

там есть метод reserve. Так что можно сказать, что всегда константа

Здравствуйте, sergii.p, Вы писали:

SP>Здравствуйте, Hоmunculus, Вы писали:

H>>Здравствуйте, Marty, Вы писали:

M>>>std::unordered_map?

H>>ну там константа не всегда.

SP>там есть метод reserve. Так что можно сказать, что всегда константа

Коллизии еще бывают

Здравствуйте, T4r4sB, Вы писали:

TB>Коллизии еще бывают

Сложность всё равно константная. Вряд ли у ТС подразумевалось именно константное время (не более XX микро/наносекунд), он, скорее всего, не совсем точно выразился

Здравствуйте, Marty, Вы писали:

M>Здравствуйте, T4r4sB, Вы писали:

TB>>Коллизии еще бывают

M>Сложность всё равно константная. Вряд ли у ТС подразумевалось именно константное время (не более XX микро/наносекунд), он, скорее всего, не совсем точно выразился

O(1) однозначно значит независимость от количества элементов. И если их станет миллиард, чтобы это не привело к просадкам. Разумеется, это не значит одно и то же количество миллисекунд на любой платформе

Здравствуйте, Hоmunculus, Вы писали:

TB>>>Коллизии еще бывают

M>>Сложность всё равно константная. Вряд ли у ТС подразумевалось именно константное время (не более XX микро/наносекунд), он, скорее всего, не совсем точно выразился

H>O(1) однозначно значит независимость от количества элементов. И если их станет миллиард, чтобы это не привело к просадкам. Разумеется, это не значит одно и то же количество миллисекунд на любой платформе

Именно это я и имел в виду. В хэш мапе, даже если есть коллизия это перебор нескольких элементов, и это всё равно O(1). Проблема может быть с рехэш при увеличении размера, но это можно решить, если это прям проблема.

Здравствуйте, Marty, Вы писали:

M>Сложность всё равно константная.

В среднем да, в худшем случае нет

Здравствуйте, T4r4sB, Вы писали:

M>>Сложность всё равно константная.

TB>В среднем да, в худшем случае нет

Скорее всего, ТСу нужна средняя сложность, вряд ли он делает систему жесткого реального времени. А резервирование/рехеширование можно делать по мере необходимости при вставке, или настроить max_load_factor, чтобы рехеши пореже происходили

Практические рекомендации

Всегда используйте reserve(), если знаете примерный размер

Оптимальный max_load_factor зависит от использования:

Для частых поисков: 0.7-0.8

Для экономии памяти: 1.0-1.5

Для минимизации рехеширования: 2.0-3.0

Профилируйте для нахождения оптимальных параметров

Рассмотрите альтернативные контейнеры, если рехеширование критично

Здравствуйте, Marty, Вы писали:

M>А резервирование/рехеширование можно делать по мере необходимости при вставке, или настроить max_load_factor, чтобы рехеши пореже происходили

Рехеши не помогут от коллизий

M>Скорее всего, ТСу нужна средняя сложность, вряд ли он делает систему жесткого реального времени.

Это да. В обычных прикладных задачах о коллизиях никто не задумывается, нет смысла.

Здравствуйте, T4r4sB, Вы писали:

M>>А резервирование/рехеширование можно делать по мере необходимости при вставке, или настроить max_load_factor, чтобы рехеши пореже происходили

TB>Рехеши не помогут от коллизий

При плохой хэш функции оно конечно может выродится в O(N), но на практике скорее будет O(1)/O(2)/O(3) или около того


M>>Скорее всего, ТСу нужна средняя сложность, вряд ли он делает систему жесткого реального времени.

TB>Это да. В обычных прикладных задачах о коллизиях никто не задумывается, нет смысла.

Стандартного std::hash обычно хватает, чтобы коллизий было приемлемое количество

Здравствуйте, Hоmunculus, Вы писали:


Можно попробовать как-то так. Массив узлов + массив указателей.

struct Node {
    std::vector<size_t> children;
    // ... другие данные узла
};

class Tree {
private:
    std::vector<Node> nodes;           // Все узлы хранятся здесь
    std::vector<size_t> free_ids;      // Список свободных ID
    size_t next_id = 0;
    
public:
    // Создание узла возвращает ID
    size_t createNode() {
        size_t id;
        if (!free_ids.empty()) {
            id = free_ids.back();
            free_ids.pop_back();
        } else {
            id = next_id++;
            if (id >= nodes.size()) {
                nodes.resize(id + 1);
            }
        }
        return id;
    }
    
    // Доступ за O(1)
    Node& getNode(size_t id) {
        return nodes[id];
    }
    
    void deleteNode(size_t id) {
        // Очищаем узел
        nodes[id].children.clear();
        // Добавляем ID в список свободных
        free_ids.push_back(id);
    }

Здравствуйте, Marty, Вы писали:

M>Оптимальный max_load_factor зависит от использования:
M>...
M>Для экономии памяти: 1.0-1.5
M>Для минимизации рехеширования: 2.0-3.0

А вот тут я чёт не понял
Если мы экономим память, то адресация должна быть открытая, никаких нахрен связных списков, а тогда заполнение в принципе не может достигать 1.0

Здравствуйте, T4r4sB, Вы писали:

TB>А вот тут я чёт не понял
TB>Если мы экономим память, то адресация должна быть открытая, никаких нахрен связных списков, а тогда заполнение в принципе не может достигать 1.0

А вот тут я тебя не понял. Я не спец по устройству std::unordered_map, но, как я понимаю, чем меньше корзин, тем меньше требуется памяти, т.е., количество корзин влияет на размер занимаемой памяти больше, чем размер самих корзин.

Здравствуйте, Marty, Вы писали:

M>Здравствуйте, T4r4sB, Вы писали:

TB>>А вот тут я чёт не понял
TB>>Если мы экономим память, то адресация должна быть открытая, никаких нахрен связных списков, а тогда заполнение в принципе не может достигать 1.0

M>А вот тут я тебя не понял. Я не спец по устройству std::unordered_map, но, как я понимаю, чем меньше корзин, тем меньше требуется памяти, т.е., количество корзин влияет на размер занимаемой памяти больше, чем размер самих корзин.



Тут я вижу 2 случая
Элементы мапы имеют небольшой размер ну там это поды до 50 байт каждый
Тогда накладные расходы на хранение корзин, разбросанных по куче, настолько велики, что нет смысла говорить об экономии памяти, и открытая адресация с заполнением 90% выиграет по памяти
Если элементы мапы жирные то уже пофиг сколько корзин.
А еще в стдшной мапе все элементы живут в одном односвязном списке, а для корзин просто массив итераторов на начало блока с нужным хешем, то есть увеличивая процент заполнения ты просто эеономишь на длине этого массива указателей

Здравствуйте, T4r4sB, Вы писали:

TB>Тут я вижу 2 случая
TB>Элементы мапы имеют небольшой размер ну там это поды до 50 байт каждый
TB>Тогда накладные расходы на хранение корзин, разбросанных по куче, настолько велики, что нет смысла говорить об экономии памяти, и открытая адресация с заполнением 90% выиграет по памяти
TB>Если элементы мапы жирные то уже пофиг сколько корзин.
TB>А еще в стдшной мапе все элементы живут в одном односвязном списке, а для корзин просто массив итераторов на начало блока с нужным хешем, то есть увеличивая процент заполнения ты просто эеономишь на длине этого массива указателей

Я не очень понял, что такое "открытая адресация"?

Здравствуйте, Marty, Вы писали:

M>Здравствуйте, Hоmunculus, Вы писали:

H>>У меня есть дерево. То есть нулевой узел с дочерними узлами и каждый дочерний содержит свои дочерние и так далее
H>>При создании ноды пользователю отдается unsigned int ID. И вот по этому ID нужен доступ за константное время. Идеально было бы как-то отразить дерево в вектор и чтоб ID был номером элемента в векторе. Но как-то криво выходит. Две структуры для одного и того же. Криво.
H>>Еще вариант, что ID — это собственно сам указатель, но не нравится он мне
H>>Какие есть варианты?

M>std::unordered_map?

Без примерного понимания размера, реальных тестов и того, как мапа создаётся — не всегда. Во многих случаях, особенно на небольших наборах данных map / flat_map будет (внезапно) быстрее из-за особенностей работы кэша, даже при теоретической логарифмической сложности. Особенно на всяких embedded где нет L3 кэша.

Здравствуйте, SaZ, Вы писали:

M>>std::unordered_map?

SaZ>Без примерного понимания размера, реальных тестов и того, как мапа создаётся — не всегда. Во многих случаях, особенно на небольших наборах данных map / flat_map будет (внезапно) быстрее из-за особенностей работы кэша, даже при теоретической логарифмической сложности. Особенно на всяких embedded где нет L3 кэша.

Я в курсе, что иногда тупой перебор может работать быстрее. Но в вопросе ТС не было задано никаких ограничений.

ЗЫ А в эмбеде обычно нет вообще никакого кеша.

Здравствуйте, Hоmunculus, Вы писали:

H>У меня есть дерево. То есть нулевой узел с дочерними узлами и каждый дочерний содержит свои дочерние и так далее
H>При создании ноды пользователю отдается unsigned int ID. И вот по этому ID нужен доступ за константное время. Идеально было бы как-то отразить дерево в вектор и чтоб ID был номером элемента в векторе. Но как-то криво выходит. Две структуры для одного и того же. Криво.
H>Еще вариант, что ID — это собственно сам указатель, но не нравится он мне
H>Какие есть варианты?

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

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

Или же ты спрашиваешь, как организовать быстрый поиск по unsigned int?

Здравствуйте, Marty, Вы писали:

M>Я не очень понял, что такое "открытая адресация"?

https://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0#%D0%9E%D1%82%D0%BA%D1%80%D1%8B%D1%82%D0%B0%D1%8F_%D0%B0%D0%B4%D1%80%D0%B5%D1%81%D0%B0%D1%86%D0%B8%D1%8F

Здравствуйте, Marty, Вы писали:

M>Я не очень понял, что такое "открытая адресация"?

https://learnc.info/adt/hashmap_open_addressing.html

Здравствуйте, Pzz, Вы писали:

У меня есть просто дерево. Без всяких ключей. То есть просто корневая нода, у нее дети и так рекурсивно. Ноды создает корень в любом случае, но при создании ноды указывается id родителя ноды. И создание ноды возвращает этот самый id. Вот по этому id и нужен О(1) доступ. Все делается через корень.

Здравствуйте, Hоmunculus, Вы писали:

H>Здравствуйте, Pzz, Вы писали:

H>У меня есть просто дерево. Без всяких ключей. То есть просто корневая нода, у нее дети и так рекурсивно. Ноды создает корень в любом случае, но при создании ноды указывается id родителя ноды.

Почему ид а не указатель?

Здравствуйте, T4r4sB, Вы писали:

TB>Почему ид а не указатель?

Потому что внутри нод есть некие пути к неким параметрам внутри других нод. И эти пути задаются именно через последовательность id-шников и так и сохраняются в файлы и загружаются из файлов. Сохранять в файл значение указателя, сам понимаешь, такое себе

Здравствуйте, Hоmunculus, Вы писали:

H>Потому что внутри нод есть некие пути к неким параметрам внутри других нод. И эти пути задаются именно через последовательность id-шников

Не помню такой способ хранению путей, кроме как префиксные деревья. А эта последовательность — это именно последовательность вложенных нод? Тогда достаточно LRLRLRRRRLLRLR, если дерево бинарное ну или другого компактного способа, если хранить только внутренний индекс потомка

H>Сохранять в файл значение указателя, сам понимаешь, такое себе

На самом деле так тоже можно, но для этого тебе придётся решить задачу эквивалентную дефрагментации

Здравствуйте, Hоmunculus, Вы писали:

H>У меня есть просто дерево. Без всяких ключей. То есть просто корневая нода, у нее дети и так рекурсивно. Ноды создает корень в любом случае, но при создании ноды указывается id родителя ноды. И создание ноды возвращает этот самый id. Вот по этому id и нужен О(1) доступ. Все делается через корень.

OK. Допустим, у тебя есть O(1) по этому самому ID. Зачем тебе еще и дерево? Вернее, если за какой-то надобностью ноды у тебя логически объединены в дерево, устроит ли тебя, что ссылаться друг на друга они будут не по прямому указателю, а по ID?

Здравствуйте, Pzz, Вы писали:

Да, id в рамках сессии однозначно идентифицирует ноды. И они активно друг на друга ссылаются именно по id. И эти же id сериализуются и отдаются наружу пользователю.

Здравствуйте, Hоmunculus, Вы писали:

H>Да, id в рамках сессии однозначно идентифицирует ноды. И они активно друг на друга ссылаются именно по id. И эти же id сериализуются и отдаются наружу пользователю.

Еще два вопроса:
1) ID выделяются последовательно?
2) Надо ли их удалять?

Здравствуйте, Pzz, Вы писали:

Pzz>Еще два вопроса:
Pzz>1) ID выделяются последовательно?

Неважно. Наверное, при создании — удобно последовательно , но если в предшествующих номерах после удаленных остались дыры, то можно их занимать. То есть родитель может быть с Id=9, а внутри него ребенок может быть вполне с id = 4. Это неважно. Главное — уникальность и однозначность в поиске

Pzz>2) Надо ли их удалять?

Да. Причем с удалением всех детей ноды, разумеется

Здравствуйте, Marty, Вы писали:

M>...

M>Я в курсе, что иногда тупой перебор может работать быстрее. Но в вопросе ТС не было задано никаких ограничений.
Да, это скорее мой комментарий для ТС.

M>ЗЫ А в эмбеде обычно нет вообще никакого кеша.
Ну смотря что вы понимаете под эмбеддед. Для меня всякие малинки, броадкомы, телеприставки и т.п. — это эмбеддед, хотя может я слишком широко беру.

Здравствуйте, Hоmunculus, Вы писали:

Pzz>>Еще два вопроса:
Pzz>>1) ID выделяются последовательно?

H>Неважно. Наверное, при создании — удобно последовательно , но если в предшествующих номерах после удаленных остались дыры, то можно их занимать. То есть родитель может быть с Id=9, а внутри него ребенок может быть вполне с id = 4. Это неважно. Главное — уникальность и однозначность в поиске

Ну, как вариант, можно хранить массив (вектор), в котором ID — это индекс, а значение — указатель на ноду. Расширять его по мере надобности и переиспользовать дырки по мере возможности.

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

В принципе, эта структура напоминает FAT из MS-DOS, примерно так организованы списки свободных/занятых блоков.

Потери твои — если ты навыделял много нор, а потом много освободил, то их позиции в индексном массиве остаются в оперативной памяти до тех пор, пока опять не понадобятся. Но я б на эту тему особо не переживал. Всё равно сишное освобождение памяти (free/delete) довольно маловероятно, что вернёт память системе, скорее, оставит её, как свободную область в куче.

Pzz>>2) Надо ли их удалять?

H>Да. Причем с удалением всех детей ноды, разумеется

Еще один вариант — использовать структуру, напоминающую page directory у x86. Кажется, это называется radix tree. Такая штука работает хорошо, когда у тебя ID в принципе ложатся кучно, но возможно, что с дырками между кучками. И плохо работает, когда они случайно распределены.

Здравствуйте, Pzz, Вы писали:

Ну BlackEric выше по сути и привел это решение

Здравствуйте, Hоmunculus, Вы писали:

H>У меня есть дерево. То есть нулевой узел с дочерними узлами и каждый дочерний содержит свои дочерние и так далее
H>При создании ноды пользователю отдается unsigned int ID. И вот по этому ID нужен доступ за константное время. Идеально было бы как-то отразить дерево в вектор и чтоб ID был номером элемента в векторе. Но как-то криво выходит. Две структуры для одного и того же. Криво.

Ничего кривого я тут не вижу.

1. Есть некая структура из элементов (пусть дерево, а впрочем, любая) организованная на каком-то принципе, не привязанном к ID.

2. Есть необходимость доступа по ID, причем O(1)

3. Делаем массив, где ID — индекс, а элемент — указатель на элемент из (1). При удалении элемента заносим туда null. Вот и все.

Вот пример аналогичного класса, внутри которого 2 структуры

https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html

Внутри hashmap для доступа по ключу и linkedlist — список по порядку добавления.

This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).

Не совсем то, конечно, но очень похоже. Вместо "insrtion order" тебе нужен "ID order", ну а коль нужен O(1) — массив, а не список.

Здравствуйте, Pavel Dvorkin, Вы писали:

Криво то, что и удаление и создание нод идет по сути через два контейнера. Нельзя например просто грохнуть ноду и он автоматически грохнет детей. Надо id и самой ноды и ее детей рекурсивно вычищать из другого контейнера.

Здравствуйте, Hоmunculus, Вы писали:

H>Криво то, что и удаление и создание нод идет по сути через два контейнера. Нельзя например просто грохнуть ноду и он автоматически грохнет детей. Надо id и самой ноды и ее детей рекурсивно вычищать из другого контейнера.

Если метод удаления ноды (самой) вызывает себя для детей, то достаточно при удалении ноды ставить в массив null. При удалении детей он сделает то же самое для детей

Примерно так.

void deleteNode (Node node) {
foreach(child in node) {
deleteNode(child);
}
array[node.id] = null;
// удаление самой ноды
}

Здравствуйте, Hоmunculus, Вы писали:

H>Ну BlackEric выше по сути и привел это решение

Угу. А я объяснил, откуда оно берётся.

Здравствуйте, SaZ, Вы писали:

M>>ЗЫ А в эмбеде обычно нет вообще никакого кеша.
SaZ>Ну смотря что вы понимаете под эмбеддед. Для меня всякие малинки, броадкомы, телеприставки и т.п. — это эмбеддед, хотя может я слишком широко беру.

Ну это такой себе эмбед, там обычно вполне полноценная ОС. Обычно же эмбед — это микроконтроллер, ОС там нет или что-то типа FreeRTOS, и тайминги там критические

Здравствуйте, T4r4sB, Вы писали:

M>>А резервирование/рехеширование можно делать по мере необходимости при вставке, или настроить max_load_factor, чтобы рехеши пореже происходили
TB>Рехеши не помогут от коллизий

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

Здравствуйте, Hоmunculus, Вы писали:

H>У меня есть дерево. То есть нулевой узел с дочерними узлами и каждый дочерний содержит свои дочерние и так далее
H>При создании ноды пользователю отдается unsigned int ID. И вот по этому ID нужен доступ за константное время. Идеально было бы как-то отразить дерево в вектор и чтоб ID был номером элемента в векторе. Но как-то криво выходит. Две структуры для одного и того же. Криво.
H>Еще вариант, что ID — это собственно сам указатель, но не нравится он мне
H>Какие есть варианты?

Проще пареной репы.

using TreeNode = int;
static constexpr TreeNode none = -1;

struct TreeItem
{
  TreeNode parent;
  TreeNode next;
  TreeNode child;
};

std::vector<TreeItem> treeItems;
TreeNode deletedItems = none;

Вместо указателей — индексы. Индексы знаковые, невалидное значение — отрицательное. Помимо none можно использовать спецзначения в отрицательном диапазоне.
При удалении элементов ссылка устанавливается в none. Удалённые элементы остаются в массиве, но включаются в список deletedItems, для переиспользования.

Работает с сотнями МБ данных.