How to count lines of cout?

[Alex009988]

Hello. I want to count lines of matrix.
Here is my code.

#include "stdafx.h"
#include <cstdlib>
#include <vector>
#include <iostream>
#include <iterator>
using namespace std;
void print(std::vector<int>& a) {
	ostream_iterator<int> i(cout, " ");
	copy(a.begin(), a.end(), i);
	cout << "\n";
}

void recurse(std::vector<int>& a, int pos, int remaining) {
	if (remaining == 0) { print(a); return; }
	if (pos == a.size()) { return; }
	for (int i = remaining; i >= 0; --i) {
		a[pos] = i;
		recurse(a, pos + 1, remaining - i);
	}
}

int main() {
	int v=2 , k, z;
    k=v;
	z = v + 1;
	vector<int> a(k);
	for (v = -1; v < z; v++) {
		recurse(a, 0, v);
	}
	system("pause\n");
	return 0;
}

I want to get output comething like that

1: 0 0
2: 1 0
3: 0 1
4: 2 0
5: 1 1
6: 0 2

The problem is that I do cycle "for" for a void function.
In order to add left line I think I need the otrher cycle inside void finction or ...? So I need some help with that. Thank you.

[JLBorges]

static int counter = 0 ;

void print(std::vector<int>& a) {

    std::cout << ++counter << ": " ;
    
    ostream_iterator<int> i(cout, " ");
    copy(a.begin(), a.end(), i);
    cout << '\n' ;
}

[Alex009988]

Thank you! One theoritical question.
I want to know the size of matrix when v equals 14. And it should include around 40-45 millions of lines. I've done the same thing with Wolfram Mathematica. But my 8gb ram was not enough to deal with that. I've found the answer with mathematica almost at the speed of light (a couple of seconds for v=13). But when v=14 it only freezes hard my PC. So as I cant to do it with WM, I've tried to build my own program with c++. But the problem is that console program works really really slow.
I need 2.5-3 days 68 hours, if my calculations right, to find the answer for v=14.
So the questions is, can make the prosess a bit faster?
Maybe I should use the other algorimn or cout only counter to make it faster.
Thanks in advance.

[jonnin]

you are using an O(n*n*n) algorithm to populate the a array ... a loop in main, a loop in recurse, and the recursion itself which is also a loop of sorts.

Perhaps there is a way to do this with less work, somehow?

However, the trouble is your print statement. Printing millions of lines takes forever on a console program. Try it... comment out your call to print in the function, and run it... I did this and it took less than 2 seconds for v=14.

and finally, try it with the print statement in the code, and redirect the output to a file (in your console, start the program normally and add this: >filename to the end of the command). This still takes quite some time, but its reasonable for the gigabytes of output you asked it to generate. I have a decent laptop, and its taken about 10 min redirected to a file. File was 1.1GB in size.

This is a lesson you never forget lol, first month out of school on the job I had an engineer ask me to speed up his program, which had like 500 lines of print statements on what loop it was in and what it was doing. I took all that crap out and it ran instantly (it was taking 2 days per with it in). Naturally, he put the prints back in, sigh.

it is notably faster (well, a few%... 15, 20% faster roughly, I didnt precise time it) if you just keep it dumb -- set a static constant variable to a.size the first time in print. It may be just as good to make your iterator static (?).

void print(std::vector<int>& a) {
	static int i;
	static int j = a.size();
	for(i = 0; i < j; i++)
	  cout<< a[i] << " ";
	//ostream_iterator<int> i(cout, " ");
	//copy(a.begin(), a.end(), i);
	cout << "\n";
}

[Alex009988]

Huge thanks for your answer.

void print(std::vector<int>& a) {
	ofstream myfile;
	myfile.open("example.txt");
	myfile << ++counter << ": ";
	myfile.close();
	//ostream_iterator<int> i(cout, " ");
	//copy(a.begin(), a.end(), i);
	//cout << '\n';
}

This makes the program 90% faster. So it needs 7 hours to find the answer for v=14.
Maybe it's better to output only last counter, but I cant figure out how to modify cout in this case. I need some help with that.

[jonnin]

ok, you are doing something weird.
I was able to print every single row of 14 in about 10 min (to a file, not the console) … which is a long, long way from 7 hours even given that your machine may be a little dated.

did you compile it in release / optimized mode?

Again, I did only 2 things here... I took the print out entirely, and that ran literally in 2 or 3 seconds flat. And I redirected it to a file twice, once with your print routine and once with mine. That was 10 min and 7 min, approximate.

if you only want the last row..
I think, but you can check it, that you get it with this

main...
}
print(a); // <------ put it here? and take the other one out?
system("pause\n");

[Alex009988]

Thank you for your reply.
I've compiled the progrm as x86 release with Visio 2017 for the last version of Windows 10.
As for me, It also takes around 2-3 seconds to run the program without print function.
I've rechecked the program's run with my code correction, I have the same speed, 7 hour for v=14.
But even with that it's much better than before as it's not the seven days like before.
But I need somehow to get the result, get the output.
Could you please show your correction in the code because I did somthing wrong in void function as it continiously overwrites txt file untill the program is finished. Thanks in advance.

[jonnin]

I didn't change anything else... just the print trying to speed it up, and that's up above.

are you running it directed to a file, like I said? I just don't get the 7 hours issue. That is 40 times slower, makes no sense.

it should constantly APPEND to the file in redirect mode. Should shoot up a megabyte at a time or more every refresh of the file's folder / size if watching it .

or repost your current version if you messed with it much.

[Alex009988]

I only need to now the size of the matrix. In other words, I need to know last counter. I dont need the outcomes data.

#include "stdafx.h"
#include <cstdlib>
#include <vector>
#include <iostream>
#include <iterator>
#include <time.h>
#include <fstream>
using namespace std;
static int counter = 0;
void print(std::vector<int>& a) {
	ofstream myfile;
	myfile.open("example.txt");
	myfile << ++counter << ": ";
	myfile.close();
}

void recurse(std::vector<int>& a, int pos, int remaining) {
	if (remaining == 0) {print(a); return; }
	if (pos == a.size()) { return; }
	for (int i = remaining; i >= 0; --i) {
		a[pos] = i;
		recurse(a, pos + 1, remaining - i);
	}
}
int main() {
	system("color F1");
	char yn;
	do {
		counter = 0;
		cout << "Input n:  ";
		int v, k, z;
		cin >> v;
		const clock_t begin_time = clock();
		k = v;
		z = v + 1;
		vector<int> a(k);
		for (v = -1; v < z; v++) {
			recurse(a, 0, v);
		}
		cout << counter<<endl;
		cout << float(clock() - begin_time) / CLOCKS_PER_SEC << endl;
		cout << "Press Y to continue\n";
	} while (cin >> yn && (yn == 'Y' || yn == 'y'));
	return 0;
}

As far as I understand I'm running it directed to txt file, or not?
It takes 73 seconds to be finished with v10.
So having v14 I need around 5 hours if my calculatiobs right
73/184576*45000000/3600

[jonnin]

ah. well I see what you mean about the file. you made an actual file, not a redirect. And then you open it every time you call print, which is painfully slow and overwriting.

when you run a program at the console, add >filename and all the couts will go to the file.

here...

#include <cstdlib>
#include <vector>
#include <iostream>
#include <iterator>
#include <ctime>
#include <fstream>

using namespace std;
static int counter = 0;
ofstream* print(std::vector<int>& a) //changed type so we can close file.
{
	static ofstream myfile;
	if(counter == 0)
	myfile.open("example.txt");
	myfile << ++counter << ": ";
    return &myfile;	
	//myfile.close(); //moved to main a bit weird but I am doing minimal edits. 
}

void recurse(std::vector<int>& a, int pos, int remaining) {
	if (remaining == 0) 
	{
		//print(a); //well this is boring now anyway... its just 1-N
		counter ++; //replace print ... this is all it was really doing anyway. 
		return; 
		}
	if (pos == a.size()) { return; }
	for (int i = remaining; i >= 0; --i) {
		a[pos] = i;
		recurse(a, pos + 1, remaining - i);
	}
}
int main() {
	//system("color F1");
	char yn;
	//do {
		counter = 0;
		cout << "Input n:  ";
		int v, k, z;
		cin >> v;
		const clock_t begin_time = clock();
		k = v;
		z = v + 1;
		vector<int> a(k);
		for (v = -1; v < z; v++) {
			recurse(a, 0, v);
		}
		cout << counter<<endl; //this appears to be correct
		//print(a)[0].close(); //lol... this closes the file.  but we never opened it as I commented print out. 
		cout << float(clock() - begin_time) / CLOCKS_PER_SEC << endl;
	//	cout << "Press Y to continue\n";
	//} while (cin >> yn && (yn == 'Y' || yn == 'y'));
	return 0;
}

[jonnin]

output: (didn't save 5 but its 252).

C:\c>a
Input n:  14
40116600
0.25

C:\c>a
Input n:  10
184756
0

[Alex009988]

Thank you so much for your reply. But now I have another question.
It seems that after v16 something weird happens.

Input n:  16
601080390
13.282
Input n:  18
485200708
189.1
Input n:  17
-1961361076
49.406

It's not likely to have v17 with negative value and v18 to be less than v16. What happens to the program at these vales of n?
I think int has some max value. We need to replace it by something
Edit 2, seems I've solved the problem with unsigned int.
I have last question How to get output 40116600->40 116 600 to have space beetwenn each of three digits?
Edit 3 Unsigned int dosent help with v18 I have the same result(( 485200708
220.709
With double I have aproximation 2.33361e+09
55.855

[jonnin]

when a signed value overflows past its capacity, it will turn negative.
try this:
for(char i = 0; i < 200; i++)
cout << (int)i << endl;

you are probably seeing that. make counter unsigned long long and it will work up to some N. If you need more than that, you can use a big-int library or see if your machine has a 128 bit register you can borrow (many do now). Yes, all normal int/double etc types have a max value :) Its keyed off signed / unsigned and number of bits. a 32 bit int signed can only hold 2 to the 31 power. A 64 bit int can hold up to 63 bits. Unsigned reclaims the lost bit, 32 and 64 respectively. 2 to the 64th is a very large value.

its a pain in the backside to space out an integer. You have to drop it to a string and cut it up by hand, unless there is some iostream formatter I am unaware of (its possible, I don't do that much text manipulation). you can do something like cout x/1000000 space (x-x/1000000)/10000 etc (maybe I missed the numbers of zeros but you get the idea and this has leading zeros if you don't conditionally skip them ... and you have to unsigned cast it and only print the negative sign once on negative values... etc... like I said, its a pain.

The good news is you can play with the format and all now, since it runs in a few seconds now. Experiment and learn!

By the way the above is the c++ version of a 'field repair'. Its not at all how you would write code from scratch; its how you fix code that you got from someone else when in a hurry.

if you get really bored you can plot the input and out put and craft a function that gives you the answer instantly, perhaps? If you have enough data points (and you can get at least 17, right) it may fit some exponential or something ... and you said you had a math program that can do a polynomial fitting ...

[JLBorges]

When a signed value overflows past its capacity, it engenders undefined behaviour.

[jonnin]

^^^ This is more correct.
Every system I know of, it turns it negative, but that is not assured to happen.

[Alex009988]

Thank you. I have two anomalus points so there is no strong dependacy and I'm 100% sure there thare is no problem in the program. I need some more data. I'm curently doing the calculation for v21, and I think this is the final point of this program. In order to go further, I need to use all four my cores. So I think I need to use boost library to do that. https://stackoverflow.com/questions/19063079/how-to-run-boostthreads-on-many-processors Am I right?
In order to do that I guess I need to modify the cycle. For example use one core for k=10,8,6,4,2 and another for k=9,7,5,3 etc. In this case I also need to modify counters. If I have parallel calculations, I need some sum of counts. Is it possible, or my idea is not so good?

[jonnin]

you don't need boost to do threads. Its an option, but not the only one. Pthreads is an option as well.

I don't know what you idea is, really. Breaking the above up to get the count seems like a lot of work; how long is v21 really running, 10 min? an hour? How long will it take to recode it... probably longer to thread it up (if you are new to threading for sure) than to just run it and come back in a bit. Its a one and done answer that never changes, right?

[Alex009988]

Thank you for your reply. V21 has almost took four hours and it had more than 500 bullion lines. It means that v22 should approximately have two trillions lines and it take around 15-16 hours to count this thing.
So is it possible to split the matrix in parts and pthread each part of matrix and get the final output as the sum of counts of these part.
Can it so complicate the code? In theory, of course it should be much harder, but I hope not too much.

[jonnin]

I don't know. Does each new row depend on the previous row? If so, threading it won't do a thing for you.

I honestly do not fully understand what the code does, I stuck my oar in to tell you about the print problem lol. if you can break it into parts that can be executed in parallel and then add it all up at the end, sure, that will run linearly faster on more cores. If you have 4 cores, that 20 hours will become 5, give or take a few min.

it isnt hard to break stuff up this way. Threading gets complicated quickly if you are trying to modify the same variables at the same time. If you can avoid that, its not so bad. For example a math - matrix if you can grab 1 row and do something and another row and do the same thing without touching each other, its not too complex.

ill give you a quick example..
say you had an array of a few billion items to sort.
you can take pointers into that array, split the array into 4 parts, 0-n/4, n/4+1 to n/2, .. etc and sort those 4 in parallel on 4 cpus without any worries, and then pop 2 parallel merge sorts to turn the 4 into 2, and one final merge back into 1. (Whether this is any faster or not is beside the point for the example). Nothing is shared, so you don't have to deal with concurrency problems, and the code is pretty simple (just call the sort function with the right pointers in a thread). I would start here, actually, and do a problem like this to get your head around the threading code, and then take a crack at your problem here... don't jump into threading your code without a little practice at threading. Cout and threading gets weird fast. Just so you know... you get random slices of the threads if you try to print in the thread function, and its hard to tell which row belongs to which slice.

how far are you going to push this thing? Its going up exponentially... at some point you are going to need something else, if you want like v50..

[Alex009988]

Well. tahnk you. I've found a way how to make it two times faster. So for v22 it'll take 8 hours instead of 16 hours. I also have and idea how to make it aproximately 140%, 2.4 times.
But I want to try new algorithm first.

#include "stdafx.h"
#include <cstdlib>
#include <vector>
#include <iostream>
#include <iterator>
#include <time.h>
#include <fstream>
#include <cstdio>
using namespace std;
static double counter = 0;
void print_partitions(int sum_val, int n) {
	int pos = 0, last = n - 1;
	vector<int> a(n);//int a[n] dosent work
	for (int i = 1; i != n; ++i)
		a[i] = 0;
	a[0] = sum_val;
	while (true) {
		for (int i = 0; i != last; ++i)
			printf("%3d ", a[i]);
			printf("%3d\n", a[last]);
		   ++counter;
		if (pos != last) {
			--a[pos];
			++pos;
			a[pos] = 1;
		}
		else {
			if (a[last] == sum_val)
				return;
			for (--pos; a[pos] == 0; --pos);
			--a[pos];
			int tmp = 1 + a[last];
			++pos;
			a[last] = 0;
			a[pos] = tmp;
		}
	}
}
int main() {
	system("color F1");
	char yn;
	do {
		counter = 0;
		cout << "input v:  ";
		int v,z,z1;
		cin >> v;
		z = v + 1;
		z1 = v;
		const clock_t begin_time = clock();
		for (v = 1; v < z; v++) {
			print_partitions(v, z1);
		}
		cout<<" :  "<<counter+1<<endl;
		cout  " :  " << float(clock() - begin_time) / CLOCKS_PER_SEC << endl;
		cout << "y\n";
	} while (cin >> yn && (yn == 'Y' || yn == 'y'));
	return 0;
}

So I just want to have the same thing. Just count the lines.
The problem is I cant get rid of printf functions. If I do it breaks to program. Could you please show the corrections I should do in the code. Thanks in advance.