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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
DenCHS200
32 / 32 / 1
Регистрация: 07.10.2011
Сообщений: 117
#1

Убыстрение работы программы - C++

18.10.2012, 21:33. Просмотров 415. Ответов 9
Метки нет (Все метки)

Написал программу по поиску максимальной подстроки из заданных строк. Работает правильно, но нужно оптимизировать по времени выполнения(Не более секунды на обработку результатов). У кого какие соображения по убыстрению программы.
Алгоритм конечно мудрёный получился, но может как-то можно оптимизировать её работу?
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
#include <stdio.h>
#include <iostream>
 
using namespace std;
 
 
char MassivStrok[10][10000];
unsigned int temp2,temp,DlinyStrok[10];
unsigned short numberS=11; // индекс строки с самым минимальным кол-вом символов
char ch;
unsigned int limit=0;
 
char MinString[10000];
char FindSubString[10000];
 
void main()
{
 
 
unsigned int max,j,i,n,i2;  
    
 
cin>>n;
ch=getchar();
for(i=0;i<n;i++) // инициализируем массив 
DlinyStrok[i]=0;
i=j=0;
while(i<n){
    while((ch=getchar())!= '\n')
{
MassivStrok[i][j]=ch;
DlinyStrok[i]++;
j++;
}
    j=0;
    i++;
}
max=DlinyStrok[0];numberS=0;
// далее ищем минимальную по длине строку
for(i=1;i<n;i++)
if(DlinyStrok[i]<max)
{
max=DlinyStrok[i];
numberS=i;
}
 
 
 
for(i=0;i<max;i++){// передаём минимальную строку в массив
MinString[i]=MassivStrok[numberS][i];
FindSubString[i]=MassivStrok[numberS][i];}
unsigned int i1,j1;
 
bool sovpadaet1; // если совпадает текущий проверяемый символ
bool sovpadaet2=false;  // если совпало с i-той строкой
unsigned int index1;// индекс урезания строки справа
unsigned int step,index2 ; // индекс урезания слева
 
index1=index2=0;
 
 
 
 
 
 
 
 
//max3=max;
 
i1=0;
// а теперь самый смак программы, алгоритм!
while((sovpadaet2==false)&&(max>1)){// пока не довели строку до нуля
        
        
    do{
            step=0;
            
            if(i1!=numberS){// если сравнивать не с собой
                
                // находим первый совпадающий символ 
        
    
                
        
        
                j1=0;
M1:;
        while((FindSubString[0]!=MassivStrok[i1][j1])&&(j1<DlinyStrok[i1]))
        {
        j1++;
        }
        
step=0;
i=j1;
// предполагаем, что совпадает
sovpadaet1=true;
do
{
                        if(FindSubString[step]==MassivStrok[i1][i])
                {step++;
                        i++;
                                    }
                else{
                 sovpadaet1=false;
                 sovpadaet2=false;
            break;   
                    }
temp2=max-limit;
    }while(step<temp2);
if((j1<DlinyStrok[i1]-limit)&&(sovpadaet1==false))
{j1++;goto M1;}
 
//endDo-WHILE
 
// Код изменения СубСтроки
//===============================
 
if(sovpadaet1==false) // если не совпало, то делаем строку меньше или изменяем
{
    i1=0;
    if(index1==0){
        limit++;
    index2=limit;}
 
    if(limit<max){
    
        
i2=0;
    for(j=index1;j<max-index2;j++){
        FindSubString[i2]=MinString[j];
        i2++;
    
    }
        index1++;
if(index2!=0)
index2--;
        if(index1>limit)
{index1=0;
index2=limit+1;
}
}
 
}
 
            
 
    
 
        
// Конец изменения субстроки
else // если же строка совпала, то переходим на следующую строку и
// сообщаем о совпадении 
{
sovpadaet2=true;
i1++;
}
            }// endIF
 else{ // в противном случае переходим к следующей строке
i1++;
}
 temp=max-limit;
        }while((i1<n)&&(temp>1));
            
}
        if(sovpadaet2==true){
        for(i=0;i<max-limit;i++)// выводим полученную подстроку
            cout<<FindSubString[i];}
getchar();
    
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MrGrig
176 / 159 / 2
Регистрация: 08.10.2012
Сообщений: 422
18.10.2012, 21:48     Убыстрение работы программы #2
вы хоть какие нибудь диалоговые сообщения выводите. или хотя бы пример сделайте что дано и что получится после. А то выполнение начинается, мигает курсор, вводишь строку какую то, энтер и вылетает сразу прэсэникей =/

Добавлено через 8 минут
почитал повнимательнее код, ввел цифру 5
но почему то строк ввел 6
сразу оптимизация, правда не решения

вместо
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(i=0;i<n;i++) // инициализируем массив 
DlinyStrok[i]=0;
//...///
 
while(i<n){
    while((ch=getchar())!= '\n')
{
MassivStrok[i][j]=ch;
DlinyStrok[i]++;
j++;
}
    j=0;
    i++;
}
это
C++
1
2
3
4
5
6
7
8
9
10
11
while(i<n){
    DlinyStrok[i]=0;
    while((ch=getchar())!= '\n')
{
MassivStrok[i][j]=ch;
DlinyStrok[i]++;
j++;
}
    j=0;
    i++;
}
DenCHS200
32 / 32 / 1
Регистрация: 07.10.2011
Сообщений: 117
18.10.2012, 21:54  [ТС]     Убыстрение работы программы #3
Пардон. Первый параметр - количество вводимых строк (максимально 10), затем идёт посимольный ввод строк(максимальное количество элементов 10 000), ввод строки завершается клавишей Enter. Пример

3
myarchive
its_not_my_archive
thisarcisarchive

Выведено будет archive

Добавлено через 5 минут
Странно, что 6 строк .У меня если ввёл пять, то пять только можно внести.Может вы шестую посчитали, которая выводится в конце?
MrGrig
176 / 159 / 2
Регистрация: 08.10.2012
Сообщений: 422
18.10.2012, 21:56     Убыстрение работы программы #4
наличие в программе гоуту сильно напрягает, завтра с утречка попробую написать с нуля использую ваши комментарии. Есть правда пару вопросиков. Есть ли ограничения какиенибудь косаемо программы? например не запрещается ли использовать вместо двумерного чаровского массива одномерный стринговый? или какие либо обязательное присутствие/отсутствие каких либо функций в программе?

Добавлено через 30 секунд
Цитата Сообщение от DenCHS200 Посмотреть сообщение
транно, что 6 строк .У меня если ввёл пять, то пять только можно внести.Может вы шестую посчитали, которая выводится в конце?
вполне возможно сейчас проверю
DenCHS200
32 / 32 / 1
Регистрация: 07.10.2011
Сообщений: 117
18.10.2012, 22:07  [ТС]     Убыстрение работы программы #5
Ну разве что Api функции не использовать, так как код под Linux у меня код будет работать.А так никаких ограничений, только если массив string делать, то ведь по умолчанию длина одной строки 256 символов, а ,задавая длину принудительно (10 000 символов), у меня компилятор ругаться начинал, поэтому на char всё делал, но если будет решение с использованием string то был бы рад посмотреть, как правильно его задать.Я завтра из универа приеду, допишу комментариев побольше, чтобы проще было, заранее спасибо!

Добавлено через 6 минут
C++
1
goto M1;
поставил один раз, управление от него передаётся назад(согласен, стиль программирования не очень ).Его суть (
C++
1
goto
)заключается в том, чтобы дальше продолжить проверку подстроки на совпадение с j1-ым символом(Проверка в цикле while, над которым стоит эта метка M1 )
MrGrig
176 / 159 / 2
Регистрация: 08.10.2012
Сообщений: 422
19.10.2012, 13:41     Убыстрение работы программы #6
2 комментария добавлю.
чтобы проверить работоспособность программы сделал ввод не ручной, а рандомно записываю цифры ровно 9999 и последний 0 байт на все 10 строк. т.е полностью забил массивы.
так вот 1е программа думает доли секунды,
2е результат не выводится, хотя в 9999 символах в 10 строках есть хотябы одно которое длиною даже 3-4 символов... где то есть косячок

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

Добавлено через 14 часов 52 минуты
я придумал алгоритм на основе рекурсивного вызова следующей строки. в функцию будет передаваться субстрока и индификатор строки в которой нужно искать(порядковый номер).
соответвтвенно если субстрока будет найдена, функция будет вызвана рекурсивно с порядковым номером уже следующей строки. всего таких вызовов может быть н-1 где н количество строк. а всего циклов вот я высчитать пока что не могу. нужно составить алгоритм вычисления к примеру:
если строка длинной 2 то циклов будет 3, где 2 цикла по 1й букве
если строка длинной 3 то циклов будет 6, где 3 цикла по 1й букве
если строка длинной 4 то циклов будет 3, где 4 цикла по 1й букве
если строка длинной 5 то циклов будет 15, где 5 циклов по 1й букве
если строка длинной 6 то циклов будет 20, где 6 циклов по 1й букве
и т.д.... если поможете посчитать количество циклов,то напишу полную реализацию быстрее =)
Герц
523 / 340 / 4
Регистрация: 05.11.2010
Сообщений: 1,077
Записей в блоге: 1
19.10.2012, 13:52     Убыстрение работы программы #7
Максимальная общая подстрока? В текущем виде - никак не убыстрить (асимптотика не изменится), изучайте алгоритм Ахо-Корасика (построение суффиксного дерева), он даст асимптотику O(n).
DenCHS200
32 / 32 / 1
Регистрация: 07.10.2011
Сообщений: 117
19.10.2012, 19:24  [ТС]     Убыстрение работы программы #8
MrGrid , думаю, рекурсия только усугубит положение, так как она проста в реализации, но требует больше ресурсов.Вроде ваш алгоритм побыстрее, но рекурсия всё может свести на нет, но всё равно спасибо за совет!

Герц Спасибо за совет, буду копать в этом направлении.

Но тут задумался над вводом информации, может торможение вызывает сам ввод в программу, может getchar() да ещё и в цикле тормозит?
Герц
523 / 340 / 4
Регистрация: 05.11.2010
Сообщений: 1,077
Записей в блоге: 1
19.10.2012, 20:03     Убыстрение работы программы #9
Твой алгоритм почти на 100% (я не смотрел код) имеет сложность O(n^3), а то и все O(n^4). Ты не выведешь его из этого временного класса, экономя на getchar'ах и прочих операциях.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.10.2012, 20:47     Убыстрение работы программы
Еще ссылки по теме:

C++ Принцип работы программы
C++ Описание работы программы
Скрин работы программы C++
Составить программы работы с файлами C++

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

Или воспользуйтесь поиском по форуму:
DenCHS200
32 / 32 / 1
Регистрация: 07.10.2011
Сообщений: 117
19.10.2012, 20:47  [ТС]     Убыстрение работы программы #10
Всем спасибо, буду переделывать по Ахо Корасику
Yandex
Объявления
19.10.2012, 20:47     Убыстрение работы программы
Ответ Создать тему
Опции темы

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