Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
Форум программистов > C/C++: Общие вопросы > STL list или vector |
Автор: lamber 7.1.2011, 16:44 |
Столкнулся с мало знакомым мне явлением, записываю 40мб файл в list и получаю размер программы в памяти порядка 200мб. Но это пол беды как только начинаю орабатывать получившийся массив выкидывает с оибкой меня bad_alloc, не может выделить память, хотя дело в том что я и не выделяю память в своей функции. Прохожусь по данном list' итератором. Вот думаю может использовать вместо list vector. Правда в vector файл загружается достаточно долго (навернное ввиду того что огромное количество new delete), но хотябы не вылеает ошибка памяти. Плотно с STL я не знаком подскажите кто компитентен |
Автор: lamber 7.1.2011, 19:01 |
у меня list<string> а вот сколько элементов там будет по разному может быть очень много а может и не очень ))) |
Автор: azesmcar 7.1.2011, 19:17 |
все равно, оверхэда это не отменяет. Прежде чем использовать любой из контейнеров STL следует понимать как он работает и как хранит данные в памяти. |
Автор: lamber 7.1.2011, 20:27 | ||||||||
опять танцы с бубнами, не могу задача все таже есть два файла зашружаем их первый в vector<string> второй в map<char<vector<string>> формат перового файла somedata key somedata \n key somedata key somedata \n второго файла key=>value key=>value код загрузки файлов загрузка первого файла
загрузка второго файла
key_value это структура
вот основная ф-ция где происходит обработка
Не знаю почему, но программа вылетает выдавай сообщение _Roff off end (после того как выдало ошибку выбрасывает на этот участок кода в stl при использовании контейнера list вылетает из bad_alloc'а) . Вообщем-то в большей степени это продолжения моего топика про обработку больших файлов. Надеюсь на помощь azesmcar'а ))) |
Автор: azesmcar 7.1.2011, 20:33 | ||
lamber Не совсем понял, откуда list, у тебя ведь vector?
хотя в общем итоге у тебя просто памяти не хватает, видимо файлы слишком большие, чтобы их загружать в оперативную память. Хотелось бы побольше разузнать про задачу и алгоритм ее решения, что за файлы (как я понял их два), какого размера и что в итоге нужно получить? |
Автор: lamber 7.1.2011, 20:38 |
В этом топике все изложил http://forum.vingrad.ru/forum/topic-319530/kw-%D0%BE%D0%B1-%D0%BA%D0%B0-%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85.html |
Автор: azesmcar 7.1.2011, 20:43 |
lamber размер второго файла тоже большой? Добавлено @ 20:47 ок. вижу, что во втором файле занимает место, ключ или значение? |
Автор: lamber 7.1.2011, 20:48 |
Отсортировать а потом загружать частями :? Как это лучше использовать и алгоритм какой использовать. Лучше загрузить сначала в контейнер потом отсортировать сохранить в файл обратно а потом загружать :? В первом файле который и является самым большим, key не всегда в одном и том же месте, как мне его сортировать :? |
Автор: azesmcar 7.1.2011, 20:49 |
lamber нет, это я сперва не так понял задачу. Я полагаю, стоит загрузить второй файл в map, а первый вообще не надо загружать, читать его по частям, менять ключи на значения и записывать в третий файл. Правда тут может быть проблема с загрузкой второго, раз уж он такой большой, но можно и его не загружать, а загрузить только ключи и в качестве значения хранить смещение значения в файле, но это имеет смысл если значение на самом деле длинное, если это пара символов то конечно не стоит. |
Автор: lamber 7.1.2011, 20:49 |
во втором файле большее место занимает ключ как правило. |
Автор: azesmcar 7.1.2011, 20:57 | ||||
ну, в крайнем случае можно загрузить не сам файл, а создать какие-то индексы.
файл
создается индекс
т.е. указываются позиции, с которых надо искать в файле некий range чем больше range - тем больше время поиска, но меньше расход памяти. прочитали из второго файла ключ, например key3 ищем в map-е индексов его положение в файле, он располагается между позициями 14 и 27, переходим на эту позицию и ищем оттуда перебором. но если второй файл можно загрузить в память - то лучше конечно загружать. и еще...если ключи слишком длинные их можно хэшировать и хранить не сам ключ а его хэш. надеюсь понятно описал? |
Автор: lamber 7.1.2011, 21:11 |
Не совсем понятно как по индексу искать в файле, т.е. как можно свободно путшествовать по файлу :? я так поняимаю вид должен быть примерно следующий. map<char<vector<int>> где char у нас будет первый символ ключа а vector<int> это номер строк где он содержится. Но вод беда в том что первый файл может и не иметь четкой структуры я имеюю ввидуто что во втором файле все организованно все имеет вид key=>value то первй фал это некоторые предложения где key может идти в организованной форме так и без нее. |
Автор: azesmcar 7.1.2011, 21:18 | ||||||||||
средствами стандартной библиотеки. Функцией seek если быть точным.
нет
что-то вроде этого, где string_range - структура, хранящая key_from и key_to (это отрезок ключей) и соответствующий этому отрезку offset в файле.
да, но это и не нужно. алгоритм примерно следующий
ну и если не удастся загрузить второй файл в память, то придется еще и искать его ключ по файлу, в этом случае файл придется сортировать, так-как искать что-то в чем-то НЕ отсортированном не самая удачная из идей ![]() Желательно конечно загрузить второй файл в память. Попробуй сперва это, если ключи очень длинные - храни хэш. |
Автор: lamber 7.1.2011, 21:23 |
### я думал это казуальная задача а выходит на деле далеко не так. |
Автор: azesmcar 7.1.2011, 21:24 |
ну.. в принципе так оно и есть, просто когда размеры файла превышают всякие разумные пределы, то приходиться иметь дело с непростой оптимизацией. Если загрузишь второй файл в память то задача станет более чем казуальной. |
Автор: lamber 7.1.2011, 21:27 |
Думаю загрузить второй файл т.к. он в разы меньше первого, разбить его в алфавитное дерево map<char<vector<string>> и загружать первый файл кусками и обходить его в цикле. |
Автор: azesmcar 7.1.2011, 21:29 |
lamber Зачем? Почему не просто map<string, string> или hash_table? а первый файл естественно нужно кусками, его всего загружать и не нужно. |
Автор: lamber 7.1.2011, 21:40 | ||
Немного не улавливаю. с hash_table пробовал map<string,vector<string>> но начинает ругатся на следующую конструкцию
ругается на приведение из char в string |
Автор: azesmcar 7.1.2011, 21:42 |
его нет в стандарте, посмотри в boost. а почему vector<string>? я так понял соответствие идет одно к одному key=>value, почему не просто map<string, string> ? ну да, line[0] это первый символ строки, т.е. char, а line - это string |
Автор: lamber 7.1.2011, 22:02 | ||
Это я делаю для того что бы собрать алфавитное дерево т.е. к примеру в первом файле находим первый ключ и начинается он на 'a' зачем просматривать весь массив во втором файле когда мне нужны ключи начинающиеся только с 'a' тогда я просто делаю следующим образом
Я вот так подошел к проблеме чтоб ускорить процесс, он подходит когда первый файл структурирован т.к. когда мы точно знаем где key в первом файле (ну он выделен как то там ) |
Автор: azesmcar 8.1.2011, 07:29 |
lamber поиск в std::map имеет логарифмическую сложность и твое алфавитное дерево будет лишь тормозить. Большинство реализаций map и так хранят данные в виде бинарного дерева, хотя тебя должна интересовать только сложность поиска, остальное не важно. |
Автор: lamber 8.1.2011, 13:02 |
2azesmcar Т.е. ты хочешь сказать что map<string,string> будет быстрее чем map<char<vector<string>> :? Мне критическми является скорость, вчера всю ночь просидел, так и ничего путного не сделал, скорость поиска и замена ацкий ацтой. |
Автор: azesmcar 8.1.2011, 13:13 | ||
Да. Для того map и существует. map<string, string> найдет твой ключ за логарифмическое время, т.е. для миллиона записей там будет порядка 14 итераций (смотри бинарный поиск), а в твоем случае ты за 3-4 итерации найдешь несортированный список, который потом придется обходить линейно, т.е. количество итераций равно количеству записей в векторе. хотя я не совсем понял что за ? это что? вектор ключей, значений или и того и другого? |
Автор: boostcoder 8.1.2011, 13:43 |
а hash_map разве в стандарт не входит? если ключ - строка, то имеет смысл воспользоваться именно hash_map`ом. |
Автор: lamber 8.1.2011, 13:45 |
я имел ввиду map<char<vector<key_value>> где key_value структура string key; string value; Добавлено через 1 минуту и 19 секунд 2boostcoder Не работал с boost'ом разве что с regex'ом если скинешь пример или ссылку на пример будет очень круто. |
Автор: azesmcar 8.1.2011, 14:46 | ||
Нет, но много где реализован. Я так и подумал.
![]() |