Многопотоковые итераторы c ++ - PullRequest
0 голосов
/ 22 октября 2018

Цель моей программы - открыть текстовый файл m строк одинаковой длины n , прочитать файл столбец за столбцом и распечатать каждый столбец.

Например, для этого текстового файла

abcd
efgh 
jklm

Я хотел бы напечатать

a e j
b f k
c g l
d h m

Поскольку длина одной строки может составлять 200 000 000, а длина столбца можетбыть больше 10 000, я не могу открыть весь файл в памяти в матрице.

Теоретически, я хотел бы иметь программу, которая использует O (m) в пространстве и O (m * n)во времени.

Сначала мне нужно было подумать об этих решениях:

  • если я вижу все файлы для каждого столбца, сложность O (m * n²),
  • Если я использую seekg и массив позиций и прыгаю с позиции на позицию, сложность O (m n log (n)).

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

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

ifstream str2;
str2.open ("Input/test.data", ifstream::in);

int nbline = 3;
int nbcolumn = 4;
int x = 0;

istreambuf_iterator<char> istart (str2);
istreambuf_iterator<char> iend ;

istreambuf_iterator<char>* iarray;
iarray = new istreambuf_iterator<char>[nbline];


while (istart != iend){
    if (x % nbcolumn == 0){
        iarray[x/nbcolumn] = istart;
    }
    istart++;
    x++;
}

for (int j = 0; j<nbcolumn;j++){
    for (int i = 0; i<nbline;i++){
        cout  << *iarray[i] << "\t";
        iarray[i]++;
    }
    cout << endl;
}

К сожалению, он не работает, и у меня есть эта вещь в качестве вывода

a       e       f       
�       �       �       
�       �       �       
�       �       �       

Я думаю, проблема в том, что массив итераторов iarray не зависят от istart , как я могу это сделать?

Ответы [ 5 ]

0 голосов
/ 15 декабря 2018

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

Позвольте мне сначала объяснить, что я пытаюсь сделать;Вы знаете, что чтение файлов происходит намного быстрее, если вы делаете это последовательно.То, что я там делаю, это буферизованное чтение.Допустим, в вашем примере я буферизую две строки, поэтому мне нужно выделить 6 байтов буфера и заполнить его поисками;Каждое чтение будет читать два байта, поскольку мы держим две строки.Это может быть оптимизировано, хотя, если вы распечатываете первый символ сразу после прочтения, вы можете буферизовать две строки, просто используя 3 байта и трилины, просто буферизуя 6 байтов в вашем примере.В любом случае, я даю вам неоптимизированную версию.

Опять позвольте напомнить вам, что нельзя использовать istreambuf_iterator дважды: Как использовать итератор в ifstream дважды в C ++?

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

#include <iostream>
#include <fstream>
#include <vector>
#include <stdexcept>
#include <sstream>
#include <algorithm>

std::vector<std::size_t> getPositions(std::ifstream& str2, int &numcolumns) {
    std::vector<std::size_t> iarray;

    iarray.push_back(0); // Add first iterator

    bool newlinereached = false;
    int tmpcol = 0;
    int currentLine = 0;
    char currentChar = 0;
    char previosChar = 0;

    numcolumns = -1;

    for (str2.seekg(0, std::ios_base::beg); !str2.eof(); previosChar = currentChar) {
        const std::size_t currentPosition = str2.tellg();
        str2.read(&currentChar, 1);
        if (newlinereached) {
            if (currentChar == '\r') {
                // Always error but skip for now :)
                continue;
            }
            else if (currentChar == '\n') {
                // ERROR CONDITION WHEN if (numcolumns < 0) or previosChar == '\n'
                continue;
            }
            else if (tmpcol == 0) {
                throw std::runtime_error((std::stringstream() << "Line " << currentLine << " is empty").str());
            }
            else {
                if (numcolumns < 0) {
                    // We just found first column size
                    numcolumns = tmpcol;
                    iarray.reserve(numcolumns);
                }
                else if (tmpcol != numcolumns) {
                    throw std::runtime_error((std::stringstream() << "Line " << currentLine
                        << " have incosistend number of columns it should have been " << numcolumns).str());
                }

                iarray.push_back(currentPosition);
                tmpcol = 1;
                newlinereached = false;
            }
        }
        else if (currentChar == '\r' || currentChar == '\n') {
            newlinereached = true;
            ++currentLine;
        }
        else {
            tmpcol++;
        }
    }

    if (currentChar == 0) {
        throw std::runtime_error((std::stringstream() << "Line " << currentLine
            << " contains 'null' character " << numcolumns).str());
    }

    str2.clear(); // Restart 

    return iarray;
}

int main() {
    using namespace std;

    ifstream str2;
    str2.open("Text.txt", ifstream::in);
    if (!str2.is_open()) {
        cerr << "Failed to open the file" << endl;
        return 1;
    }

    int numinputcolumns = -1;

    std::vector<std::size_t> iarray =
        getPositions(str2, numinputcolumns); // S(N)

    const std::size_t numinputrows = iarray.size();

    std::vector<char> buffer;
    const int numlinestobuffer = std::min(2, numinputcolumns); // 1 For no buffer

    buffer.resize(numinputrows * numlinestobuffer); // S(N)

    const std::size_t bufferReadMax = buffer.size();


    for (int j = 0; j < numinputcolumns; j += numlinestobuffer)
    {
        // Seek fill buffer. Needed because sequental reads are much faster even on SSD
        // Still can be optimized more: We can buffer n+1 rows as we can discard current row read
        std::size_t nread = std::min(numlinestobuffer, numinputcolumns - j);
        for (int i = 0; i < numinputrows; ++i)
        {
            str2.seekg(iarray[i], ios_base::beg);
            size_t p = str2.tellg();
            str2.read(&buffer[i * numlinestobuffer], nread);
            iarray[i] += nread;
        }

        // Print the buffer
        for (int b = 0; b < nread; ++b)
        {
            for (int k = 0; k < numinputrows; ++k) {
                std::cout << buffer[b + k * numlinestobuffer] << '\t';
            }
            std::cout << std::endl;
        }
    }

    return 0;
}
0 голосов
/ 13 декабря 2018

Я бы сделал это следующим образом:

  1. Откройте исходный файл.
  2. Измерьте размер строки
  3. Измерьте количество строк (размер файла / (размер строки +размер EOL)).Примечание EOL может быть 2 байта.
  4. рассчитать размер файла результата.Откройте файл результатов и задайте для него желаемый размер, чтобы позже можно было искать любую часть файла.
  5. Пиковый размер квадрата, который можно контролировать из памяти.Например, 1024x1024
  6. Теперь вам нужно загрузить квадратную часть матрицы.1024 элемента для строк из 1024 составных строк.
  7. Транспонировать квадрат
  8. Запишите его в конечный файл, обратившись к соответствующему столбцу каждой части строки, которую вы пишете.(вы можете уменьшить потребление памяти в предыдущей точке, транспонировав один столбец, а затем записав его в виде строки, вместо того, чтобы сразу транспонировать целый квадрат)
  9. Итерировать квадрат по всей матрице файлов

IMOты не можешь сделать это лучше.Наиболее важным будет то, как выбрать размер квадрата.Рекомендуется большая сила 2.

0 голосов
/ 12 декабря 2018

Общие соображения

Если бы массив итераторов работал, ему пришлось бы перебирать память (см. Также ответ Уильяма Миллера), или где он должен перебирать?

Компромисс:

  1. Разбор до завершения первой строки вывода, чем тот же для всех других строк вывода
    • медленно, почти не используется память
  2. Полностью заполнить матрицу и вывести транспонированную матрицу
    • много используемой памяти
  3. Создать массив позицийдля всех выходных линий ищите через все позиции
    • быстро и разумно используйте память
  4. Очень разумное сочетание методов 2 и 3.
    • сокращает возможное время с данной памятью (например, например, 8 ГБ ОЗУ).

Решение для компромисса 4

Требуется больше знаний о граничном условии.

Концепция решения 4 зависитна многих неизвестных условиях

  • Каковы характеристики входных данных?
    • Является ли 200TByte для одной матрицы для нескольких матриц?
    • Для сколько?
    • Каков наихудший случай соотношения между столбцами и строками?
    • Это просто отдельные символы или могут быть слова?
    • Если это просто отдельные символы, гарантируется ли, что каждая строка имеет одинаковый объем памяти?
    • Если нет, как распознать новыйстрока?
  • Сколько свободной оперативной памяти доступно?
  • Как быстро целевой компьютер заполняет всю свободную оперативную память?
  • Что такоемаксимально допустимое время?

Анализ проблемы с исходной программой

Вопрос также: почему это не работает.

Программа ...

#include    <fstream>
#include    <string>
#include    <iostream>

int main(int argc, char* argv[]) {
    std::ifstream str2;
    str2.open ("test.data", std::ifstream::in);

    std::istreambuf_iterator<char> istart(str2);
    std::istreambuf_iterator<char> iend;
    std::istreambuf_iterator<char> iarray1 = istart;

    istart++;
    istart++;
    istart++;
    istart++;
    std::istreambuf_iterator<char> iarray2 = istart;

    std::cout  << *(iarray1);
    std::cout << std::endl;
    std::cout  << *(iarray2);
    std::cout << std::endl;
    return 0;
}

... читает test.data содержит ...

abcdefghjklm

... и программа печатает ...

e
e

Следовательно, цикл ...

while (istart != iend){
    if (x % nbcolumn == 0){
        iarray[x/nbcolumn] = istart;
    }
    istart++;
    x++;
}

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

iarray[i]++;

... манипулирует всеми итераторами одновременно.


Решение для компромисса 3

Какой выход?Создание кода в соответствии с компромиссом № 3.

Программа ...

#include    <iostream>
#include    <ios>
#include    <string>
#include    <fstream>

int main(int argc, char* argv[]) {
    int nbline = 3;
    int nbcolumn = 4;
    std::ifstream   fsIn;
    std::streampos  posLine[nbline];
    std::streampos  posTemp;

    fsIn.open("test.data", std::ifstream::in);
    for ( int i = 0; i < nbline; i++) {
        posLine[i] = posTemp;
        posTemp += nbcolumn;
    }

    for ( int j = 0; j < nbcolumn; j++) {
        for ( int i = 0; i < nbline; i++) {
            fsIn.seekg(posLine[i]);
            std::cout  << char(fsIn.get()) << " ";
            posLine[i] = fsIn.tellg();
        }
        std::cout << std::endl;
    }
    return 0;
}

... создает вывод:

a e j
b f k
c g l
d h m
0 голосов
/ 12 декабря 2018

Если вы хотите сделать это, используя несколько std::istreambuf_iterator с, вам понадобится несколько fstreams, чтобы они действовали, в противном случае, когда вы выполните итерацию одного (то есть istart++), который повлияет на все итераторы для этого fstream, что означает, что при следующей итерации одного (то есть *iarray[i]++) вы пропустите символ.Это объясняется более четко в справке .Рассмотрим следующий фрагмент:

std::ifstream str;
str.open("test.data", std::ifstream::in);

std::istreambuf_iterator<char> i1 (str);
std::istreambuf_iterator<char> i2 (str);

std::cout << "i1 - " << *i1 << "   i2 - " << *i2 << std::endl;
i1++;
std::cout << "i1 - " << *i1 << "   i2 - " << *i2 << std::endl;
i2++;
std::cout << "i1 - " << *i1 << "   i2 - " << *i2 << std::endl;

, который будет выводить

i1 - a   i2 - a
i1 - b   i2 - a
i1 - b   i2 - c

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

std::ifstream str;
str.open("test.data", std::ifstream::in);

std::istreambuf_iterator<char> i1 (str);
std::istreambuf_iterator<char> i2;
std::istreambuf_iterator<char> iend;

int x = 0;
while (i1 != iend) {
    if (x % 4 == 0) {
        i2 = i1;
        break;
    }
    x++;
    i1++;
}

std::cout << *i1 << " " << *i2 << std::endl;
i1++;
std::cout << *i1 << " " << *i2 << std::endl;
i2++;
std::cout << *i1 << " " << *i2 << std::endl;

, результат останется прежним -

i1 - a   i2 - a
i1 - b   i2 - a
i1 - b   i2 - c

Почему?

Поскольку в обоих случаях оба итератора действуют на один и тот же объект потока, и каждый раз, когда вы выполняете один итератор, он удаляет символ из потока.В рассматриваемом коде каждый итератор (istart, iarray[i]) действует на один и тот же объект потока, и поэтому каждая итерация одного из них удаляет char из потока.Выходные данные быстро становятся результатом неопределенного поведения, поскольку итерации за end-of-stream не определены (и поскольку итераторы итерируют вместе, вы быстро достигаете его).


Если вы хотите сделать это так, как у вас есть контур, вам просто нужно несколько fstream объектов, таких как

#include <fstream>
#include <string>
#include <iostream>


int main(int argn, char** argv) {
    std::ifstream str2;
    str2.open ("test.data", std::ifstream::in);

    int nbline = 3;
    int nbcolumn = 4;
    int x = 0;

    std::istreambuf_iterator<char> istart (str2);
    std::istreambuf_iterator<char> iend ;

    std::ifstream* streams = new std::ifstream[nbline];
    for (int ii = 0; ii < nbline; ii++) {
        streams[ii].open("test.data", std::ifstream::in);
    }
    std::istreambuf_iterator<char>* iarray = new std::istreambuf_iterator<char>[nbline];
    for (int ii = 0; ii < nbline; ii ++) {
        iarray[ii] = std::istreambuf_iterator<char> (streams[ii]);
    }

    int idx = 0;
    while (istart != iend) {
        if (x % nbcolumn == 0) {
            std::advance(iarray[x/nbcolumn], (nbcolumn+1)*idx);
            idx++;
        }
        x++;
        istart++;
    }

    for (int ii = 0; ii < nbcolumn; ii ++) {
        for (int jj = 0; jj < nbline; jj ++) {
            std::cout << *iarray[jj]++ << "\t";
        }
        std::cout << std::endl;
    }
}

, который производит ожидаемый результат,

a       e       j
b       f       k
c       g       l
d       h       m

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

0 голосов
/ 09 декабря 2018

Вы можете разбить задачу на части, затем обработать каждый кусок перед тем, как перейти к следующей.

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

Считать B байтов в буфер для каждой строки (используя tellg для сохранения позиции в каждой строке),затем зациклите их и сгенерируйте результат.Вернитесь назад и прочитайте следующие B байтов из каждой строки (используя seekg, чтобы заранее установить положение файла, и tellg, чтобы запомнить это позже) и сгенерируйте вывод.Повторяйте до тех пор, пока не закончите, следя за тем, чтобы последний кусок (или с небольшими входами) не проходил за конец строки.

Используя ваш пример, у вас есть 3 строки для отслеживания.Используя размер B 2, вы прочитали бы ab, ef и jk в ваши 3 буфера.Перебирая те, которые вы выводите aej и bfk.Вернитесь и прочитайте следующие фрагменты: cd, gh и lm.Это дает cgl и dhm в качестве вывода.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...