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

@VAS77 · Регистрация: 29.09.2018

Студворк — интернет-сервис помощи студентам

Привет, всем! Помогите, пожалуйста, ускорить работу алгоритма. При вводе примерно вот таких чисел:
set_size 2048
set_size 5555968309949909707681474679239964879410 98089
pop
push 9135565113072939263667946945100443718717 81413
push 8290665784011544157364734732752448795769 03152
pop
pop
push 3899094529347580946394815074405058392683 35626
pop
pop
push 1111784069636132896708799990424882372470 610535
push 1512174111137708691166236430962931101104 54401
push 9622822769940284262922960932234834730547 11193
push 8058182192795982241528647458945318494258 40725
push 1834639368728251647060186302888760644458 03957
push 7910648106719246467765649869456586406685 46771
... их здесь около 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;
}

@JaponDemon · 07.10.2018, 00:15

А вы не находите, что логика какая-то дурацкая, сначала
складывать в одну строку команду и числа, а потом зачем-то
опять их выковыривать ?
Можно же просто сделать менюшку с командами ,
если ввели set_size, то создать стек
если push, то предоставить ввод чисел
( а корректность ввода чисел кстати можно сразу обработать, а не ковыряться потом в
строке)
если print, то напечатать стек.

@schdub · 07.10.2018, 01:56

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

Новые блоги и статьи Все статьи Все блоги /
Загрузка PNG-файла с альфа-каналом с помощью библиотеки SDL3_image на Android 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .
Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом

@JaponDemon 166 / 109 / 57 Регистрация: 30.08.2018 Сообщений: 357
	07.10.2018, 00:15
	А вы не находите, что логика какая-то дурацкая, сначала складывать в одну строку команду и числа, а потом зачем-то опять их выковыривать ? Можно же просто сделать менюшку с командами , если ввели set_size, то создать стек если push, то предоставить ввод чисел ( а корректность ввода чисел кстати можно сразу обработать, а не ковыряться потом в строке) если print, то напечатать стек. 0

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

Решение