C++

Forum

 
The finished code needs an explanation

sergeyutkin221 (21)
Hello everyone, I have a code that matches the following assignment:

1) Count the number of occurrences of the prog message line in two ways: using an iterative algorithm and using a recursion.

2) Increasing the number of elements (recursion depth), get a stack overflow.

3) Determine the execution time of the iterative algorithm and using recursion for the number of items 100, 5000 and for n, close to Stack Overflow

I have a ready code for that (I need your help to figure out this code, I was given it, and I need to understand what is responsible for what, I would be grateful if you could comment on the code approximately partially, at least to a minimum):

#include <iostream>
#include <cstring>
#include <ctime>
#include <chrono>
using namespace std;

void functionIteration(char array[], const int size, int countProg);
void functionRecurcy(char array[], const int size, int countProg, int& k, int i = 0, int j = 0, int index = 0);

int main() {
srand(time(NULL));

int size, k = 0, j = 0, i = 0, index = 0;
string str = "prog";

while (true){
cout << "Insert the size: ";
cin >> size;

if (!cin or size <= 0) {
cin.clear();
cin.ignore(10000, '\n');
}
else
break;
}

int countProg = 1 + rand() % 10;
char array[5000];

while (k != countProg) {
while (j != 4){
array[i] = str[j];
i++;
j++;
}
j = 0;
k++;
}

for (; i < size; i++)
array[i] = (char)i;

functionIteration(array, size, countProg);
k = i = j = index = 0;

auto start = chrono::high_resolution_clock::now();

functionRecurcy(array, size, countProg, k, 0, 0, 0);
cout << "\n[RECYRCY]Count = " << countProg << " K = " << k << endl;

auto end = chrono::high_resolution_clock::now();
chrono::duration<double> duretion = end - start;
cout << "Duration: " << duretion.count() << "s" << endl;
return 0;
}

void functionIteration(char array[], const int size, int countProg){
auto start = chrono::high_resolution_clock::now();

string str = "prog";
int j = 0, i = 0;
int k = 0;


j = 0;
int index = 0;
for (int i = 0; i < size; ){
if (array[i] == str[0]) {

while (index != 4){
if (array[i] == str[j])
j++;

i++;
index++;
}
if (j == 4)
k++;
j = 0;
index = 0;
}
else
i++;
}
auto end = chrono::high_resolution_clock::now();

chrono::duration<double> duretion = end - start;
cout << "Duration: " << duretion.count() << "s" << endl;
cout << "Count prog = " << countProg << "\tK = " << k << endl;
}

void functionRecurcy(char array[], const int size, int countProg, int& k, int i, int j, int index){
string str = "prog";

if (array[i] == str[0]) {

while (index != 4){
if (array[i] == str[j])
j++;

i++;
index++;
}
}
else
i++;

if (j == 4) {
k++;
j = 0;
index = 0;
}

if (i == size) {
return;
}
functionRecurcy(array, size, countProg, k, i++, j++, index++);

}
kbw (9488)
I would be grateful if you could comment on the code
I've done this many times over the years. It's a thankless task.

However; if there's some particular construct you don't understand, please ask.
seeplus (6592)
Use code tags so that the code is at least readable!

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
 
#include <iostream>
#include <cstring>
#include <ctime>
#include <chrono>
using namespace std;

void functionIteration(char array[], const int size, int countProg);
void functionRecurcy(char array[], const int size, int countProg, int& k, int i = 0, int j = 0, int index = 0);

int main() {
	srand(time(NULL));

	int size, k = 0, j = 0, i = 0, index = 0;
	string str = "prog";

	while (true) {
		cout << "Insert the size: ";
		cin >> size;

		if (!cin or size <= 0) {
			cin.clear();
			cin.ignore(10000, '\n');
		} else
			break;
	}

	int countProg = 1 + rand() % 10;
	char array[5000];

	while (k != countProg) {
		while (j != 4) {
			array[i] = str[j];
			i++;
			j++;
		}

		j = 0;
		k++;
	}

	for (; i < size; i++)
		array[i] = (char)i;

	functionIteration(array, size, countProg);
	k = i = j = index = 0;

	auto start = chrono::high_resolution_clock::now();

	functionRecurcy(array, size, countProg, k, 0, 0, 0);
	cout << "\n[RECYRCY]Count = " << countProg << " K = " << k << endl;

	auto end = chrono::high_resolution_clock::now();
	chrono::duration<double> duretion = end - start;

	cout << "Duration: " << duretion.count() << "s" << endl;
	return 0;
}

void functionIteration(char array[], const int size, int countProg) {
	auto start = chrono::high_resolution_clock::now();
	string str = "prog";
	int j = 0, i = 0;
	int k = 0;

	j = 0;

	int index = 0;

	for (int i = 0; i < size; ) {
		if (array[i] == str[0]) {
			while (index != 4) {
				if (array[i] == str[j])
					j++;

				i++;
				index++;
			}

			if (j == 4)
				k++;

			j = 0;
			index = 0;
		} else
			i++;
	}

	auto end = chrono::high_resolution_clock::now();
	chrono::duration<double> duretion = end - start;

	cout << "Duration: " << duretion.count() << "s" << endl;
	cout << "Count prog = " << countProg << "\tK = " << k << endl;
}

void functionRecurcy(char array[], const int size, int countProg, int& k, int i, int j, int index) {
	string str = "prog";

	if (array[i] == str[0]) {
		while (index != 4) {
			if (array[i] == str[j])
				j++;

			i++;
			index++;
		}
	} else
		i++;

	if (j == 4) {
		k++;
		j = 0;
		index = 0;
	}

	if (i == size) {
		return;
	}

	functionRecurcy(array, size, countProg, k, i++, j++, index++);
}

jonnin (11437)
its all over the place. using namespace std has many threads on why not to do it.
you use chrono, but are still stuck with C's random instead of <random> ?!
its using tail recursion, which 'usually' ends up being turned into a loop by the compiler, but you are tasked to find when the stack will blow out? It probably won't; your limitation on stack is probably just how big you make the array, and on 64 bit, that is a hefty size.

This is an oddly specific block of code to be 'given' without comments. Did you happen to pay someone to do your homework or something here? Or 'borrow' off a classmate? It feels like commenting it would just be enabling you, which I try very hard to avoid. But do pay attention to my hints above... if you can't blow out the stack, the reason is the type of recursion you used, rewrite it to do the recursion first if you want to test that. And modern machines have a big stack size, don't expect a blowout with just a few thousand.
seeplus (6592)
Well on my computer, recursion bombs at 369!

seeplus (6592)
As a first refactor, possibly consider:

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
 
#include <iostream>
#include <ctime>
#include <chrono>
#include <limits>
#include <string>

const std::string sfnd {"prog"};

template<typename T = int>
auto getNum(const std::string& prm)
{
	const auto notsp {[&]() {while (std::isspace(static_cast<unsigned char>(std::cin.peek())) && std::cin.peek() != '\n') std::cin.ignore(); return std::cin.peek() != '\n'; }};
	T n {};

	while ((std::cout << prm) && (!(std::cin >> n) || notsp())) {
		std::cout << "Not a number\n";
		std::cin.clear();
		std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
	}

	std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
	return n;
}

auto functionIteration(const char array[], const size_t size, size_t& fnd) {
	const auto start {std::chrono::high_resolution_clock::now()};

	fnd = 0;

	for (const char* parr {array}, *pend = array + size; parr < pend; parr += sfnd.size())
		fnd += std::memcmp(parr, sfnd.data(), sfnd.size()) == 0;

	const auto end {std::chrono::high_resolution_clock::now()};

	return end - start;
}

void functionRecursive(const char array[], const size_t size, size_t& fnd, const char* parr = nullptr) {
	if (parr == nullptr) {
		parr = array;
		fnd = 0;
	}

	if (parr > array + size)
		return;

	fnd += std::memcmp(parr, sfnd.data(), sfnd.size()) == 0;
	functionRecursive(array, size, fnd, parr + sfnd.size());
}

int main() {
	constexpr size_t MaxArr {5000};

	srand(static_cast<unsigned>(time(nullptr)));

	size_t size {};

	do {
		size = getNum<unsigned>("Enter the size (max " + std::to_string(MaxArr / sfnd.size()) + "): ");
	} while (size > MaxArr / sfnd.size() && (std::cout << "Maximum size is " << MaxArr / sfnd.size() << '\n'));

	const size_t countProg = 1 + rand() % 10;
	char array[MaxArr] {};

	for (char *parr {array}, *pend {array + countProg * sfnd.size()}; parr < pend; parr += sfnd.size())
		memcpy(parr, sfnd.data(), sfnd.size());

	size_t fnd1 {};
	const auto dur1 {functionIteration(array, size, fnd1)};

	std::cout << "Iteration found " << fnd1 << " in " << std::chrono::duration<double, std::micro>(dur1).count() << " micro sec\n";

	size_t fnd2 {};
	const auto start {std::chrono::high_resolution_clock::now()};

	functionRecursive(array, size, fnd2);

	const auto end {std::chrono::high_resolution_clock::now()};

	std::cout << "Recursive found " << fnd2 << " in " << std::chrono::duration<double, std::micro>(end - start).count() << " micro sec\n";
}



Enter the size (max 1250): 1250
Iteration found 9 in 4.346 micro sec
Recursive found 9 in 5.532 micro sec

Last edited on
Topic archived. No new replies allowed.