Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/6: Рейтинг темы: голосов - 6, средняя оценка - 4.50
0 / 0 / 0
Регистрация: 29.09.2018
Сообщений: 32
1

Ускорение алгоритма

06.10.2018, 21:27. Показов 1153. Ответов 2
Метки нет (Все метки)

Привет, всем! Помогите, пожалуйста, ускорить работу алгоритма. При вводе примерно вот таких чисел:
set_size 2048
set_size 555596830994990970768147467923996487941098089
pop
push 913556511307293926366794694510044371871781413
push 829066578401154415736473473275244879576903152
pop
pop
push 389909452934758094639481507440505839268335626
pop
pop
push 1111784069636132896708799990424882372470610535
push 151217411113770869116623643096293110110454401
push 962282276994028426292296093223483473054711193
push 805818219279598224152864745894531849425840725
push 183463936872825164706018630288876064445803957
push 791064810671924646776564986945658640668546771
... их здесь около 2000.
Алгоритм работает больше 3сек. (set_size - размер стека задаётся один раз при входе в программу.)
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
#include<iostream>
#include<string>
#include<regex>
#include<deque>
 
class stack
{
    size_t set_size = 0;
    unsigned int count = 0;
    std::deque<std::string> deq;
public:
    stack(size_t N);
    void push(std::string X);
    void pop();
    void print();
};
 
stack::stack(size_t N)
{
    set_size = N;
}
 
 
 
void stack::push(std::string X)
{
    if (count < set_size)
    {
        deq.push_front(X);
        count++;
    }
    else
        std::cout << "overflow" << std::endl;
}
 
void stack::pop()
{
    if (count != 0)
    {
        std::cout << deq[0] << std::endl;
        deq.pop_front();
        count--;
    }
    else
        std::cout << "underflow" << std::endl;
}
 
void stack::print()
{
    if (count != 0)
    {
        for (std::deque<std::string>::size_type i = count; i != 0; )
        {
            if (i == 1)
                std::cout << deq[--i];
            else
                std::cout << deq[--i] << ' ';
        }
        std::cout << std::endl;
    }
    else
        std::cout << "empty" << std::endl;
}
 
 
 
int main()
{
 
    unsigned int pos = 0;
    size_t num = 0;
    std::string s = "", temp="";
    std::regex reg{ "[^0-9]" };
 
    do
    {
        std::getline(std::cin, s);
        if (s != "")
        {
            if (s.substr(0,8)=="set_size")
            {
                s = std::regex_replace(s, reg, "");
                if (s.find_first_of("0123456789") != std::string::npos)
                {
                    num = atoi(s.c_str());
                }
                else
                    std::cout << "error" << std::endl;
            }
            else
            {
                std::cout << "error" << std::endl;
            }
        }
        else
            pos++;
 
    } while (num <= 0 && pos <= 15);
    stack st(num);
 
 
    do
    {
        std::getline(std::cin, s);
 
        if (s != "")
        {
            if (s == "pop")
            {
                st.pop();
                continue;
            }
 
            if (s == "print")
            {
                st.print();
                continue;
            }
 
            if (s.substr(0,4)=="push")
            {
                s.erase(0, 5);
                temp = s;
                s = std::regex_replace(s, reg, "a");
                
                if (temp!=s)
                {
                    std::cout << "error" << std::endl;
                    continue;
                }
                else
                {
                    st.push(s);
                    continue;
                }
 
            }
            std::cout << "error" << std::endl;
 
        }
        else
        {
            pos++;
        }
 
    } while (pos <= 15);
    
 
    return 0;
}
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.10.2018, 21:27
Ответы с готовыми решениями:

Ускорение алгоритма
Я хочу реализовать свой метод компрессии данных (не спрашивайте зачем, оч. надо). Он заключается в...

Ускорение алгоритма перебора
Здравствуйте! В общем есть такая задачка: Имеются N(1 ≤ N ≤ 18) камней с массами W1, W2 ,...

Ускорение
Здраствуйте, есть код: #include &lt;stdio.h&gt; #define MAX 1000010 long long h; int i, n,...

Реализуйте на практике 2 алгоритма поиска и 2 алгоритма сортировки. Результаты сравните
Всем привет! Я в С++ абсолютный чайнег, поэтому за дебильные вопросы сапогами не пинайте))) в...

2
165 / 108 / 57
Регистрация: 30.08.2018
Сообщений: 357
07.10.2018, 00:15 2
А вы не находите, что логика какая-то дурацкая, сначала
складывать в одну строку команду и числа, а потом зачем-то
опять их выковыривать ?
Можно же просто сделать менюшку с командами ,
если ввели set_size, то создать стек
если push, то предоставить ввод чисел
( а корректность ввода чисел кстати можно сразу обработать, а не ковыряться потом в
строке)
если print, то напечатать стек.
0
Эксперт С++
3058 / 1400 / 421
Регистрация: 19.01.2009
Сообщений: 3,771
07.10.2018, 01:56 3
Лучший ответ Сообщение было отмечено VAS77 как решение

Решение

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

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
// ...
#include <algorithm>
#include <cctype>
#include "benchmark.hpp"
// ...
 
// старая версия обработки строк push
void handlePushOld(std::string s) {
    std::string temp="";
    std::regex reg{ "[^0-9]" };
    stack st(2048);
 
    {
    OP_BENCHMARK; // см. benchmark.hpp
 
    if (s.substr(0,4)=="push") // на этом этапе можно избавиться от создания подстроки
    {
        s.erase(0, 5);                       // удалением первых 5 символов в строке из-за чего оставшиеся
                                             //  символы будут перемещены - нужно избавиться;
        temp = s;                            // создание копии строки - нужно избавиться;
        s = std::regex_replace(s, reg, "a"); // поиск не числовых символов и замена их на символ 'a'
                                             //  это можно реализовать оптимальнее - простой проверкой есть
                                             //  ли среди символов строки нечисловые символы;
        if (temp!=s)                         // сравнение строк - нужно избавиться;
        {
            std::cout << "error" << std::endl;
        }
        else
        {
            st.push(s);
        }
    }
    }
}
 
// новая версия
void handlePushNew(const std::string & s) {
    stack st(2048);
    {
    OP_BENCHMARK;
 
    if (s.compare(0, 4, "push") == 0) {
        if (std::all_of(ss.begin()+5, ss.end(), ::isdigit)) {
            st.push(s.substr(5));
        } else {
            std::cout << "error" << std::endl;
        }
    }
    }
}
 
int main() {
    // тестовые данные
    const char * data[] = {
    "push 1111784069636132896708799990424882372470610535",
    "push 151217411113770869116623643096293110110454401",
    "push 962282276994028426292296093223483473054711193",
    "push 805818219279598224152864745894531849425840725",
    "push 183463936872825164706018630288876064445803957",
    "push 791064810671924646776564986945658640668546771",
    "push 79106481067192464677656986945658640668546771DAAAAA",
    nullptr
    };
 
    // запустим тесты для новой версии
    for (const char ** p = data; *p; handlePushNew(*p++));
 
    // запустим тесты для старой версии
    for (const char ** p = data; *p; handlePushOld(*p++));
 
    return 0;
}
benchmark.hpp
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
#include <chrono>
 
namespace op {
 
class benchmark {
private:
    const char * m;
    std::chrono::high_resolution_clock::time_point t1, t2;
public:
    explicit benchmark(const char* msg=nullptr) : m(msg) {
        start();
    }
    ~benchmark() {
        stop();
        if (m) std::cout << m << " ";
        std::cout << msec_elapsed() << std::endl;
    }
    inline void start() {
        t1 = std::chrono::high_resolution_clock::now();
    }
    inline void stop() {
        t2 = std::chrono::high_resolution_clock::now();
    }
    inline unsigned msec_elapsed() {
        return std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count();
    }
};
 
#define OP_BENCHMARK op::benchmark __op_bench##COUNTER(__FUNCTION__)
 
};


вывод
Bash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
handlePushNew 6
handlePushNew 1
handlePushNew 1
handlePushNew 1
handlePushNew 1
handlePushNew 1
error
handlePushNew 4
handlePushOld 27
handlePushOld 20
handlePushOld 19
handlePushOld 20
handlePushOld 19
handlePushOld 20
error
handlePushOld 35
2
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.10.2018, 01:56

Ускорение алгоритма поиска символов
Добрый вечер, проблема следующая: необходимо подсчитать сколько раз в тексте встречаются буквы...

Скорость, касательное ускорение, полное ускорение, нормальное ускорение и радиус кривизны траектории
Движение точки задано координатным способом. Найти траекторию и начертить ее. Кроме того определить...

"Автоматические друзья" ускорение алгоритма поиска
Решал задание на Яндекс.Контест и возникла проблема,отправляю задание в систему и оно проходит...

Directx 11: недоступны функции Ускорение DirectDraw, Direct3D, Ускорение текстур AGP
Здравствуйте. Вся проблема как я понял в том, что у меня не правильно работает Directx. Я никак не...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.