Vectors with 1.000.000 elements

[Gorthorien]

Hello,

I'm using C++, MinGW developer studio.
I need to check how many pairs of { x, x^2 } are in a vector(the same vector).The vector has "n" elements and 2<=n<=1.000.000. The problem is how can i declare a vector with 1.000.000 possible elements. If i try to declare it as v[1000000] the algorithm crashes( I get that not responding error ) after i try to debug it. I tried using multiple vectors and combine them, but that didn't work either.Here is the algorithm:

#include<iostream>

using namespace std;

int main()
{
	float v[1000000], a;
	int	n, r, j, i;
	cout<<"n= ";
	cin>>n;
	for(i=1;i<=n;i++)
		cin>>v[i];
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			a=sqrt((double)v[j]);
			if(v[i]==a)
				r++;
		}
	}
	cout<<r;
	return 0;
}

in "r" variable i stocked the number of the pairs.

Sorry if my English is bad :).

Thank you in advance.

[BlackSheep]

Use dynamic allocation:

float *v = new float[1000000];

Or, even better, you can use an std::vector:

#include <vector> //Gotta include the vector headers

std::vector<float> v(1000000);
//OR
std::vector<float> v;
v.reserve(1000000);

[Gorthorien]

I will google about what you just said, i'm just 9th Grade and we didn't learn anything about this.
P.S: We didn't even learn vectors.....i just learn them from google :D

[Catfish2]

Gorthorien, do you see the menu on the left?
Reference and Documentation are there.

[zb0S216C]

Note that std::vector::reserve() reserves enough space for at least N elements; the call could allocate more than requested or exactly the specified amount. However, a default-initialised std::vector implicitly allocates a lot of memory to begin with, so there may be no need to reserve memory.

Dynamic memory allocation is an option here, just make sure you de-allocate the resources you accumulate.

_Wazzak

[Gorthorien]

that

#include <vector> //Gotta include the vector headers

std::vector<float> v(1000000);
//OR
std::vector<float> v;
v.reserve(1000000);

works (now the program doesn't crash), but the execution time is too long(i waited for about 10 seconds and I didn't the final result wasn't ready yet and it has to be maximum 1 sec, and i tried with exactly 1.000.000 elements).Any ideas how i could make it run faster?
Thank you for the help given.

[Catfish2]

The complexity of your program is pretty high (looks like O(n²) to me?).
This means that the total number of operations is your n, which is 1 million, squared, because of those nested for()'s. So 10 seconds is expectable.
http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

[Gorthorien]

This seems a little bit too hard for me yet.However the 1.000.000 elements was for 100% of the score, and 1.000 for 30% which is really easy.Seems that i will stick with that 30% of the total score and i will try with 1.000.000 after i learn some more things at school and maybe the teacher could explain some things to me.
Thank you very much for your help.

[Catfish2]

I think you should keep at it.

The problem is this: you read the user data in a big vector, then go through the vector by using two for()'s, checking for your x = y² condition. This takes time, because there are > n² operations to be done.

So what can you do to make the algorithm run faster?
It's complicated, but basically you should use something other than std::vector<float>.
I'm thinking std::multiset<std::pair<float, float> >.
(Instead of std::map<float, float> because that wouldn't keep duplicates.)

What does this help with? You can store extra information and the multiset will find your target faster than you can with a for(), because it sorts the pairs, internally.

I do not know if using vectors is one of your requirements for the project. But if not, by using a multiset of pairs, you can reduce complexity to O(n log n) which means the program will run faster.

Otherwise, 1 second for dealing with a 1 million floats vector doesn't look sane to me.
Are you sure you didn't misunderstand the problem you were given?

[Lowest0ne]

Maybe I am wrong, but arent you really just trying to find how many square numbers there are that are less than 1mil?

[BlackSheep]

@LowestOne: I've got an O(1) algo for that:

count = (int)sqrt(1000000);

XD

I think the easiest way to solve this problem is not to build a vector containing the actual numbers, but one that just counts how many of each number there are. Use the number for the index, and then increment the value stored there. The only problem is that you'll have to initialize the vector to all 0's for this to work. Something like this:

std::vector<int> count(1000000,0);
for(size_t i = 0; i < 1000000; ++i)
{
int index;
std::cin >> index;
count[index-1]++;
}

Then, iterate through your vector and multiply the current index's count by its square's count:

for(int i = 1; i < sqrt(1000000); ++i)
{
total += count[i-1]*count[(i*i)-1];
}

Disclaimer: I might be completely wrong, but if this works it should give you approximately O(2n).

EDIT: Fixed indexing.