Форум программистов, компьютерный форум CyberForum.ru

Замена строк в текстовых документах больших размеров - C++

Восстановить пароль Регистрация
 
Vanya_qwestions
Сообщений: n/a
05.09.2013, 19:29     Замена строк в текстовых документах больших размеров #1
Дан текстовой документ размером в несколько гигабайт( больше миллиона строк) и номера двух строк, расположенных в произвольной части файла. Необходимо, максимально быстро найти обе строки, и поменять их местами. Длина строк не фиксирована и может быть совершенно разной. Как можно максимально ускорить построчный поиск признаков конца строки, чтобы как можно быстрее добраться до искомой строки?

P.S.: Количество строк в документе неизвестно, значит несколько потоков для одновременного поиска с начала и с конца, не получиться.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gazlan
2857 / 1805 / 271
Регистрация: 27.08.2010
Сообщений: 4,888
Записей в блоге: 1
05.09.2013, 21:33     Замена строк в текстовых документах больших размеров #2
Размер строки (если только он не фиксирован, как в .DBF, например), ни на что не влияет.

Поскольку EOL-маркер это 1 или 2 байта (зависит от OS), то быстрее, чем полным перебором по файлу, найти индексы строк не получится.

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

Если одноразовая - обмен только двух строк - тупо сканировать до большего номера строки, потом делать обмен. Быстрее не получится.
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
06.09.2013, 01:47     Замена строк в текстовых документах больших размеров #3
Когда-то делал:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
// без зависимости от '\n' в конце файла
 
#include <windows.h>
#include <iostream>
#include <fstream>
#include <string>
 
using namespace std;
 
const long long int N = 100000000000;
 
const char* filename = "1.txt";
 
void createfile() //создание файла для теста
{
    //string str = "AAAAAAAAAA";
    ofstream fout("test.txt");
    for (int i = 0; i < N; ++i)
    {
        fout << i + 1 << endl;
        //fout << str << endl;
    }
    fout.close();
}
 
char* findStr(char *begin, int n, int w, unsigned long &c) // поиск начала n-ой строки  
                                                           // w - это номер строки, от которой начинается поиск
                                                           // c - счётчик байтов
{
    while (w != n)
    {
        if (*begin == '\n') ++w;
        ++begin;
        ++c;
    }
    
    return begin;
}
 
int numberStr(char *pvFileSrc, unsigned long fileSize, int &flag_n) // подсчёт количества строк
{
    int n = 0;           // количество строк
    unsigned long c = 0; // счётчик байтов
    while (c != fileSize)
    {
        if (*pvFileSrc == '\n') ++n;
        ++pvFileSrc;
        ++c;
    }
    --pvFileSrc;
    if (*pvFileSrc == '\n') // если последняя строка заканчивается на '\n'
    {
        flag_n = 1;
        return n;
    }
    return n + 1;
}
 
void transfer(char* begin, char* end, int offset) // перемещение данных между переставляемыми строками
{
    if (offset > 0) // если первая строка меньше второй
    {
        --end;
        while (end >= begin)
        {
            *(end + offset) = *end;
            --end;
        }
    }
    else // offset отрицательный
    {
        while (begin != end)
        {
            *(begin + offset) = *begin;
            ++begin;
        }
    }
}
 
void showStr(int num1, int num2) // вывод двух строк из файла
{
    FILE *fin = fopen(filename, "rb"); // в бинарном быстрее
    
    if (!fin) 
    {
        printf("Error!\n");
        return;
    }
    else
    {
        char str1[500];
        char str2[500];
        char temp[500];
        
        int i = 1;
        while (true) 
        {
            if (i == num1) 
            {
                fgets(str1, 500, fin);
                cout << num1 << ") " << str1;
                ++i;
                break;
            }
            fgets(temp, 500, fin); 
            ++i;
        }
        while (true)
        {
            if (i == num2) 
            {
                fgets(str2, 500, fin);
                cout << num2 << ") " << str2;
                ++i;
                break;
            }
            fgets(temp, 500, fin); 
            ++i;
        }
    }
}
 
 
int main(int argc, char *argv[])
{
    //createfile();
    
    HANDLE file = CreateFile(filename, GENERIC_READ | GENERIC_WRITE, 0, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
    DWORD fileSize = GetFileSize(file, NULL);
    HANDLE fileMap =  CreateFileMapping(file, NULL, PAGE_READWRITE, 0, 0, NULL);
    CloseHandle(file);
    char *pvFileSrc = (char*)MapViewOfFile(fileMap, FILE_MAP_WRITE, 0, 0, fileSize);
    CloseHandle(fileMap);
    
    //cout << pvFileSrc; // вывод всех строк из проекции файла (демонстрация). В памяти, после последнего символа строки, стоят '\0',
                         // поэтому корректный вывод возможен
    
    int flag_n = 0;                                 // флаг наличия в конце последней строки '\n' (1, если есть)
    unsigned long c = 0;                            // счётчик байтов
    
    int n = numberStr(pvFileSrc, fileSize, flag_n); // количество строк
    cout << "n = " << n << endl << endl;
    
    int num1 = 4, num2 = 1;  // номера переставляемых строк
    
    if (num1 < 0 || num1 > n || num2 < 0 || num2 > n) // проверка корректности номеров строк
    {
        cout << "Incorrect line numbers: " << num1 << ", " << num2 << " !" << endl;
        return 0;
    }
    if (num1 > num2) // если номер первой строки больше второй, то перестановка значений
    {
        int temp = num1;
        num1 = num2;
        num2 = temp;
    }
    
    //showStr(num1, num2); // вывод двух строк из файла до перестановки (демонстрация)
    //cout << endl << endl;
    
    string str1, str2;
    
    char *num1_begin = findStr(pvFileSrc, num1, 1, c); // начало num1, первой из переставляемых строк (ищем от начала строк)
    char *num1_end   = findStr(num1_begin, 2,   1, c); // конец num1 (начало следующей)  
    
    str1.assign(num1_begin, num1_end); // сохраняем num1 (будем менять на num2)
    
    char *num2_begin = findStr(num1_end, num2, num1 + 1, c); // начало num2, второй из переставляемых строк (ищем от следующей за num1)
    char *num2_end;
    if (num2 == n && flag_n == 0) // если последняя строка не заканчивается символом новой строки
    {
        int size_end_str = fileSize - c;        // размер последней строки
        num2_end  = num2_begin + size_end_str;  // конец num2 (конец проекции файла)
    
    }
    else num2_end  = findStr(num2_begin, 2, 1, c);      // конец num2 (начало следующей) 
                                                   
    str2.assign(num2_begin, num2_end); // сохраняем num2 (будем менять на num1)
    
    int offset = str2.size() - str1.size(); // размер смещения данных между переставляемыми строками
 
    if ((offset == 0 && flag_n == 1) || (offset == 0 && num2 != n)) // если переставляемые строки равны 
                                                                    // и последняя строка заканчивается символом новой строки
                                                                    // или вторая строка не последняя
    {
        cout << num1 << ") " << str1;   // выводим переставляемые строки (демонстрация)     
        cout << num2 << ") " << str2;
        cout << endl;
        
        // переставляем строки
        strncpy(num1_begin, str2.c_str(), str2.size()); 
        strncpy(num2_begin, str1.c_str(), str1.size());
    }
    else if (num2 == n && flag_n == 0) // если последняя строка не заканчивается символом новой строки
         {
            str2.append("\r\n");
            if (str2.size() - str1.size() == 0)
            {
                str1.erase(str1.size() - 2, 2);
 
                // выводим переставляемые строки (демонстрация)
                cout << num1 << ") " << str1;        
                //if (num2 == n && flag_n == 0) // если последняя строка не заканчивается символом новой строки
                    cout << endl;
                cout << num2 << ") " << str2;
                cout << endl;
                
                // переставляем строки
                strncpy(num1_begin, str2.c_str(), str2.size()); 
                strncpy(num2_begin, str1.c_str(), str1.size());
            }
            else 
            {
                str1.erase(str1.size() - 2, 2);
                offset += 2; 
                
                // выводим переставляемые строки (демонстрация)
                cout << num1 << ") " << str1;     
                cout << endl;
                cout << num2 << ") " << str2;
                cout << endl;
 
                transfer(num1_end, num2_begin, offset);  // перемещаем данные между переставляемыми строками  
         
                // переставляем строки
                strncpy(num1_begin, str2.c_str(), str2.size());         
                strncpy(num2_begin + offset, str1.c_str(), str1.size());
            }
        }
        else
        {
            // выводим переставляемые строки (демонстрация)
            cout << num1 << ") " << str1;        
            if (num2 == n && flag_n == 0) // если последняя строка не заканчивается символом новой строки
                cout << endl;
            cout << num2 << ") " << str2;
            cout << endl;
 
            transfer(num1_end, num2_begin, offset);     // перемещаем данные между переставляемыми строками  
            
            // переставляем строки
            strncpy(num1_begin, str2.c_str(), str2.size()); 
            strncpy(num2_begin + offset, str1.c_str(), str1.size());
        }
            
    // демонстрация
    showStr(num1, num2);          // вывод двух строк из файла после перестановки
    if (num2 == n && flag_n == 0) // если последняя строка не заканчивается символом новой строки
        cout << endl;
    
    //cout << pvFileSrc;  // вывод всех строк после перестановки (демонстрация)
 
    UnmapViewOfFile( pvFileSrc );
    
    return 0;
}


Добавлено через 2 минуты
Чтобы зарезервированной памяти хватило на файл в несколько Гб, нужно создавать проект х64.

Добавлено через 6 минут
Вариант без мапирования (запись в другой файл):
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// если одна из строк последняя, то проверить наличие '\n' в конце строки.
// если нет, то добавить, а у строки, которая будет последней - убрать '\n'
 
#include <iostream>
#include <string>
#include <ctime>
#include <fstream>
 
using namespace std;
 
const int N = 1000000;
 
void createfile() //создание файла для теста
{
    string str = "AAAAAAAAAA";
    ofstream fout("file1.txt");
    for (int i = 0; i < N; ++i)
    {
        fout << i + 1;
        fout << str << endl;
    }
    fout.close();
}
 
int main()
{
    //createfile(); //создание файла для теста
    
    char str1[255] = {'\0'};
    char str2[255] = {'\0'};
    char temp[255] = {'\0'};
    
    clock_t t1 = clock();
    FILE *fin = fopen("file1.txt", "rb");
    
    if (!fin) printf("Error!\n");
    else
    {
        int i = 1;
        int n = 1, m = 1000000; // номера заменяемых строк (не должны выходить за диапазон)
        while (true) 
        {
            if (i == n) 
            {
                fgets(str1, 255, fin);
                ++i;
            }
            if (i == m) 
            {
                fgets(str2, 255, fin);
                ++i;
            }
            fgets(temp, 255, fin); // предполагается, что длина строки не более 255 символов
            if (feof(fin)) break;
            ++i;
        }
        rewind(fin);
        
        printf("%d\n", i - 1);
        
        i = 0;
        char ch;
        FILE *fout = fopen("file2.txt", "wb");
        while (true)
        {
            fgets(temp, 255, fin);
            if (feof(fin)) break;
            ++i;
            if (i == n)  fputs(str2, fout);
            else if (i == m) fputs(str1, fout);
                 else  fputs(temp, fout);
        }
        
        fclose(fout);
        fclose(fin);
        
        clock_t t2 = clock();
        printf("%f\n", (t2 - t1 + .0) / CLOCKS_PER_SEC); // время отработки
    }
  
    system("pause");
    return 0;
}
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5547 / 2561 / 233
Регистрация: 01.11.2011
Сообщений: 6,330
Завершенные тесты: 1
06.09.2013, 14:45     Замена строк в текстовых документах больших размеров #4
Цитата Сообщение от gazlan Посмотреть сообщение
есть смысл предварительно построить полный индекс всех строк
А вот здесь нельзя ли по подробнее? Имеется в виду приблизительно что-то типа хеша строки? Точнее массива таких хешей? И когда будет требоваться найти какую-либо строку, надо будет эту искомую строку подвергнуть тому же самому хешированию, что и весь текст, и сравнить с ранее созданным массивом?
gazlan
2857 / 1805 / 271
Регистрация: 27.08.2010
Сообщений: 4,888
Записей в блоге: 1
06.09.2013, 16:37     Замена строк в текстовых документах больших размеров #5
Цитата Сообщение от SatanaXIII Посмотреть сообщение
подробнее
Читайте - побайтно (о буферизации побеспокоится OS, если ипользовать подходящие функции).
Первая строка начинается с 0. Вторая - за концом первой итд. Это и будет вашим индексом. Хэшировать
(пока вас не интересует содержание строки) ничего не требуется.

Для обмена двух произвольных строк выбираете из индекса их смещения. (Размер вычисляется как разность смещений со строкой со следующим порядковым номером или размером файла - для последней строки).

- Копируете начало файла до первой строки.
- Копируете вторую строку.
- Копируете все между первой и второй строкой.
- Копируете первую строку.
- Копируете все после второй строки и до конца файла.

Имеете копию файла с обменеными строками.
Yandex
Объявления
06.09.2013, 16:37     Замена строк в текстовых документах больших размеров
Ответ Создать тему
Опции темы

Текущее время: 08:37. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru