Контейнер больших целочисленных множеств

чота у буста похожее видел. Вспомнить название не могу.

а что сортированный вектор не? хотя вставка удаление там да ...

чота у буста похожее видел. Вспомнить название не могу.

ничего подходящего не нашел - там всё более универсальное. хотя, может, плохо смотрел.

а что сортированный вектор не? хотя вставка удаление там да ...

ну да, и вставка/удаление, и память тоже хотелось бы, по возможности, меньше использовать. просто как-то глупо выглядит хранение последовательностей вроде 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, когда можно хранить только [1, 10] без ущерба для дела.

BVH-tree

Возможно. Вопрос - где взять реализацию, причем, качественную?

Поправка: BVH-tree — это частный случай spatial partitioning trees. Я бы копал в эту сторону. Структур подобного класса много, на самом деле. Возможно вам больше подойдёт segment tree или что-то ещё.

Готовых реализаций BVH-деревьев много, но я пользовался самописной. Пишется несложно.

А какая нужна итерация? По всему множеству? Нужны диапазонные выборки?

std::set не устраивает?

Можно посмотреть на Judy Arrays или другие вариации trie, типа https://github.com/armon/libart

trie

Наркоман чтоль?

BVH или октодерево можно адаптировать под задачу.

Готового не знаю. В голову приходит вариант реализации на основе дерева пар (интервалов). Вставка: ищем пару, соседнюю с данным. Если такая пара одна: расширяем интевал, если две — склеиваем интевалы, ни одной — добавляем новую точечную пару в дерево. Удаление элемента аналогично, может привести: к сужению интервала, к разбиению интервала на два, к удалению точечного интервала.

А какая нужна итерация? По всему множеству? Нужны диапазонные выборки?

Да на самом деле нужно уметь быстро доставать первые N элементов из множества (очень желательно чтобы оно было упорядоченным).

std::set не устраивает?

Я сомневаюсь, что оно вообще влезет в те 2-3-4 гига, которые доступны для 32-битного процесса. Да и для 64-битного памяти запросто может не хватить - там, по-моему, нужно раз в 10 больше памяти, чем просто размер элемента * число элементов. Это уже не говоря о логарифмической сложности вставки/удаления.

Нет, он не наркоман. Я бы тоже сперва попробовал Judy Arrays.

числа лежат в диапазоне от 0 до, собственно, ~100 000 000

большинство элементов лежат в непрерывных интервалах

Кстати, можно же и правда сыграть на этом. Хранить отсортированные пары - начало и конец диапазона (сортировать по началу). Или вообще держать диапазон в uint64_t.

Впрочем, не буду настаивать. Может действительно лучше BVH или октодерево (на одномерных интервалах, да)

ничего подходящего не нашел - там всё более универсальное.

interval_set?

да блин у Седжвика в самом начале.

Да, с виду оно. Но зачем же они засунули это в отдельную библиотеку??

Я сомневаюсь, что оно вообще влезет в те 2-3-4 гига, которые доступны для 32-битного процесса. Да и для 64-битного памяти запросто может не хватить - там, по-моему, нужно раз в 10 больше памяти, чем просто размер элемента * число элементов. Это уже не говоря о логарифмической сложности вставки/удаления.

Всё это справедливо для любого дерева. set внутри - тоже дерево. И не в 10 (делать такие заявления не указывая размера элемента и архитектуру вообще безграмотно). Элемент дерева - это данные + 3 указателя, учитывая что нужно хранить 2 инта, на 32 битах это будет всего 2.5x, на 64 битах - 4x.

set внутри - тоже дерево

Да и простой массив — тоже вполне себе дерево, ибо оператика на железном уровне имеет иерархическую структуру. ^___~

используй unordered_set с кастомным аллокатором, который будет сразу много памяти выделять

Это, типа, ты мне тут решил устроить лекцию на тему как устроены AVL-деревья и красно-черные деревья? Спасибо, такие лекции я уже слушал и в более компетентном исполнении)

Всё это справедливо для любого дерева. set внутри - тоже дерево.

4.2. И даже std::set, вовсе не обязан быть деревом внутри.

Это, типа, ты мне тут решил устроить лекцию на тему как устроены AVL-деревья и красно-черные деревья? Спасибо, такие лекции я уже слушал и в более компетентном исполнении)

Типа да, решил устроить лекцию, потому что если бы знал как устроены деревья про 10x чушь бы не городил.

4.2. И даже std::set, вовсе не обязан быть деревом внутри

Разумеется не обязан, но во всех вменяемых реализациях является. С тех пор как ты открыл рот о потреблении памяти, мы говорим о конкретных реализациях.

Может смотреть в сторону подобного:

struct V
{
   unsigned from;
   unsigned to;
};

std::vector<V> container;

Типа да, решил устроить лекцию, потому что если бы знал как устроены деревья про 10x чушь бы не городил.

Чувак, да ты сам плохо представляешь как чего устроено и как работает. Битики решил посчитать. Так никто не делает. Максимум - берут и проверяют. Ты про выравнивание чего-нибудь слышал? Или про фрагментацию? Поэтому давай ты не будешь тут флудить. Я написал «раз в 10», а не «в 10 раз» и этого достаточно для иллюстрации проблемы.

Да тут уже ответили: Контейнер больших целочисленных множеств (комментарий) Осталось только проверить. Но вообще, я бы и сам что-то подобное написал скорее всего, если бы его не было.

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

Это относится только к тебе. При этом ты имеешь наглость выпендриваться.

Битики решил посчитать.

Посчитать решил ты когда сказал про 10x. Я показал что это не так.

Максимум - берут и проверяют.

Проверяют те кто не знают как оно работает. Да, можешь проверить.

Ты про выравнивание чего-нибудь слышал?

Слышал, а ты? 3 указателя + 2 инта будут выровнены без дырок на 32 и 64 битах. Тебе есть что добавить?

Или про фрагментацию?

Внимательно слушаю.

Поэтому давай ты не будешь тут флудить. Я написал «раз в 10», а не «в 10 раз» и этого достаточно для иллюстрации проблемы.

Для иллюстрации твоей безграмотности этого вполне достаточно.

Да тут уже ответили: Контейнер больших целочисленных множеств (комментарий) Осталось только проверить

Ты будешь шокирован, но внутри там тот же set.

Посчитать решил ты когда сказал про 10x. Я показал что это не так.

Ещё раз тебе повторяю: я сказал «раз в 10», а не в 10 раз. А может быть и больше 10 раз, как описано тут. Поэтому идешь в игнор как школота.

Я не буду шокирован потому что сам это скорее всего с помощью std::set и реализовал бы (как минимум в первом варианте).

Ещё раз тебе повторяю: я сказал «раз в 10», а не в 10 раз

Оправдываться и юлить поздно, ты уже опозорился.

100 000 000 это всего примерно 12 мегабайт, если в битовый вектор запихнуть, ерунда, нет ? И да, у буста раньше был, а сейчас в стандартной библиотеке, std::bitset . Ничего вроде изобретать не надо.

100 000 000 это всего примерно 12 мегабайт, если в битовый вектор запихнуть, ерунда, нет ?

С битовым вектором и одного элемента из этого множества будет достаточно чтоб эти 12+ мегабайт занять (это если реализация будет действительно биты использовать). А потом чтобы его там найти ещё потребуется по всему вектору пройтись.

чтобы его там найти ещё потребуется по всему вектору пройтись

Не нужно проходиться. Смотришь, если бит в проверяемой позиции установлен, значит число принадлежит множеству.

Пару лет назад на лоре уже была похожая тема, я на коленке промерял скорости нескольких способов (даже довольно экзотических). Judy arrays из традиционных способов оказались самыми быстрыми, быстрее чем битовые карты

Не нужно проходиться. Смотришь, если бит в проверяемой позиции установлен, значит число принадлежит множеству.

Я ж говорю не проверить позицию, а НАЙТИ.

Ну так фишка в том, что количество занимаемой памяти не зависит от количества элементов и вполне приемлемое. То есть 12 МБ будет занято, хоть в этом множестве 1 элемент, хоть миллион. Это не так уж и плохо.

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

посмотри boost::icl
http://www.boost.org/doc/libs/1_58_0/libs/icl/doc/html/index.html
может, подойдёт.

Да, да, уже подсказали выше. На днях попробую прикрутить.

Если число непрерывных интервалов не шибко велико (меньше, чем 1e8/32 для x86_64 или 1e8/20 для x86), то просто берешь красно-черное дерево, которое тебе больше нравится, в узлах которого хранятся интервалы, добавляешь функцию поиска точки по этому дереву, на основе поиска точки пишешь функцию добавления/удаления интервала; если скорость итерации очень критична, сдабриваешь сверху интрузивным списком, и вуаля!

Если взять sys/tree.h и sys/queue.h, то на сишке описанное реализуется примерно за час. С бустом просношаешься куда дольше.

С бустом просношаешься куда дольше.

В каком смысле? #include <boost/icl/interval_set.hpp> буду 2 часа писать?

boost::interval предлагает подобную логику.

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

#include <boost/icl/interval_set.hpp> буду 2 часа писать?

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

И не надо заливать про параметр Alloc шаблона. Все мы знаем, что крестовые аллокаторы, растущие из STL, являют собой бескрайне убогое и практически неприменимое говно.

Ты, случайно, не царь?)

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

сколько истребителейинтервалов?

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

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

в сети полно уже готовых аллокаторов на все случаи жизни

А в сети уже есть куча костылей, чтобы, скажем, сравнить/присвоить string/map/vector, находящиеся в разных аллокаторах?

Все проблемы растут из двух абсолютно идиотских решений:

• невозможно передать в контейнер свой инстанс аллокатора
• аллокатор является параметром шаблона, что автоматически делает объекты, выделенные внутри разных аллокаторов несовместимыми без специальных и весьма утомительных свистоплясок

Хотя STL состоит из дебильных решений процентов на 95, а единственный вменяемый концепт в нем - итераторы.

Надеюсь, порядка нескольких сотен, но точно пока сказать нельзя. В худшем случае ~50 000 000)

просто если их мало(ну хотя бы там 10^5), то по крайней мере можно написать самому маленькую структурку, внутри которой обычный map<int,int>. если же нет никаких правил по поводу того, как расположены числа, то самые лучшие варианты — unordered_set и тот самый vector<bool>.

upd: чего-то я забыл про interval_set из буста. если интервалов хотя бы раз в 10 меньше, чем чисел, то польза уже будет ощутима.

я совсем не молодой человек. и опыта у меня более чем достаточно. и по работе с пулами в том числе. ваше «невозможно» - всего лишь следствие незнания. вы бы лучше не парили людям мозг, а погуглили на тему cpp custom allocator. и будет вам счастье.