excessive RAM consumption

[ar2007]

Hi forum, I have created a program for the arrangement of n elements, on k positions. Each permutation obtained is passed to a vector of positions which uses it in another function, until the end of the permutations. The program works well but when the number of elements n> 100, the program slowly consumes all the RAM memory of the PC, until it stops because it cannot continue.
I want to clarify that the vectors are all std :: vector and have a constant number of elements, as well as the number of positions k = 5.
How can I do a RAM reset while running the program?
Any suggestions are appreciated. Thanks in advance.

[Repeater]

If all vectors have a constant number of elements, how can the memory required increase? All the memory required would be allocated at the start.

[Ganado]

Show us an example of what types you're using and what allocations you're doing.
Dealing with permutation logic can quickly blow up in your face if you use a naive approach. 100 choose 5, for instance, is already 75287520. How big are your vectors getting before you run out of memory?

If your program is 32-bit, you most likely will have only 4 GB to work with.
If you only need memory for one particular purpose, then don't store it in a vector for the lifetime of the program. Pop it back off or don't put it in a vector to begin with. It's hard to be more specific without seeing any code.

For example, the following program only requires 5 ints worth of space, but prints 5! = 120 rows.

// Example program
#include <iostream>     // std::cout
#include <algorithm>    // std::next_permutation, std::sort

int main () {
    int myints[] = {0, 1, 2, 3, 4};

    std::sort (myints, myints+5);

    std::cout << "The 5! possible permutations with 5 elements:\n";
    do {
        for (int i = 0; i < 5; i++)
            std::cout << myints[i] << ' ';
        std::cout << '\n';
    } while ( std::next_permutation(myints, myints + 5) );
}

[ar2007]

that's what I thought too :)

[Repeater]

Are your vectors fixed size? How are you creating them? Are you creating them all at the start, and reserving all the memory you need, or are you creating them or growing them as you go?

[ar2007]

#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>

inline bool isPrime(const size_t& n);
inline bool Add(size_t n, size_t m);
inline bool test( std::vector< int> &p, std::vector< int> &r); 

const size_t TOTAL_DISPLACEMENT = 126026429760;

inline void stampa2(const std::vector< int >& A)
{
	for (int i = 0; i < A.size(); ++i)
	{
		std::cerr << A[i] << " ";
	}
	std::cerr << '\n';
}

inline int CalcolaDisposizioni(int n, int k)
{
	int c{ n }, totale{ 1 }, d{ n - k + 1 };

	while (c >= d)
	{
		totale *= c--;
	}
	return totale;
}

void solutionP60(std::vector<int>& V, size_t& somma, size_t& minimaSomma, const int& len, std::vector< int>& P) // da inserire al posto della funzione stampa(P)
{
	size_t soluzione{ 0 };
	{
		bool test2 = true;

		for (int i = 0; i < len; ++i)
		{
			for (int j = i; j < len; ++j)
			{
				if (i != j)
				{
					if (!Add(P[i], P[j]) || !Add(P[j], P[i]))
					{
						test2 = false;
						break;
					}
				}
			}
			if (!test2)
				break;
		}

		if (test2)
		{
			for (int i = 0; i < P.size(); ++i)
			{
				soluzione += P[i];
			}

			if (soluzione < minimaSomma)
			{
				minimaSomma = soluzione;
				for (int i = 0; i < P.size(); ++i)
				{
					std::cerr << P[i] << " ";
				}
				std::cerr << '\n' << "soluzione: " << soluzione << '\n';
				
			}
		}

	}

}

void f2(std::vector< int >& V, std::vector< int >& P, size_t  &somma, size_t &minimaSomma, const int &len)
{
	std::vector< int> a(P.size(), 0);
	size_t j{ P.size() - 1 }, i{ 0 };
	size_t count{ 0 };

	for (int w = 0; w < P.size(); ++w)
	{
		P[w] = V[w];
		a[w] = w;
	}

	bool flag{ false };

	while (j >= 0)
	{
		if (j == P.size() - 1)
		{
			for (int k = 0; k < V.size(); ++k)
			{
				bool test{ true };
				for (int l = 0; l < P.size() - 1; ++l)
				{
					if (V[k] == P[l])
					{
						test = false;
						break;
					}
				}

				if (test)
				{
					P[j] = V[k];
					a[j] = k;
					solutionP60(V, somma, minimaSomma, len, P);

					++count;
				}
			}
			flag = false;
			--j; // posizione precedente
		}
		else if (0 < j && j < P.size() - 1)                // SE J è COMPRESA TRA 0 E P.size-1
		{
			if (flag)                                       // VERIFICA SE SI è PASSATI DA J = 0;
				a[j] = 0;

			i = a[j];                                       // ASSEGNA AD i IL VALORE NELLA MEMORIA DEGLI INDICI

			if (i < V.size())                             // SE i è INFERIORE AL LIMITE MASSIMO DEL VETTORE DEGLI ELEMENTI,...
			{
				bool test{ true };

				for (int l = 0; l <= j; ++l)                // VERIFICA SE NELLE POSIZIONI PRECEDENTI ED ATTUALE CHE NON VI SIA GIà V[i]
				{
					if (V[i] == P[l])                       // IN CASO DI ESITO POSITIVO NELLA RICERCA, i NON PUò ESSERE USATO E QUINDI.....
					{
						test = false;
						break;
					}
				}

				P[j] = V[i];                                // ASSEGNAZIONE DI V[i] ALLA POSIZIONE J
				a[j] = ++i;                                 // MEMORIZZAZIONE DEL VALORE SUCCESSIVO DI i

				if (test)                                   // SE ESITO NEGATIVO DELLA RICERCA NELLE POSIZIONI PRECEDENTI,
				{
					++j;                                    // SPOSTAMENTO NELLA posizione successiva solo nel caso di ricerca con esito negativo
				}
			}
			else                                            // ALTRIMENTI SE i == V.size-1
			{
				a[j] = 0;                                   // AZZERA LA POSIZIONE DELLA COLONNA
				--j;                                        // RITORNA ALLA posizione precedente
			}
			flag = false;
		}
		else if (j == 0)                                    // ALTRIMENTI SE J è ARRIVATO ALLA POSIZIONE INIZIALE,
		{
			i = a[j];                                       // ASSEGNA AD i IL VALORE NELLA MEMORIA DEGLI INDICI

			a.resize(5, 0);                                  // RESET DEL VETTORE DELLE POSIZIONI

			a[j] = ++i;                                     // MEMORIZZAZIONE DEL VALORE SUCCESSIVO DI i

			if (i <= V.size() - 1)                            // CONDIZIONE DI USCITA O DI VARIAZIONE DELLA POSIZIONE J = 0
				P[j] = V[i];
			else
			{
				std::cerr << count << '\n';
				return;
			}

			++j;                                            // SPOSTAMENTO SULLA POSIZIONE SUCCESSIVA
			flag = true;                                    // SEGNALE CHE è AVVENUTO IL RESET
		}
	}

}


int main()
{
	size_t n{ 1 };
	const int len = 4;
	std::vector< int> P(len, 0);

	size_t minimaSomma{ 1000000 };
	size_t somma{ 0 };

	std::vector< int> V;
	
	
//
	int k{ 0 };
	while ( (n += 2) < 100)
	{
		if (isPrime(n))
		{
			V.push_back( n);
		}
	}  // ok

	for( int i = 0; i < V.size(); ++i)
		std::cerr << V[i] << " ";
	std::cerr << '\n';

	clock_t t = clock();

	f2(V, P, somma, minimaSomma,len);

	t = clock() - t;
	std::cerr << " tempo in secondi: " << ((float)t / CLOCKS_PER_SEC) << '\n';

	return 0;
}

inline bool isPrime(const size_t &n)
{
	for (size_t i = 2; i <= sqrt(n); ++i)
	{
		if (n % i == 0 || n == 5)
		{
			return 0;
		}
	}
	return 1;
}

inline bool Add( size_t n, size_t m)
{
	size_t d{ m }, size{ 0 };

	while ( m > 0 )
	{
		m /= 10;
		++size;
	}

	return (isPrime(d + n * pow(10, size )));
}

[ar2007]

my pc is a 64 bit and has 16 gb of ram, i7 quad core cpu.

my code reduces the number of permutations needed by 72% compared to the std :: next_permutaion () function. that's why I'm trying to force this type of program to run

[Ganado]

I had to add #include <cmath> to compile your code. You should #include <cmath> if you're going to be using functions like sqrt.

My output for your program is:

3 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
212520
 tempo in secondi: 0.089

What are the exact conditions that make it start to fail? Also, function names like "f2" and "Add" make no sense.

Does your program actually crash? Or are you just saying it's taking too long to complete?

[ar2007]

please use:
line 182:

const int len = 5;

line 193:

while ( (n += 2) < 1000)

f2: function permutation;
Add: given two numbers 'a' and 'b', Add returns 'ab'
example a = 10, b = 37, ab = 1037,
then verify that the tiling is a prime number

Does your program actually crash? Or are you just saying it's taking too long to complete?

yes, is too long but stops due to exhaustion of the RAm

[Ganado]

Okay, so it correctly prints the prime numbers (except 5, you might want to double check your logic there). As far as I can tell, your problem isn't memory. What is the exact error message you get if you're saying it's RAM? Your issue is your program just never stops running (it's taking too long to crunch the numbers). You need to re-think your algorithm.

What kind of a run-time duration are you expecting?
Here is the number it prints for given values of "< N", with len = 5.

 10          0
 15          0
 17          0
 18        120
 19        120
 20        720
 24       2520
 30       6720
 32      15120
 38      30240
 50     154440
110    9687600
113    9687600
114   11793600
128   14250600

The run-time complexity of your code seems to be blowing up.

Check out the OEIS.
Input 120,720,2520,6720,15120
http://oeis.org/search?q=120%2C720%2C2520%2C6720%2C15120&sort=&language=english&go=Search

The OEIS probably already has something similar to the data you're computing, and may have suggestions for a much better way to compute it.

[ar2007]

question: even if the number of cycles (indicated by the variable 'count') becomes very large, what does it imply in a linear permutation procedure, since the variable 'count' is only a counter?
function 'f2' generates permutations only on 5 positions, with the condition that in position 5 (last), it lists all the elements not present in the previous positions.
Therefore it is only a consecutive procedure, without displacements between the elements of V []. So I don't think the problem is the number of cycles the program runs. In fact, the PC does not stop and does not generate any error code. The program remains running but does not go on because the RAM is almost exhausted (I check it through the 'memory' app).

[ar2007]

The run-time complexity of your code seems to be blowing up.

Check out the OEIS.
Input 120,720,2520,6720,15120
http://oeis.org/search?q=120%2C720%2C2520%2C6720%2C15120&sort=&language=english&go=Search

The OEIS probably already has something similar to the data you're computing, and may have suggestions for a much better way to compute it.

okay. i try to rethinking my code.

thank you.

[ar2007]

The problem is inline function ‘Add()’, no problem with complexity. See you.
Thx Ganado.

[Ganado]

If changing your Add function to something else fixed the issue, I'd argue you probably changed the runtime complexity of the program :)
Anyway glad it working now.