Страница 1 из 1
std::map
Добавлено: 06 дек 2005, 13:58
Alezis
Мне нужно было создать ас. контейнер в котором ключом есть int а самим значением какой-то объект, котрый представляет собой структуру с некоторыми данными параметрами. Объектов в среднем что то вроде 1млн. , затраты памяти пока ужасные но этого пока не касаемся. map сортирует всё по убыванию моего ключа, это меня устраивает. Вопрос вот в чем. Когда я начинаю обработку этих объектов , то уж больно "долго" идёт эта обработка. Счас уточню. Долго относительно того же алгоритма только на CSharp где место map используется Hashtable. Она тоже сортирует по убыванию ключа что мне и надо. Так вот CSharp работает допустим 8 сек. ТО С++ около 25. Ошибки в алгоритме нет. просто мот сам цикл долго ходит. он типа такой.
Код: Выделить всё
Obj* o;
for(iterator = _map.begin();!(iterator == _map.end());iterator++)
{
std::pair<int,Obj*> s = *iterator;
o = s.second;
....
}
Как мот лучше огранизовать перебор.
Далее.Если я ставлю hash_map
Всё не отсортировано, но это меня тоже устраивает.
Но теперь как организовать перебор потому что насколько я понимаю
через iterator не покатит.
Добавлено: 06 дек 2005, 14:37
Kolinus
перебор оптимизировать можно если идти с конца в начало
плюс возможно стоит условие окончания модифицировать таким образом чтобы вынести получение нужного элемента до цикла а в цикле сравнивать с полученным значением.
все зависит от версии и настроек компилятора - но наиболее часто помогающие способы я написал.
Добавлено: 06 дек 2005, 16:09
Absurd
Если добавления происходят редко, то можно использовать std::vector< std:
air<int, ValType> > , затем поддерживать все это дело в отсортированном состоянии и искать бинарным поиском. Можешь взять из Loki класс Loki::AssocVector, он все это делает автоматически.
Добавлено: 06 дек 2005, 16:41
Eugie
Относительно hash_map. Он а) хранит элементы в отсортированном виде (один из параметров конструктора включает предикат сортировки) и б) содержит внутренний тип iterator, аналогично другим контейнерам STL. Надо только иметь в виду, что в разных версиях STL hash-контейнеры могут и не включаться в std namespace, например, в Visual C++ .NET 2003 требуется указывать дополнительно using namespace <stdext>
Добавлено: 08 дек 2005, 14:38
Alezis
мда... чёто тут попробовал и list и hash и map. Всё как то медленно пашет. Просто когда загоняю в контейнер значения (1000000 штук) они только могут удалятся, но не добавляться. Т.е. после обработки всего контейнера, оттуда например надо удалить 300000 штук. т.е. остаётся 700000. Ну и так далее в итоге должно оставаться около 5000 сиз 1 миллиона. я вот думаю забить на stl и сделать с помощью обычных массивов. Хотя мот просто алгоритм жрёт много.
Добавлено: 09 дек 2005, 01:44
WinMain
Если массив отсортирован по какому-то ключевому параметру, то поиск в нём осуществляется не последовательным перебором, а методом деления пополам (т.н. бинарный поиск). Для поиска значения в массиве из 1.000.000 элементов потребуется не более 20 итераций. Ещё для организации большого массива данных и поиска значений по индексу используют бинарное дерево сортировки. Об этом отдельный разговор. Контейнеры STL свми по себе довольно медленные, поэтому неудивительно, что у тебя программа тормозит и большой расход памяти наблюдается.
Добавлено: 09 дек 2005, 11:11
Absurd
А нафиг тебе в память такие большие объемы загружать? Используй B* деревья и грузи их по кусочкам