Есть пара вопросов о multimap:
1. Как можна при создании multimap, зарезервировать под него место, так что бы при вставке нового элемента не тратилось время на выделение памяти? Просто очень много вставок в процессе работы...
2. Можна ли в процессе работы менять ключ элемента? Если да, то как?
3. Как ускорить процесс удаления элементов, у меня в мультимапе куча стрингов и профайлер показывает что процесс удаления этих стрингов дольше выполняется чем сам процесс их обработки...
wrote:
> 1. Как можна при создании multimap, зарезервировать под него место, так что бы при вставке нового элемента не тратилось время на выделение памяти? Просто очень много вставок в процессе работы...
Использовать собственный allocator, который будет выделять память из превыделенного пула.
Альтернативный вариант — map_light. Использовать в качестве контейнера отсортированный vector, для поиска использовать equal_range, для вставки upper/lower_bound.
> 2. Можна ли в процессе работы менять ключ элемента? Если да, то как?
Можно, но не inplace. Удалить элемент, изменить ключ, снова вставить.
> 3. Как ускорить процесс удаления элементов, у меня в мультимапе куча стрингов и профайлер показывает что процесс удаления этих стрингов дольше выполняется чем сам процесс их обработки...
Здравствуйте, MaximE, Вы писали:
ME>wrote:
>> 1. Как можна при создании multimap, зарезервировать под него место, так что бы при вставке нового элемента не тратилось время на выделение памяти? Просто очень много вставок в процессе работы...
ME>Использовать собственный allocator, который будет выделять память из превыделенного пула.
Весело... Еще менеджер памяти самому писать
ME>Альтернативный вариант — map_light.
А где он этот map_light?
ME>Использовать в качестве контейнера отсортированный vector, для поиска использовать equal_range, для вставки upper/lower_bound.
А разве такой есть, что то не могу вспомнить...
>> 2. Можна ли в процессе работы менять ключ элемента? Если да, то как?
ME>Можно, но не inplace. Удалить элемент, изменить ключ, снова вставить.
Так и делаю по сути, но что мне это не нравится...
>> 3. Как ускорить процесс удаления элементов, у меня в мультимапе куча стрингов и профайлер показывает что процесс удаления этих стрингов дольше выполняется чем сам процесс их обработки...
ME>Тут варианты зависят от задачи.
Я и сам не могу понять, почему delete всех элементов так долго работает, помоему delete должна быть очень простой операцией...
Здравствуйте, Аноним, Вы писали:
ME>>Использовать собственный allocator, который будет выделять память из превыделенного пула.
А>Весело... Еще менеджер памяти самому писать
Любишь кататься...
Попробуй STLPort — у него достаточно продвинутые аллокаторы.
ME>>Использовать в качестве контейнера отсортированный vector, для поиска использовать equal_range, для вставки upper/lower_bound.
А>А разве такой есть, что то не могу вспомнить...
Обычный вектор превращается в сортированный простым мановением std::sort Впрочем, можно обратить свой взор на AssocVector из Loki.
ME>>Можно, но не inplace. Удалить элемент, изменить ключ, снова вставить. А>Так и делаю по сути, но что мне это не нравится...
А что делать? Такова суровая правда жизни...
А>Я и сам не могу понять, почему delete всех элементов так долго работает, помоему delete должна быть очень простой операцией...
К сожалению это не так.
Bell wrote:
> А>А разве такой есть, что то не могу вспомнить... > Обычный вектор превращается в сортированный простым мановением std::sort Впрочем, можно обратить свой взор на AssocVector из Loki.
Возможно, что сортировать вектор не очень удачное решение, по сравнению с использованием upper/lower_bound. После вставки sort будет перелопачивать весь массив, lower_bound же найдет тебе нужное место вставки бинарным поиском.
Хотя вполне может оказаться, что нужно вставить большое количество элементов до того момента как будет производиться поиск. В этом случае может оказаться эффективнее набить вектор, затем его отсортировать.
Хотя опять же, сложность lower_bound — гарантировано log2(n), быстрой сортировки std::sort — в среднем c * n * log2(n), в худшем — n ** 2...
Здравствуйте, MaximE, Вы писали:
ME>Bell wrote:
>> А>А разве такой есть, что то не могу вспомнить... >> Обычный вектор превращается в сортированный простым мановением std::sort Впрочем, можно обратить свой взор на AssocVector из Loki.
ME>Возможно, что сортировать вектор не очень удачное решение, по сравнению с использованием upper/lower_bound. После вставки sort будет перелопачивать весь массив, lower_bound же найдет тебе нужное место вставки бинарным поиском.
Да я не спорю — просто я упоманул про std::sort в овет на фразу "А разве такой есть"...
Здравствуйте, MaximE, Вы писали:
ME>Возможно, что сортировать вектор не очень удачное решение, по сравнению с использованием upper/lower_bound. После вставки sort будет перелопачивать весь массив, lower_bound же найдет тебе нужное место вставки бинарным поиском.
А потом придется использовать вставку в вектор со сложностью O(N)
ME>Хотя опять же, сложность lower_bound — гарантировано log2(n), быстрой сортировки std::sort — в среднем c * n * log2(n), в худшем — n ** 2...
Не lower_bound не катит ибо ты забыл еще и про вставку... А std::sort в томже STLPort реализован через IntroSort у которого нет проблем с худшим случаем.
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
WolfHound wrote:
> Здравствуйте, MaximE, Вы писали: > > ME>Возможно, что сортировать вектор не очень удачное решение, по сравнению с использованием upper/lower_bound. После вставки sort будет перелопачивать весь массив, lower_bound же найдет тебе нужное место вставки бинарным поиском.
> А потом придется использовать вставку в вектор со сложностью O(N)
> ME>Хотя опять же, сложность lower_bound — гарантировано log2(n), быстрой сортировки std::sort — в среднем c * n * log2(n), в худшем — n ** 2... > Не lower_bound не катит ибо ты забыл еще и про вставку...
Я не забыл. Вставка в вектор занимает амортизированное константное время — O(1).
> А std::sort в томже STLPort реализован через IntroSort у которого нет проблем с худшим случаем.
И что это за алгоритм такой — IntroSort? Два года назад std::sort был реализован как quick sort с оптимизациями по размеру стэка и малых массивов (<25).
Здравствуйте, MaximE, Вы писали:
ME>Я не забыл. Вставка в вектор занимает амортизированное константное время — O(1).
Чего??? Втавка и уделение из вектора с сохранением порядка элементов всегда были O(N). Это вставка/удаление с конца амортизированая константа, а из произвольного места O(N)
ME>И что это за алгоритм такой — IntroSort?
Он для кврадратичных случаев переключается на heapsort. И вобще гугль тебе в помощь.
ME>Два года назад std::sort был реализован как quick sort с оптимизациями по размеру стэка и малых массивов (<25).
Не знаю куда ты там смотрел. Посмотри в последний STLPort
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
WolfHound wrote:
> Здравствуйте, MaximE, Вы писали: > > ME>Я не забыл. Вставка в вектор занимает амортизированное константное время — O(1). > Чего??? Втавка и уделение из вектора с сохранением порядка элементов всегда были O(N). Это вставка/удаление с конца амортизированая константа, а из произвольного места O(N)
Да, я не прав.
23.2.4
A vector is a kind of sequence that supports random access iterators. In addition, it supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time. Storage management is handled automatically, though hints can be given to improve efficiency.
Здравствуйте, Аноним, Вы писали:
А>Есть пара вопросов о multimap: А>1. Как можна при создании multimap, зарезервировать под него место, так что бы при вставке нового элемента не тратилось время на выделение памяти? Просто очень много вставок в процессе работы...
Аллокатор, скажем, поверх вектора (чтобы абстрагироваться от настоящего менеджера памяти). Не такая уж это тяжёлая задача.
А>2. Можна ли в процессе работы менять ключ элемента? Если да, то как?
В принципе, можно было бы поддержать такую фичу (узел из дерева отцепляется, вставляется в новое место, выполняется перебалансировка), но STL такого механизма не содержит. Придётся удалять-вставлять.
А>3. Как ускорить процесс удаления элементов, у меня в мультимапе куча стрингов и профайлер показывает что процесс удаления этих стрингов дольше выполняется чем сам процесс их обработки...
Половина тормозов уйдёт, если стринги будут пользоваться Copy-On-Write. Если твой STL так не делает — пиши рукодельный класс строки либо пользуйся, например, shared_ptr'ами (только аккуратно, чтобы случайно не перековырять разделяемые данные).
Здравствуйте, MaximE, Вы писали:
ME>Возможно, что сортировать вектор не очень удачное решение, по сравнению с использованием upper/lower_bound. После вставки sort будет перелопачивать весь массив, lower_bound же найдет тебе нужное место вставки бинарным поиском.
ME>Хотя опять же, сложность lower_bound — гарантировано log2(n), быстрой сортировки std::sort — в среднем c * n * log2(n), в худшем — n ** 2...
А вставку элемента в середину вектора, в случае использования upper/lower_bound, вы учли?
Serhio wrote:
> Здравствуйте, MaximE, Вы писали: > > ME>Возможно, что сортировать вектор не очень удачное решение, по сравнению с использованием upper/lower_bound. После вставки sort будет перелопачивать весь массив, lower_bound же найдет тебе нужное место вставки бинарным поиском. > > ME>Хотя опять же, сложность lower_bound — гарантировано log2(n), быстрой сортировки std::sort — в среднем c * n * log2(n), в худшем — n ** 2... > > А вставку элемента в середину вектора, в случае использования upper/lower_bound, вы учли?
Впрочем, можно обратить свой взор на AssocVector из Loki.
Перекуём баги на фичи!
