Зачем переносить этот std :: vector> так медленно?

Question

У меня есть 1000-строчный файл размером около 400 МБ, представляющий некоторые числовые данные, представленные в виде строки. Я хочу транспонировать данные, чтобы в каждой строке было только 1000 строк (чтобы я мог открыть их и быстро построить с помощью панд).

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

Я использую два вложенных цикла для прохождения 2d-структуры и записываю их в некоторый std :: ofstream. Это очень долго. Затем я попытался сосредоточиться на транспонировании и написал следующий код:

//Read 400MB file, 90K strings per line and 1K lines, and store it into
std::vector<std::vector<std::string>> mData;

// ... 
// IO the file and populate mData with raw data 
// ...

//All rows have same number of string
size_t nbRows = mData.size();
size_t nbCols = mData[0].size();

std::vector<std::vector<std::string> > transposedData(nbCols);
for(size_t i = 0 ; i < nbCols  ; ++i)
{
    transposedData[i].resize(nbRows);
    for(size_t j = 0 ; j < nbRows ; ++j)
    {
        transposedData[i][j] = doc.mData[j][i];
    }
}

Я думал, что нескольких секунд будет достаточно, но это займет несколько минут. Кроме того, я пытаюсь с различными входными размерами (только 3 строки и намного больше строк на строку, для того же размера файла 400 МБ), и это намного быстрее.

РЕДАКТИРОВАТЬ 1

По советам людейЯ выполнил профилирование с помощью callgrind. Я получил это сообщение во время процесса: ... переполнение сегмента brk в потоке # 1: невозможно увеличить до ...

Я проанализировал результат и суммировал его здесь:
25% потрачено вoperator = of basic_string
21% тратится на построение basic_string (с новым временем только 3%)
14% тратится в operator () [] на внешнем векторе
11% тратится наoperator () [] на внутреннем векторе

Спасибо за ваши предложения.

Answer 1

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

Очевидным является то, что вам не нужно транспонировать вектор для транспонирования файла.

vector<vector<string> originalData;
// read the file to originalData

for(size_t i = 0 ; i < nbCols  ; ++i)
{
    for(size_t j = 0 ; j < nbRows ; ++j)
    {
        cout << originalData[j][i] << " ";
    }
    cout<<endl;
}

Предполагается, что вы делаетепо какой-то причине нужно создать транспонированный вектор, один из способов записать цикл транспонирования был бы

vector<vector<string>> transposedData (nbCols);
for (size_t j = 0; j < nbCols; ++j)
{
    transposedData[j].reserve(nrows);
    for (size_t i = 0; i < nbRows; ++i) 
    {
        transposedData[j].emplace_back(originalData[i][j]);
        // if keeping original veector is not needed ...
        // transposedData[j].emplace_back(std::move(originalData[i][j]));
    }
}

. На моей (довольно громоздкой) машине требуется около 6-7 секунд, чтобы транспонировать матрицу 1000x90000 из 3-символьные строки. Это не особенно впечатляет: если вам не нужно транспонировать матрицы из нескольких миллионов элементов 24 часа в сутки, это делает то, что вам нужно, без лишних затрат.

Answer 2

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

Тем не менее, в этом случае я вполне уверен, что проблема может заключаться в том, что вы выделяете 90k векторов строки, каждый из которых имеет размер 1k. Как вы знаете, выделение памяти является дорогостоящим, и это может объяснить ваши потери производительности.

Ниже показано, как вы можете реализовать свой код, используя только массив 1D, выделенный заранее.

size_t nbRows = mData.size();
size_t nbCols = mData[0].size();

auto get_idx = [](const int i, const int nr, const int j)
{
    return i*nr+j;
};

std::vector<std::string> transposedData(nbCols*nbRows);  
for(size_t i = 0 ; i < nbCols  ; ++i)
{
    for(size_t j = 0 ; j < nbRows ; ++j)
    {
        const int idx = get_idx(j, nbCols,i);
        transposedData[idx] = std::move(mData[j][i]);
    }
}

for(size_t i = 0 ; i < nbCols  ; ++i)
{
    for(size_t j = 0 ; j < nbRows ; ++j)
    {
        const int idx = get_idx(j, nbCols,i);
        cout<<transposedData[idx]<<" ";
    }
    cout<<endl;
}    

---

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

Answer 3

На моей машине недостаточно памяти для выполнения этой задачи (см. Ниже). Разделив мои данные на три части, я решил задачу за несколько секунд. Вот вывод кода проверки памяти:

free ram 2.5GB  
IO populating mData with raw data  
free ram 0.2GB  
Empty string capacity : 15 bytes  
Intending to allocate 1.4 GB  
terminate called after throwing an instance of 'std::bad_alloc'  
  what() : std::bad_alloc  
Aborted

Answer 4

Наказание может быть связано с тем, что вы чрезмерно используете размер для вашего цикла for.

Согласно ссылке :

Сложность

Линейная разница между текущим размером и количеством. Дополнительная сложность возможна из-за перераспределения, если емкость меньше, чем количество

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