Добрый день. Существует обертка на некоторым контейнером, которая занимается тем, что вставляет в этот контейнер указатели и периодически достает элемент, который имеет наименьшее значение ключа ( тип ключа unsigned long ). Дело в том, что в этом контейнере может хранится ~40M этих указателей. И вставка в контейнер происходит достаточно интенсивно. Сейчас работает std::multimap, он дает в принципе достаточно приемлимое время вставки, но пока максимальное число элементов ~2M. Настораживает потребление памяти этим map которое, будет при 40M и скорость (ведь у него время поиска log(n), если я не ошибаюсь). Пробовал использовать хэшированные контейнеры, но в моей реализации все время съедает операции с вектором, при помощи которого он реализован, даже если место заранее резервировать, по времени он работает примерно так же как и multimap. Вопросов несколько:
1. Имеет ли смысл выносить вставку в контейнер в отдельный поток (запрос элемента из контейнера не намного реже вставки)? Если имеет, то как это обычно организовывается?
2. Имеет ли смысл использовать для map свой аллокатор?
3. Какой же контейнер все таки выбрать?
Re: C++: Вставка большого числа элементов в контейнер.
Здравствуйте, Dmitriy Lyfar, Вы писали:
DL>Добрый день. Существует обертка на некоторым контейнером, которая занимается тем, что вставляет в этот контейнер указатели и периодически достает элемент, который имеет наименьшее значение ключа ( тип ключа unsigned long ). DL>3. Какой же контейнер все таки выбрать?
Погляди на priority_queue, вроде похоже на то, что ты хочешь.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re: C++: Вставка большого числа элементов в контейнер.
Здравствуйте, Dmitriy Lyfar, Вы писали:
DL>Добрый день. Существует обертка на некоторым контейнером, которая занимается тем, что вставляет в этот контейнер указатели и периодически достает элемент, который имеет наименьшее значение ключа ( тип ключа unsigned long ). Дело в том, что в этом контейнере может хранится ~40M этих указателей. И вставка в контейнер происходит достаточно интенсивно. Сейчас работает std::multimap, он дает в принципе достаточно приемлимое время вставки, но пока максимальное число элементов ~2M. Настораживает потребление памяти этим map которое, будет при 40M и скорость (ведь у него время поиска log(n), если я не ошибаюсь). Пробовал использовать хэшированные контейнеры, но в моей реализации все время съедает операции с вектором, при помощи которого он реализован, даже если место заранее резервировать, по времени он работает примерно так же как и multimap. Вопросов несколько:
В чистом виде хэш-таблица не предоставляет возможности найти минимальный элемент лучше чем полным перебором. Как Вам удаётя извлечь элемент с минимальным значением ключа из хэшированного контейнера?
DL>1. Имеет ли смысл выносить вставку в контейнер в отдельный поток (запрос элемента из контейнера не намного реже вставки)? Если имеет, то как это обычно организовывается?
ИМХО не имеет. Всё равно прийдётся синхронизировать вставку и запрос, так что паралельного доступа не выйдет. Если есть реализация multimap, которая поддерживает более мелкозернистую синхронизацию, тогда могло бы иметь смысл. Но насколько я знаю все stl контейнеры вообще не thread-safe.
DL>2. Имеет ли смысл использовать для map свой аллокатор?
Может помочь. Все элементы одного размера и при этом существуют способы сделать fixed-size аллокатор быстрее чем в общем случае, при переменном размере элементов.
Re: C++: Вставка большого числа элементов в контейнер.
Здравствуйте, Dmitriy Lyfar, Вы писали:
DL>Добрый день. Существует обертка на некоторым контейнером, которая занимается тем, что вставляет в этот контейнер указатели и периодически достает элемент, который имеет наименьшее значение ключа ( тип ключа unsigned long ).
