Рабочее

[spamsink]

std::set<int>, когда их много больших (тысячи элементов) похожих друг на друга и сделанных друг из друга, сосёт у __gnu_cxx::rope<int> большое время (100x) и большую память (>100x). Очень рекомендую.

Comments

[ygam.livejournal.com]

Я забыл: set - это двоичное дерево, а хэш-таблица - это hash_set? Я на сиплюсплюсе писал в последний раз в 2007 году.

[spamsink]

Да, set - это дерево (red-black). А в rope при вставлении в нее по одному элементу получается чуть дороже двоичного дерева, и в реализации GCC все узлы refcounted, поэтому "копирование" бесплатное, а добавление элемента логарифмически дешевое по памяти.

[yigal_s]

хммм... милая штучка.

и что, вы на этой структуре бинарный поиск сделали, я верно понимаю???

[spamsink]

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

rint::const_iterator cit = lower_bound(r.begin(), r.end(), rnd);
// Вот это место хотелось бы O(1), а не O(log n), как оно сейчас:
rint::iterator it = r.mutable_begin() + (cit - r.begin());

[yigal_s]

я верно понимаю, что сложность lower_bound у вас будет (log n)^2

???

[spamsink]

Похоже на то, но это не беда.

[fatoff.livejournal.com]

Да, как-то раз для map с многими тысячами строк был придуман аллокатор, чтобы писать всё в contiguous memory. Пусть даже на поверхности нерационально, резервировалась максимальная длина для каждой выделяемой строчки, оно получилось менее сосущее и по памяти, и по скорости, чем map с аллокатором по умолчанию.

[spamsink]

Это да, без собственного аллокатора никак не можно.

[fatoff.livejournal.com]

Может... вместо верёвкового решения пойдёт? Вопрос, как правильно упаковать, и как поддерживать достаточно большую непрерывную область памяти. Ну, memory-mapped file поддерживается и в *nix.

[yigal_s]

так ведь тогда и получение неконстантного итератора всего-то дает log n * (log n + 1) в совокупности, что не так чтоб сильно хуже

[spamsink]

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

[spamsink]

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

[fatoff.livejournal.com]

Понятно, какие-то невероятно длинные строки, хранимые в set.

[spamsink]

Там хранятся просто числа, но этих множеств очень много и они очень похожи друг на друга.

[sasha-gil.livejournal.com]

Ой, а я почему-то под словами "C++ STL, так штаааа...." вижу ссылку http://spamsink.livejournal.com/444210.html# - то есть ничего не вижу - получается, я уже пропустил интересное, или у меня браузер неправильный?

[spamsink]

Там я использовал не кат, а спойлер (тег lj-spoiler), работающий через джаваскрипт. На него надо просто кликать.

[sab123.livejournal.com]

Я так понимаю, что главная фича множества - возможность быстро проверить, является ли некое значение элементом множества, при этом теряется?

[spamsink]

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

[sab123.livejournal.com]

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

[sab123.livejournal.com]

Кстати, а последовательных диапазонов в данных нету? А то еще и на них можно сэкономить.

[spamsink]

Кого его? Множества четко строятся одно из другого - это, считай, необходимое условие.

[spamsink]

Бывают, но хотелось прибегнуть к готовому решению, а не изобретать доморощенную структуру данных.

[sab123.livejournal.com]

Двоичный поиск? Хотя вроде там был какой-то готовый STLный.

[spamsink]

Из-за refcounting в rope можно переиспользовать подстроки, так что структура в общем случае - не дерево, а DAG, и память, необходимую для строки, можно уменьшить до значения, пропорционального длине этой строки в сжатом каким-нибудь Лемпель-Зивом виде.