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

Найти ошибку в реализации алгоритма n - путевого слияния - C++

Восстановить пароль Регистрация
 
PG94
2 / 2 / 0
Регистрация: 15.01.2012
Сообщений: 181
21.06.2013, 10:16     Найти ошибку в реализации алгоритма n - путевого слияния #1
Доброе утро.
Нужно реализовать алгоритм n - путевого слияния (n - аргумент функции). Некоторые операции проходят неверно, причём вычислить ошибку никак не удаётся (подробности ниже). Вот код:
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
namespace MultiMerge {
 
const int empty=0x80000000;
 
struct Buffer {
    //буфер для работы с ключами
    Buffer():prev(empty),curr(empty) { };
 
    int prev;
    int curr;
};
 
void create_files(vector<string>& fnames, int n)
{
    //создание списка имён вспомогательных файлов
    string templ="_File_for_MultiMerge";
    for (int i=0; i<2*n; ++i)
        fnames.push_back(templ+to_string(i));
 
    //создание самих файлов
    ofstream ofs;
    for (int i=0; i<2*n; ++i) {
        ofs.open(fnames[i]);
        ofs.close();
    }
}   
 
int split(const string& source, vector<string>& workfiles, int n)
{
    //распределение элементов из исходного файла, 
    //возвращается кол-во возрастающих серий в source
 
    ifstream ifs(source);   
    if (!ifs) throw runtime_error("split: can't open source file");
 
    vector<ofstream> vofs(n);       
    for (int i=0; i<n; ++i) {
        vofs[i].open(workfiles[i]);
        if (!vofs[i]) throw runtime_error("split: can't open one of auxiliary file");
    }
 
    int series(0);                          
    int write_num(0);                       //номер вспомогательного файла, в который идёт запись
    int buffer1(empty), buffer2(empty);     //буферы для чтения ключей и определения границ серий
    while (true) {
        if (buffer2==empty && !(ifs>>buffer2)) {
            ++series;
            break;
        }
        if (buffer2>=buffer1) {
            vofs[write_num]<<buffer2<<" ";
            buffer1=buffer2;
            buffer2=empty;
        }
        else {                              //конец очередной серии
            ++series;
            write_num=(write_num+1)%n;
            buffer1=empty;                  //начало новой серии, условие (buffer2>=buffer1)==true
        }
    }
 
    return series;
}
 
void sort(const string& source, int n)
{
    //source - исходный файл, n - путевое слияние
    if (n<2) throw runtime_error("sort: not enough auxiliary files for sorting");
 
    vector<string> fnames;
    create_files(fnames,n);
    int series=split(source,fnames,n);  //кол-во серий на каждом очередном этапе
 
    vector<int> table_dir(2*n);         //таблица, первые n значений - индексы сливаемых файлов
    for (int i=0; i<2*n; ++i)
        table_dir[i]=i;
 
    vector<int> table_from(n);          //таблица для отслеживания окончания серий и окончания данных в сливаемых файлах
    vector<Buffer> v_buf(2*n);          //вектор буферов для каждого файла, из которого на данном этапе сливаются ключи
    while (series>1) {
 
        int cnt1(n), cnt2(n);           //число непустых файлов; число файлов, в которых текущая серия ещё не закончилась
        if (series<n) 
            cnt1=cnt2=series;
 
        int file_for_write=n;               //table_dir[file_for_write] - индекс файла, в который идёт запись
        series=0;
 
        for (int i=0; i<n; ++i) {
            table_from[i]=table_dir[i];         //подготовка таблицы
            v_buf[table_from[i]].prev=empty;    //подготовка буферов (1)
        }
        
        vector<fstream> v_fs(2*n);              //подготовка файлов
        for (int i=0; i<2*n; ++i) {
            v_fs[i].open(fnames[table_dir[i]]); 
            if (!v_fs[i]) throw runtime_error("sort: can't open one of auxiliary files during merge stage");
        }
        
        for (int i=0; i<cnt1; ++i)
            v_fs[table_from[i]]>>v_buf[table_from[i]].curr; //подготовка буферов (2)
 
        cout<<"Buffers before merge: ";
        for (int i=0; i<table_from.size(); ++i)
            cout<<v_buf[table_from[i]].curr<<", ";
        cout<<endl;
        while (cnt1) {
    
            //поиск минимума
            int nmin(0);
            for (int i=0; i<cnt2; ++i) {
                if (v_buf[table_from[i]].curr<v_buf[table_from[nmin]].curr) nmin=i;
            }
            cout<<"min="<<v_buf[table_from[nmin]].curr<<endl;
 
            //запись минимума
            v_fs[table_dir[file_for_write]]<<v_buf[table_from[nmin]].curr<<" ";
            v_buf[table_from[nmin]].prev=v_buf[table_from[nmin]].curr;
 
            //работа с буфером, проверки на конец серии и конец файла
            if (!(v_fs[table_from[nmin]]>>v_buf[table_from[nmin]].curr)) {
                --cnt1;
                --cnt2;
                swap(table_from[nmin],table_from[cnt1]);
                swap(table_from[nmin],table_from[cnt2]);
            } else if (v_buf[table_from[nmin]].curr < v_buf[table_from[nmin]].prev) {
                --cnt2;
                swap(table_from[nmin],table_from[cnt2]);
            }
            cout<<"cnt1 == "<<cnt1<<", cnt2 == "<<cnt2<<endl;
            cout<<"Buffers: ";
            for (int i=0; i<table_from.size(); ++i)
                cout<<v_buf[table_from[i]].curr<<", ";
            cout<<endl<<endl;
 
            //проверка на конец серий в каждом файле
            if (cnt2==0) {
                ++series; //неправльная работа с сериями (условие!)
                cnt2=cnt1;
                if (file_for_write<2*n-1)   //меняем файл для записи
                    ++file_for_write;
                else
                    file_for_write=n;
            }
 
        }
        cout<<"series=="<<series<<endl;
        cout<<"-------------------------------------------------"<<endl;
        
        //подготовка к следующему слиянию: блоки из n файлов меняются ролями
        for (int i=0; i<n; ++i)
            swap(table_dir[i],table_dir[i+n]);
        system("pause");
    }
 
    //результат должен  в v_fs[table_dir[0]]
    //перенос результата в исходный файл
    /*ifstream ifs(fnames[table_dir[0]]);
    ofstream ofs(source);
    if (!ifs || !ofs) throw runtime_error("sort: can't return result in source file");
    int buffer;
    while (ifs>>buffer)
        ofs<<buffer<<" ";*/
 
    /*удаление вспомогательных файлов*/
    /*for (int i=0; i<fnames.size(); ++i)
        remove(fnames[i].c_str());*/
}
 
}
Функции split и create_files отлажены. Тестировал на последовательности 10, 9, 8, 7, 6, 5, 4, 3, 2 (сортировать нужно по возрастанию), первый этап проходит верно: series == 3, получаем последовательности 8,9,10 | 5,6,7 | 2, 3, 4. Однако на следующем шаге перед началом слияния в буферы снова попадают 10,9,8 вместо 8,5,2 => зацикливание.
Подскажите:
1) В чём же проблема?
2) Можно ли как-то упростить код, нет ли в моё варианте слишком большого кол-ва ненужных операций?
Спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.06.2013, 10:16     Найти ошибку в реализации алгоритма n - путевого слияния
Посмотрите здесь:

Отделение интерфейса от реализации класса: компиляция кода реализации C++
C++ Написать функции рекурсивной и не рекурсивной реализации алгоритма Евклида нахождения наибольшего общего делителя (НОД) двух натуральных чисел
Нужне совет по реализации алгоритма C++
Где можно найти код реализации библиотеки STL C++
C++ Подскажите ошибку в реализации алгоритма Хаффмана
Сравнение рекурсивного параллелизма и последовательной рекурсивной программы для реализации алгоритма быстрой C++
Написать программу для реализации алгоритма сортировки методом пирамиды C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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