Столкнулся с мало знакомым мне явлением, записываю 40мб файл в list и получаю размер программы в памяти порядка 200мб. Но это пол беды как только начинаю орабатывать получившийся массив выкидывает с оибкой меня bad_alloc, не может выделить память, хотя дело в том что я и не выделяю память в своей функции. Прохожусь по данном list' итератором. Вот думаю может использовать вместо list vector. Правда в vector файл загружается достаточно долго (навернное ввиду того что огромное количество new delete), но хотябы не вылеает ошибка памяти. Плотно с STL я не знаком подскажите кто компитентен

lamber

По умолчанию используй вектор, если задача не требует иного.


можно примерно подсчитать количество загружаемых данных и предварительно попросить вектор выделить нужное количество памяти.


вообще у list-а есть overhead в плане расхода памяти, кроме данных он хранит + 2 указателя (на большинстве платформ 8 байтов) для каждого элемента. Возможно в этом причина нехватки памяти.
40Mb - 41943040 байт, в виде int - это 10485760 элемента, для каждого элемента храниться 12 байт - 10485760 * 12 = 120Mb.

у меня list<string>
а вот сколько элементов там будет по разному может быть очень много а может и не очень )))

все равно, оверхэда это не отменяет. Прежде чем использовать любой из контейнеров STL следует понимать как он работает и как хранит данные в памяти.

опять танцы с бубнами, не могу задача все таже 
есть два файла зашружаем их
первый в 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'а )))

lamber

Не совсем понял, откуда list, у тебя ведь vector?


хотя в общем итоге у тебя просто памяти не хватает, видимо файлы слишком большие, чтобы их загружать в оперативную память. Хотелось бы побольше разузнать про задачу и алгоритм ее решения, что за файлы (как я понял их два), какого размера и что в итоге нужно получить?

В этом топике все изложил http://forum.vingrad.ru/forum/topic-319530...1%8B%D1%85.html

lamber

размер второго файла тоже большой?

Добавлено @ 20:47

ок. вижу, что во втором файле занимает место, ключ или значение?

Это сообщение отредактировал(а) azesmcar - 7.1.2011, 20:47

Отсортировать а потом загружать частями :? Как это лучше использовать и алгоритм какой использовать. Лучше загрузить сначала в контейнер потом отсортировать сохранить в файл обратно а потом загружать :? В первом файле который и является самым большим, key не всегда в одном и том же месте, как мне его сортировать :?

lamber

нет, это я сперва не так понял задачу. Я полагаю, стоит загрузить второй файл в map, а первый вообще не надо загружать, читать его по частям, менять ключи на значения и записывать в третий файл. Правда тут может быть проблема с загрузкой второго, раз уж он такой большой, но можно и его не загружать, а загрузить только ключи и в качестве значения хранить смещение значения в файле, но это имеет смысл если значение на самом деле длинное, если это пара символов то конечно не стоит.

Это сообщение отредактировал(а) azesmcar - 7.1.2011, 20:52

во втором файле большее место занимает ключ как правило.

ну, в крайнем случае можно загрузить не сам файл, а создать какие-то индексы. 

• отсортировать второй файл
• загрузить в map индексы
• искать по индексу ключа в файле

Например 

файл

создается индекс

т.е. указываются позиции, с которых надо искать в файле некий range
чем больше range - тем больше время поиска, но меньше расход памяти.

прочитали из второго файла ключ, например key3
ищем в map-е индексов его положение в файле, он располагается между позициями 14 и 27, переходим на эту позицию и ищем оттуда перебором.

но если второй файл можно загрузить в память - то лучше конечно загружать.

и еще...если ключи слишком длинные их можно хэшировать и хранить не сам ключ а его хэш.

надеюсь понятно описал?

Это сообщение отредактировал(а) azesmcar - 7.1.2011, 21:02

Не совсем понятно как по индексу искать в файле, т.е. как можно свободно путшествовать по файлу :?

я так поняимаю вид должен быть примерно следующий.
map<char<vector<int>> 
где char у нас будет первый символ ключа а vector<int> это номер строк где он содержится. 

Но вод беда в том что первый файл может и не иметь четкой структуры я имеюю ввидуто что во втором файле все организованно все имеет вид
key=>value

то первй фал это некоторые предложения где key может идти в организованной форме так и без нее.

средствами стандартной библиотеки. Функцией seek если быть точным.



нет

что-то вроде этого, где
string_range - структура, хранящая key_from и key_to (это отрезок ключей) и соответствующий этому отрезку offset в файле.


да, но это и не нужно.

алгоритм примерно следующий

ну и если не удастся загрузить второй файл в память, то придется еще и искать его ключ по файлу, в этом случае файл придется сортировать, так-как искать что-то в чем-то НЕ отсортированном не самая удачная из идей 

Желательно конечно загрузить второй файл в память. Попробуй сперва это, если ключи очень длинные - храни хэш.

Это сообщение отредактировал(а) azesmcar - 7.1.2011, 21:23

### я думал это казуальная задача а выходит на деле далеко не так. 

ну.. в принципе так оно и есть, просто когда размеры файла превышают всякие разумные пределы, то приходиться иметь дело с непростой оптимизацией. Если загрузишь второй файл в память то задача станет более чем казуальной.

Думаю загрузить второй файл т.к. он в разы меньше первого, разбить его в алфавитное дерево map<char<vector<string>> и загружать первый файл кусками и обходить его в цикле.

lamber

Зачем? Почему не просто
map<string, string> или hash_table? а первый файл естественно нужно кусками, его всего загружать и не нужно.

Немного не улавливаю. с hash_table 

пробовал map<string,vector<string>> но начинает ругатся на следующую конструкцию


ругается на приведение из char в string 

его нет в стандарте, посмотри в boost.


а почему vector<string>?
я так понял соответствие идет одно к одному key=>value, почему не просто
map<string, string> ?


ну да, line[0] это первый символ строки, т.е. char, а line - это string

Это я делаю для того что бы собрать алфавитное дерево т.е.

к примеру в первом файле находим первый ключ и начинается он на 'a' зачем просматривать весь массив во втором файле когда мне нужны ключи начинающиеся только с 'a' 

тогда я просто делаю следующим образом



Я вот так подошел к проблеме чтоб ускорить процесс, он подходит когда первый файл структурирован т.к. когда мы точно знаем где key в первом файле (ну он выделен как то там )

Это сообщение отредактировал(а) lamber - 7.1.2011, 22:10

lamber

поиск в std::map имеет логарифмическую сложность и твое алфавитное дерево будет лишь тормозить. Большинство реализаций map и так хранят данные в виде бинарного дерева, хотя тебя должна интересовать только сложность поиска, остальное не важно.

Это сообщение отредактировал(а) azesmcar - 8.1.2011, 07:39

2azesmcar
Т.е. ты хочешь сказать что map<string,string> будет быстрее чем map<char<vector<string>> :?
Мне критическми является скорость, вчера всю ночь просидел, так и ничего путного не сделал, скорость поиска и замена ацкий ацтой.

Да. Для того map и существует. 
map<string, string> найдет твой ключ за логарифмическое время, т.е. для миллиона записей там будет порядка 14 итераций (смотри бинарный поиск), а в твоем случае ты за 3-4 итерации найдешь несортированный список, который потом придется обходить линейно, т.е. количество итераций равно количеству записей в векторе.
хотя я не совсем понял что за

? это что? вектор ключей, значений или и того и другого?

Это сообщение отредактировал(а) azesmcar - 8.1.2011, 13:15

а hash_map разве в стандарт не входит?
если ключ - строка, то имеет смысл воспользоваться именно hash_map`ом.

я имел ввиду map<char<vector<key_value>> где key_value структура

string key;
string value;

Добавлено через 1 минуту и 19 секунд
2boostcoder
Не работал с boost'ом разве что с regex'ом если скинешь пример или ссылку на пример будет очень круто.

Нет, но много где реализован.


Я так и подумал.