Правильный способ чтения большого файла в массив символов

Question

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

Я знаю, что получаю эту ошибку:

прекращение вызова после выброса экземпляра 'std :: bad_alloc что (): std :: bad_alloc`

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

Это код, который я использую

#include<iostream>
#include<string.h>
#include<fstream>
#include <time.h>
#include <stdio.h>
using namespace std;

// A utility function to find maximum of two integers
int max(int a, int b)
{   return (a > b)? a : b; }

/* Returns length of longest common substring of X[0..m-1]
   and Y[0..n-1] */
int LCSubStr(char *&X, char *&Y, int m, int n)
{

// Create a table to store lengths of longest common suffixes of
// substrings.   Notethat LCSuff[i][j] contains length of longest
// common suffix of X[0..i-1] and Y[0..j-1]. The first row and
// first column entries have no logical meaning, they are used only
// for simplicity of program
clock_t t;
t=clock();
int** LCSuff = new int*[m+1];
for(int i = 0; i < m+1; ++i)
    LCSuff[i] = new int[n+1];
int result = 0;  // To store length of the longest common substring

/* Following steps build LCSuff[m+1][n+1] in bottom up fashion. */
for (int i=0; i<=m; i++)
{
    for (int j=0; j<=n; j++)
    {
        if (i == 0 || j == 0)
            LCSuff[i][j] = 0;

        else if (X[i-1] == Y[j-1])
        {
            LCSuff[i][j] = LCSuff[i-1][j-1] + 1;
            result = max(result, LCSuff[i][j]);
        }
        else LCSuff[i][j] = 0;
    }
}

t = clock() - t;
printf("It took me %d clicks (%f seconds).\n",t,((float)t)/CLOCKS_PER_SEC);
cout<<"----------------------------"<<endl;
return result;
}

/* Driver program to test above function */
int main()
{
std::ifstream in("F1.txt");
std::string XS((std::istreambuf_iterator<char>(in)),
std::istreambuf_iterator<char>());
std::ifstream inn("F2.txt");
std::string YS((std::istreambuf_iterator<char>(inn)),
std::istreambuf_iterator<char>());

char *X=new char[XS.length()];
char *Y=new char[YS.length()];

XS.copy( X, XS.length() );
YS.copy( Y, YS.length() );
int m = strlen(X);
int n = strlen(Y);

cout << "Length of Longest Common Substring is "
     << LCSubStr(X, Y, m, n)<<endl;
return 0;
}

Answer 1

Вместо того, чтобы читать весь файл в память, вам нужно читать его по частям. Это подразумевает, что ваш алгоритм должен быть переписан для частичного обновления его состояния.

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

В псевдокоде:

state = lcs_init();

for (;;) {
    chunk = read();
    if (eof)
        break;

    state = lcs_update(state, chunk);
}

result = lcs_finish(state);

Как правило, в C ++ (и ООП в целом) это делается с помощью класса, который хранит состояние, то есть ::

LCS lcs;
for (each chunk)
    lcs.update(chunk);
result = lcs.result();