Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Общие вопросы > STL list или vector


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

Автор: azesmcar 7.1.2011, 17:32
lamber

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

Цитата(lamber @  7.1.2011,  16:44 Найти цитируемый пост)
Правда в vector файл загружается достаточно долго (навернное ввиду того что огромное количество new delete)

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

std::vector<int> x(10000);


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

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

Автор: azesmcar 7.1.2011, 19:17
Цитата(lamber @  7.1.2011,  19:01 Найти цитируемый пост)
у меня list<string>

все равно, оверхэда это не отменяет. Прежде чем использовать любой из контейнеров 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

код загрузки файлов
загрузка первого файла

Код

    string line;
    ifstream infile(filename,ios_base::in);
    while (getline(infile, line, '\n'))
  {
      line.erase(remove(line.begin(),line.end(),' '),line.end());
      if(line!="")
        data.push_back(line);
  }


загрузка второго файла
Код

    string line;
    key_value temp;
    ifstream infile(filename,ios_base::in);
    while (getline(infile, line, '\n'))
  {
      line.erase(remove(line.begin(),line.end(),' '),line.end());
      if(line!="")
    if(explode(line,temp))
        data[line[0]].push_back(temp);
  }
 

 
 key_value это структура 
Код

 struct key_value{
 string key;
 string value; 
 };


вот основная ф-ция где происходит обработка
Код

    int nflush=0;
    int counter=0;
    string str_buffer;    
    for(size_t start=0;start<fIn.size();start++)
    {
        temp=fIn[start];
        for(size_t iter=0;iter<data[temp[0]].size();iter++)
        {
            if(compare(temp,data[temp[0]][iter])){
                nflush++;
                counter++;
                temp=replaceAll(temp,data[temp[0]][iter].value);
                str_buffer.append(temp+"\r\n");
                if(nflush>=500)
                {
                    data.SaveToFile("outputs.txt",str_buffer);
                    wsprintfA(buffer,"Progress: %d",counter);
                    SetWindowTextA(GetDlgItem(thwnd,IDTEXT),buffer);
                    nflush=0;
                    str_buffer.clear();
                }
            }


        }



    }

    MessageBoxA(NULL,"Замена завершенна","MSG",MB_OK);
    _endthreadex(0);
    return 0;
}


Не знаю почему, но программа вылетает выдавай сообщение _Roff off end (после того как выдало ошибку выбрасывает на этот участок кода в stl при использовании контейнера list вылетает из bad_alloc'а) . Вообщем-то в большей степени это продолжения моего топика про обработку больших файлов. Надеюсь на помощь azesmcar'а )))

Автор: azesmcar 7.1.2011, 20:33
lamber

Не совсем понял, откуда list, у тебя ведь vector?
Цитата(lamber @  7.1.2011,  20:27 Найти цитируемый пост)
выбрасывает на этот участок кода в stl при использовании контейнера list


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

Автор: 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 @  6.1.2011,  18:34 Найти цитируемый пост)
достаточно большие от 30-100мб (как первый так и второй) 

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

Автор: 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
Цитата(lamber @  7.1.2011,  20:49 Найти цитируемый пост)
во втором файле большее место занимает ключ как правило. 

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

файл
Цитата

key1=1
key2=2
key3=3
key4=4

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

key1 .. key2 -> 0 .. 13
key3 .. key4 -> 14 .. 27

т.е. указываются позиции, с которых надо искать в файле некий 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
Цитата(lamber @  7.1.2011,  21:11 Найти цитируемый пост)
Не совсем понятно как по индексу искать в файле, т.е. как можно свободно путшествовать по файлу :?

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


Цитата(lamber @  7.1.2011,  21:11 Найти цитируемый пост)
я так поняимаю вид должен быть примерно следующий.
map<char<vector<int>> 
где char у нас будет первый символ ключа а vector<int> это номер строк где он содержится. 

нет
Код

map<string_range, int_range> index;

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

Цитата(lamber @  7.1.2011,  21:11 Найти цитируемый пост)
Но вод беда в том что первый файл может и не иметь четкой структуры я имеюю ввидуто что во втором файле все организованно все имеет вид
key=>value

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

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

while (something_to_read)
{
    data d = file1.read_next();
    data replacement = data_from_file2.find(d);
    if (replacement )
        file3.write(replacement);
    else
        file3.write(d);
}

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

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

Автор: lamber 7.1.2011, 21:23
### я думал это казуальная задача а выходит на деле далеко не так. 

Автор: azesmcar 7.1.2011, 21:24
Цитата(lamber @  7.1.2011,  21:23 Найти цитируемый пост)
### я думал это казуальная задача а выходит на деле далеко не так.  

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

Автор: 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>> но начинает ругатся на следующую конструкцию
Код

string line="somedata";
map<string,vector<string>> table;
table[line[0]].push_back(line);


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

Автор: azesmcar 7.1.2011, 21:42
Цитата(lamber @  7.1.2011,  21:40 Найти цитируемый пост)
Немного не улавливаю. с hash_table 

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

Цитата(lamber @  7.1.2011,  21:40 Найти цитируемый пост)
пробовал map<string,vector<string>> 

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

Цитата(lamber @  7.1.2011,  21:40 Найти цитируемый пост)
ругается на приведение из char в string  

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

Автор: lamber 7.1.2011, 22:02
Это я делаю для того что бы собрать алфавитное дерево т.е.

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

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

Код

map<char,vector<string>> vtoroy_fayl;

for(size_t i=0;i<vtoroy_fayl['a'].size();i++)
{
if(compare(key,vtoroy_fayl['a'][i]))
{
//сохраняем т.к. нашли совпадения

}

}


Я вот так подошел к проблеме чтоб ускорить процесс, он подходит когда первый файл структурирован т.к. когда мы точно знаем где 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
Цитата(lamber @  8.1.2011,  13:02 Найти цитируемый пост)
Т.е. ты хочешь сказать что map<string,string> будет быстрее чем map<char<vector<string>> :?

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

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

Автор: 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
Цитата(boostcoder @  8.1.2011,  13:43 Найти цитируемый пост)
а hash_map разве в стандарт не входит?

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

Цитата(lamber @  8.1.2011,  13:45 Найти цитируемый пост)
я имел ввиду map<char<vector<key_value>> где key_value структура

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

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

 smile 

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)