LINUX.ORG.RU

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

 


0

2

Имеется задача в которой приходится работать с потенциально очень большими (порядка сотен миллионов элементов) множествами целых чисел. При этом сами эти числа лежат в диапазоне от 0 до, собственно, ~100 000 000. Ещё одна особенность в том, что большинство элементов лежат в непрерывных интервалах [x; x + L] (то есть само множество - это множество таких вот непересекающихся интервалов). Основные операции: добавить элемент в множество, удалить элемент из множества, итерация. std::vector<bool> плохо подходит во-первых потому что итерация медленная, во-вторых, как кажется, с памятью тоже можно было бы работать гораздо эффективнее. Есть ли готовые реализации таких множеств, которыми можно было бы воспользоваться?

★★★★★

Последнее исправление: asaw (всего исправлений: 2)

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

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

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

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

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

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

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

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

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

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

fmdw
()
Последнее исправление: fmdw (всего исправлений: 3)

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

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

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

Deleted
()

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

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

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

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

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

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

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

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

mix_mix ★★★★★
()

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

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

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

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

Deleted
()

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

qulinxao ★★☆
()
Ответ на: комментарий от i-rinat

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

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

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

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

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

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

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

fmdw
()

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

asaw ★★★★★
() автор топика

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

anonymous
()
Ответ на: комментарий от f1u77y

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

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

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

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

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

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

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

Iron_Bug ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.