std::set<int>, когда их много больших (тысячи элементов) похожих друг на друга и сделанных друг из друга, сосёт у __gnu_cxx::rope<int> большое время (100x) и большую память (>100x). Очень рекомендую.
Да, set - это дерево (red-black). А в rope при вставлении в нее по одному элементу получается чуть дороже двоичного дерева, и в реализации GCC все узлы refcounted, поэтому "копирование" бесплатное, а добавление элемента логарифмически дешевое по памяти.
Из-за refcounting в rope можно переиспользовать подстроки, так что структура в общем случае - не дерево, а DAG, и память, необходимую для строки, можно уменьшить до значения, пропорционального длине этой строки в сжатом каким-нибудь Лемпель-Зивом виде.
Ну да. Там пришлось прибегнуть к трюку с переходом от дешевых константных итераторов к дорогим неконстантным после собственно поиска (хотя я не уверен, что сделал это оптимальным образом, а в остальном всё прозрачно).
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());
Это да, просто некрасиво выглядит. Собственно, разница между константным и неконстантным итератором в том, что последний хранит указатель на всю веревку, а не только на корень ее содержимого, что делает его больше по размеру (это пустяки), а также приводит к локам при изменении счетчика референсов при создании/уничтожении (это в теории не пустяки, а на однотредной программе, как у меня - пара команд разницы). Так что если по статистике большинство попыток вставки приводят к реальным вставкам, проще сразу делать неконстантный итератор и давать его поиску.
Да, как-то раз для map с многими тысячами строк был придуман аллокатор, чтобы писать всё в contiguous memory. Пусть даже на поверхности нерационально, резервировалась максимальная длина для каждой выделяемой строчки, оно получилось менее сосущее и по памяти, и по скорости, чем map с аллокатором по умолчанию.
Может... вместо верёвкового решения пойдёт? Вопрос, как правильно упаковать, и как поддерживать достаточно большую непрерывную область памяти. Ну, memory-mapped file поддерживается и в *nix.
Там вся соль в структуре, позволяющей переиспользовать общие части - это дает выигрыш на два десятичных порядка по сравнению с сетами, а простая упаковка в непрерывные массивы - примерно на порядок.
Ой, а я почему-то под словами "C++ STL, так штаааа...." вижу ссылку http://spamsink.livejournal.com/444210.html# - то есть ничего не вижу - получается, я уже пропустил интересное, или у меня браузер неправильный?
Она становится в теории несколько медленнее (лог-квадрат), но выигрыш по памяти - именно при описанной конфигурации слабо отличающихся друг от друга множеств - настолько существенный, что в результате получается гораздо быстрее.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
winterfish
no subject
Date: 2012-07-28 12:51 am (UTC)no subject
Date: 2012-07-28 01:09 am (UTC)no subject
Date: 2012-07-30 09:19 pm (UTC)no subject
Date: 2012-07-28 01:35 am (UTC)и что, вы на этой структуре бинарный поиск сделали, я верно понимаю???
no subject
Date: 2012-07-28 01:48 am (UTC)no subject
Date: 2012-07-28 02:31 am (UTC)???
no subject
Date: 2012-07-28 02:38 am (UTC)no subject
Date: 2012-07-28 03:11 am (UTC)no subject
Date: 2012-07-28 05:34 am (UTC)no subject
Date: 2012-07-28 02:47 am (UTC)no subject
Date: 2012-07-28 02:51 am (UTC)no subject
Date: 2012-07-28 03:05 am (UTC)no subject
Date: 2012-07-28 05:35 am (UTC)no subject
Date: 2012-07-28 05:51 am (UTC)no subject
Date: 2012-07-28 06:02 am (UTC)no subject
Date: 2012-07-28 09:27 pm (UTC)no subject
Date: 2012-07-29 04:09 am (UTC)no subject
Date: 2012-07-30 06:08 pm (UTC)no subject
Date: 2012-07-30 06:16 pm (UTC)no subject
Date: 2012-07-30 06:33 pm (UTC)no subject
Date: 2012-07-30 06:42 pm (UTC)no subject
Date: 2012-07-30 07:53 pm (UTC)no subject
Date: 2012-07-30 06:34 pm (UTC)no subject
Date: 2012-07-30 06:45 pm (UTC)