?

Log in

No account? Create an account

Рабочее - Общество дровосеков Бердичева по изучению Мишны

Jul. 27th, 2012

05:13 pm - Рабочее

Previous Entry Share Next Entry

[C++ STL, так штаааа....]

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

Tags:

Comments:

[User Picture]
From:ygam
Date:July 28th, 2012 12:51 am (UTC)
(Link)
Я забыл: set - это двоичное дерево, а хэш-таблица - это hash_set? Я на сиплюсплюсе писал в последний раз в 2007 году.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:July 28th, 2012 01:09 am (UTC)
(Link)
Да, set - это дерево (red-black). А в rope при вставлении в нее по одному элементу получается чуть дороже двоичного дерева, и в реализации GCC все узлы refcounted, поэтому "копирование" бесплатное, а добавление элемента логарифмически дешевое по памяти.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:July 30th, 2012 09:19 pm (UTC)
(Link)
Из-за refcounting в rope можно переиспользовать подстроки, так что структура в общем случае - не дерево, а DAG, и память, необходимую для строки, можно уменьшить до значения, пропорционального длине этой строки в сжатом каким-нибудь Лемпель-Зивом виде.
(Reply) (Parent) (Thread)
[User Picture]
From:yigal_s
Date:July 28th, 2012 01:35 am (UTC)
(Link)
хммм... милая штучка.

и что, вы на этой структуре бинарный поиск сделали, я верно понимаю???
(Reply) (Thread)
[User Picture]
From:spamsink
Date:July 28th, 2012 01:48 am (UTC)
(Link)
Ну да. Там пришлось прибегнуть к трюку с переходом от дешевых константных итераторов к дорогим неконстантным после собственно поиска (хотя я не уверен, что сделал это оптимальным образом, а в остальном всё прозрачно).
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());


(Reply) (Parent) (Thread)
[User Picture]
From:yigal_s
Date:July 28th, 2012 02:31 am (UTC)
(Link)
я верно понимаю, что сложность lower_bound у вас будет (log n)^2

???
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:July 28th, 2012 02:38 am (UTC)
(Link)
Похоже на то, но это не беда.
(Reply) (Parent) (Thread)
[User Picture]
From:yigal_s
Date:July 28th, 2012 03:11 am (UTC)
(Link)
так ведь тогда и получение неконстантного итератора всего-то дает log n * (log n + 1) в совокупности, что не так чтоб сильно хуже
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:July 28th, 2012 05:34 am (UTC)
(Link)
Это да, просто некрасиво выглядит. Собственно, разница между константным и неконстантным итератором в том, что последний хранит указатель на всю веревку, а не только на корень ее содержимого, что делает его больше по размеру (это пустяки), а также приводит к локам при изменении счетчика референсов при создании/уничтожении (это в теории не пустяки, а на однотредной программе, как у меня - пара команд разницы). Так что если по статистике большинство попыток вставки приводят к реальным вставкам, проще сразу делать неконстантный итератор и давать его поиску.
(Reply) (Parent) (Thread)
[User Picture]
From:fatoff
Date:July 28th, 2012 02:47 am (UTC)
(Link)
Да, как-то раз для map с многими тысячами строк был придуман аллокатор, чтобы писать всё в contiguous memory. Пусть даже на поверхности нерационально, резервировалась максимальная длина для каждой выделяемой строчки, оно получилось менее сосущее и по памяти, и по скорости, чем map с аллокатором по умолчанию.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:July 28th, 2012 02:51 am (UTC)
(Link)
Это да, без собственного аллокатора никак не можно.
(Reply) (Parent) (Thread)
[User Picture]
From:fatoff
Date:July 28th, 2012 03:05 am (UTC)
(Link)
Может... вместо верёвкового решения пойдёт? Вопрос, как правильно упаковать, и как поддерживать достаточно большую непрерывную область памяти. Ну, memory-mapped file поддерживается и в *nix.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:July 28th, 2012 05:35 am (UTC)
(Link)
Там вся соль в структуре, позволяющей переиспользовать общие части - это дает выигрыш на два десятичных порядка по сравнению с сетами, а простая упаковка в непрерывные массивы - примерно на порядок.
(Reply) (Parent) (Thread)
[User Picture]
From:fatoff
Date:July 28th, 2012 05:51 am (UTC)
(Link)
Понятно, какие-то невероятно длинные строки, хранимые в set.

Edited at 2012-07-28 05:55 am (UTC)
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:July 28th, 2012 06:02 am (UTC)
(Link)
Там хранятся просто числа, но этих множеств очень много и они очень похожи друг на друга.
(Reply) (Parent) (Thread)
[User Picture]
From:sasha_gil
Date:July 28th, 2012 09:27 pm (UTC)
(Link)
Ой, а я почему-то под словами "C++ STL, так штаааа...." вижу ссылку http://spamsink.livejournal.com/444210.html# - то есть ничего не вижу - получается, я уже пропустил интересное, или у меня браузер неправильный?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:July 29th, 2012 04:09 am (UTC)
(Link)
Там я использовал не кат, а спойлер (тег lj-spoiler), работающий через джаваскрипт. На него надо просто кликать.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:July 30th, 2012 06:08 pm (UTC)
(Link)
Я так понимаю, что главная фича множества - возможность быстро проверить, является ли некое значение элементом множества, при этом теряется?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:July 30th, 2012 06:16 pm (UTC)
(Link)
Она становится в теории несколько медленнее (лог-квадрат), но выигрыш по памяти - именно при описанной конфигурации слабо отличающихся друг от друга множеств - настолько существенный, что в результате получается гораздо быстрее.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:July 30th, 2012 06:33 pm (UTC)
(Link)
Ну и плюс его надо написать, и плюс для этого должны быть слабоменяющиеся множества (а не то их формирование будет дорогим).
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:July 30th, 2012 06:42 pm (UTC)
(Link)
Кого его? Множества четко строятся одно из другого - это, считай, необходимое условие.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:July 30th, 2012 07:53 pm (UTC)
(Link)
Двоичный поиск? Хотя вроде там был какой-то готовый STLный.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:July 30th, 2012 06:34 pm (UTC)
(Link)
Кстати, а последовательных диапазонов в данных нету? А то еще и на них можно сэкономить.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:July 30th, 2012 06:45 pm (UTC)
(Link)
Бывают, но хотелось прибегнуть к готовому решению, а не изобретать доморощенную структуру данных.
(Reply) (Parent) (Thread)