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

Быстрая сортировка содержимого больших файлов - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 5.00
TokiTori
0 / 0 / 0
Регистрация: 11.01.2011
Сообщений: 4
11.01.2011, 21:09     Быстрая сортировка содержимого больших файлов #1
Здравствуйте. Поставлена такая задача - отсортировать содержимое файла. Человек сразу сказал, что файлы могут быть больших размеров. Поэтому решил производить сортировку напрямую в файле. Собственно, алгоритм сначала написал под массив - все работало замечательно, а когда переписал под работу с файлом - перестал корректно сортировать. К примеру, исходная последовательность символов "абвгдеёжзийклмнопрстуфхцчшщъыьэюя" в файле заменяется на "абвгдёежзийклмнопрстуфхцчшщъыьэюя", что показывает некорректную работу. Сам ошибку ищу уже несколько дней, но найти так и не удалось. Работаю в wxDev-C++.
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
#include <iostream>
 
using namespace std;
 
FILE *f;
 
void doSort(long start, long end) {
    if (start>=end)
        return;
    long i=start, j=end;
    long cur=i-(i-j)/2;
    char ci,cj,ccur;
    while (i<j) {
        fseek(f,i,0);
        fread(&ci,sizeof(char),1,f);
        
        fseek(f,j,0);
        fread(&cj,sizeof(char),1,f);
        
        fseek(f,cur,0);
        fread(&ccur,sizeof(char),1,f);        
        
        while (i<cur && (ci<=ccur)) {
            i++;
        }
        while (j>cur && (ccur<=cj)) {
            j--;
        }
        
        if (i<j) {                 
            //заново читаем i-ый и j-ый символы
            fseek(f,i,0);
            fread(&ci,sizeof(char),1,f);
 
            fseek(f,j,0);
            fread(&cj,sizeof(char),1,f);
            
                
            //меняем j-ый символ на i-ый
            fseek(f,j,0);
            fwrite(&ci,sizeof(char),1,f);
            
            //меняем i-ый символ на j-ый            
            fseek(f,i,0);
            fwrite(&cj,sizeof(char),1,f);
 
            if (i==cur)
                cur=j;
            else if (j==cur)
                cur=i;
        }
    }
    doSort(start, cur);
    doSort(cur+1, end);
}
 
 
int main(int argc, char *argv[]){
    
    f = fopen("c:/1.txt", "rb+");
    if (f == 0) {
        cout<<"Can't open file";
        return 1;
    }
 
    fseek(f, 0, SEEK_END);
    long file_size = ftell(f);
    cout<<"Sorting file: "<<file_size<<" bytes."<<"\n";
 
    doSort(0,file_size-1);
    fclose(f);
    system("PAUSE");
    return EXIT_SUCCESS;
}
Заранее спасибо за помощь!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
odip
Эксперт C++
 Аватар для odip
7224 / 3286 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
12.01.2011, 09:12     Быстрая сортировка содержимого больших файлов #2
Поставлена такая задача - отсортировать содержимое файла
По-байтно отсортировать что-ли ?

Код будет медленно работать - читать и писать по одному символу весьма плохая идея.

Просто посчитай сколько у тебя каких байт.
А потом запиши их в файл.

Например если файл такой "cbbaaa"
то count[a]= 3
count[b]= 2
count[c]= 1

Потом просто пишем в файл
Сначала "aaa"
потом "bb"
потом "c"

Тогда и сортировать ничего не нужно
TokiTori
0 / 0 / 0
Регистрация: 11.01.2011
Сообщений: 4
12.01.2011, 18:14  [ТС]     Быстрая сортировка содержимого больших файлов #3
Идея отличная, но человек поставил четко задание - реализовать быструю сортировку файла. В другой ситуации принял бы сторонние идеи, но сейчас стоит вопрос - почему некорректно работает мой алгоритм?
odip
Эксперт C++
 Аватар для odip
7224 / 3286 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
12.01.2011, 19:23     Быстрая сортировка содержимого больших файлов #4
Для начала неплохо проверять каждый вызов fread(), fseek()
Если где-то будет ошибка - ты не заметишь ее
TokiTori
0 / 0 / 0
Регистрация: 11.01.2011
Сообщений: 4
13.01.2011, 12:21  [ТС]     Быстрая сортировка содержимого больших файлов #5
Ухтыжйооожыыыык!!!!!111 Как все было тривиально: в циклах начинающхся на 23 и 28 строках забыл пересчитать ci и cj... неделя времени на это ушла:
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
#include <iostream>
 
using namespace std;
 
FILE *f;
 
void doSort(long start, long end) {
    if (start>=end)
        return;
    long i=start, j=end;
    long cur=i-(i-j)/2;
    char ci,cj,ccur;
    while (i<j) {
        fseek(f,i,0);
        fread(&ci,sizeof(char),1,f);
        
        fseek(f,j,0);
        fread(&cj,sizeof(char),1,f);
        
        fseek(f,cur,0);
        fread(&ccur,sizeof(char),1,f);        
        
        while (i<cur && (ci-ccur<=0)) {
            i++;
            fseek(f,i,SEEK_SET);
            fread(&ci,sizeof(char),1,f);
        }
        while (j>cur && (ccur-cj<=0)) {
            j--;
            fseek(f,j,SEEK_SET);
            fread(&cj,sizeof(char),1,f);
        }
        
        if (i<j) {                 
            //заново читаем i-ый и j-ый символы
            fseek(f,i,0);
            fread(&ci,sizeof(char),1,f);
 
            fseek(f,j,0);
            fread(&cj,sizeof(char),1,f);
            
                
            //меняем j-ый символ на i-ый
            fseek(f,j,0);
            fwrite(&ci,sizeof(char),1,f);
            
            //меняем i-ый символ на j-ый            
            fseek(f,i,0);
            fwrite(&cj,sizeof(char),1,f);
 
            if (i==cur)
                cur=j;
            else if (j==cur)
                cur=i;
        }
    }
    doSort(start, cur);
    doSort(cur+1, end);
}
 
 
int main(int argc, char *argv[]){
    
    f = fopen("c:/1.txt", "rb+");
    if (f == 0) {
        cout<<"Can't open file";
        return 1;
    }
 
    fseek(f, 0, SEEK_END);
    long file_size = ftell(f);
    cout<<"Sorting file: "<<file_size<<" bytes."<<"\n";
 
    doSort(0,file_size-1);
    fclose(f);
    system("PAUSE");
    return EXIT_SUCCESS;
}
Добавлено через 9 часов 32 минуты
Тему можно считать закрытой.
Yandex
Объявления
13.01.2011, 12:21     Быстрая сортировка содержимого больших файлов
Ответ Создать тему
Опции темы

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