Thread: Number of permurations an memory problems.

Hello guys!

I'll give you the big picture of what I'm doing. I'm solving a combinatorial optimization problem. I find an initial solution and then try to improve it with some heuristics. One of them involves some local search techniques. Everything works well except that I encounter a memory problem. My local search works only for small instances of the problem (ie up to 600 nodes). For larger instances I get an OutOfMemoryError exception. The exception occures in the method that finds the "neighbors" of the current solution. You can think of this method as one that finds all possible permutations of a list (all possible triplets or quadraplets of arcs, more precisely).
Each neighbor-permutation is saved in an array (since I know its length) and the whole neighborhood in an ArrayList.
My thought is to find the number of permutations P(n,r) so that I can use an array for the neighborhood or at least an ArrayList of initial size -since the exception occurs while the ArrayList is increasing its size, ie copies its internal array to a bigger one, and I think it will avoid that if it has an initial size.

I implemented a recursive method to calculate P(n,r)

public static long factorial(long n) {
        if (n == 0) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
 
    //P(n,r) = n! / (n - r)!
    public static long permutations(long n, long r) {
        long arithmitis = factorial(n); //n!
        long paron = factorial(n - r); //(n - r)!
 
        return arithmitis / paron;
    }

This method works fine for a relatively small n (r is always 3 or 4) but when I try to find P(120,3) for example -which is near to what I will have to find for my program- it crashes, because the values of factorial(n) factorial(n-r) are very large and cannot be held in the long variables.

Here are my questions:
Firstly, do you think that saving the neighborhood in an array or an ArrayList with initial size would improve my memory problem or I'm just wasting my time?
And secondly, any thoughts on how to make the permutations(long n, long r) method to work?

Thanks for your time.

PS:I have used the -Xmx option to increase the VM's heap space with some good results.

Originally Posted by KevinWorkman

What is the actual error you're getting?

When I try to solve a large instance of the problem I get the following error:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
        at java.util.Arrays.copyOf(Unknown Source)
        at java.util.Arrays.copyOf(Unknown Source)
        at java.util.ArrayList.grow(Unknown Source)
        at java.util.ArrayList.ensureCapacityInternal(Unknown Source)
        at java.util.ArrayList.add(Unknown Source)
        at msp.MSPImprover.getTriads(MSPImprover.java:295)
        at msp.MSPImprover.opt_3(MSPImprover.java:61)
        at msp.MSPImprover.opt_3(MSPImprover.java:114)
        at msp.MSPImprover.opt_3(MSPImprover.java:114)
        at msp.MSPSolver.main(MSPSolver.java:658)

That's why I thought it would help if I used an ArrayList(int initialCapacity)
To be able to find the initialCapacity I tried the recursive method I posted which for large numbers of n throws the following exception:

Exception in thread "main" java.lang.ArithmeticException: / by zero
	at msp.MSPImprover.permutations(MSPImprover.java:411)
	at msp.MSPImprover.main(MSPImprover.java:415)

I did some debugging and found out that after some (big) number both variables arithmitis and paron become 0.

Originally Posted by KevinWorkman

What happened when you tried increasing the initial size?

I didn't tried that externally. I ment that the ArrayList increases its internal array's size (ie copies its elements to a bigger one).

Hope that makes sense.

Originally Posted by KevinWorkman

How big does your data structure have to become in order to accommodate all the permutations?

It should be equal to the number of the permutations , if I'm getting right what you asked.

Originally Posted by KevinWorkman

Do you really need to make so many copies?

You mean if I need all the permutations? Yes, I need them because I want to search every possible neighbor. That was my purpose. At this point, I don't want to improve the computational time or the memory usage against the results (even though the way it is now it can be applied only in small instances - but it gives optimal solutions regarding the local search).
I'm planning to implement some more sophisticated techniques and algorithms that will be able to give good results in large instances of the problem.

Originally Posted by KevinWorkman

How many permutations are you generating though? How large is each permutation?

I'm also asking whether you need to copy the data as many times as you do, since you mentioned copying arrays in your first post. You can generate different arrays without actually copying the values inside them. Compare an array that points to a million instances of String that contain the same text versus an array that contains a million references to a single String instance.

I don't actually know the answers to these questions, since you haven't posted an SSCCE, so I'm just guessing. But it's where I'd look if I were you.

I didn't explain well what I'm doing. This is the method that causes the java.lang.OutOfMemoryError exception I posted in post#2. I generate P(n,r) permutations which for the following method is P(forObj.size, 4). If you are asking about the actual number of permutations the exception occurs for n > 60 approximately.

public ArrayList<Edge[]> getQuadraplets(ArrayList<Edge> forObj) {
        ArrayList<Edge[]> quadraplets = new ArrayList();
 
        for (int i = 0; i < forObj.size(); i++) {
            for (int j = 0; j < forObj.size(); j++) {
                for (int k = 0; k < forObj.size(); k++) {
                    for (int l = 0; l < forObj.size(); l++) {
                        if ((i != j && i != k && i != l && j != k && j != l && k != l)) {
                            Edge[] qudraplet = new Edge[4];
                            qudraplet[0] = forObj.get(i);
                            qudraplet[1] = forObj.get(j);
                            qudraplet[2] = forObj.get(k);
                            qudraplet[3] = forObj.get(l);
 
                            quadraplets.add(qudraplet);
                        }
                    }
                }
            }
        }
//        System.out.println("quadraplets : " + quadraplets);
//        System.out.println("quadraplets.size =  " + quadraplets.size());
        return quadraplets;
    }

As you can see I'm not copying any array in my code. I thought that if I gave quadraplets an initial size that would improve my memory use.
I tested that and it didn't help - as you had told me in post#3.

I realized that I can accomplish what I want to do with a different approach which will hopefully decrease my memory consumption. I'm working on the new design right now. I will update the thread when I complete the tests and have some results.

Originally Posted by KevinWorkman

You've specified n, but how do your permutations grow? Is it really (60!), which is 8.3209871e+81, which is definitely not going to fit in memory? Or is it something else?

Basically, as n gets bigger, how does the size of quadraplets grow?

The number of permutations is P(n,r) = n!/(n-r)!
So for n=60 and r=4 I have P(60,4) = 60! / (60 - 4)! = 11703240 permutations.

I tried the same method with each quadraplet being a String instead of an Edge array but I got again a java.lang.OutOfMemoryError exception. That's why I'll try a new approach (without trying to find all the permutations).

Originally Posted by andreas90

The number of permutations is P(n,r) = n!/(n-r)!
So for n=60 and r=4 I have P(60,4) = 60! / (60 - 4)! = 11703240 permutations.

I get it: You want to calculate the number of permutations of (n,4) in Java, where n can be something on the order of 104 (as indicated in your first post). Then you can specify the initial size of the ArrayList of arrays of Edges so that the loop does not have to spend time garbage collecting and re-allocating space as the ArrayList grows.


Now, here's the thing: The largest number whose factorial fits into a Java long variable (64-bit signed integer) is 20, so you certainly can't use Java's built-in integer or long data types to calculate P(104,4) with a naive implementation of the expression 104!/(104-4)! = 104!/100!

However...

If you think of what happens if you divide 104 factorial by 100 factorial, you should realize that the result is equal to the first r terms of the numerator: 104*103,*102*101.

See? The other factors in the numerator are 100*99*98*....*1, and they get canceled exactly by the 100 factorial in the denominator. It makes no sense to multiply 100*99*98* ... *1 in both numerator and denominator then cancel that much out by division.

In general, the scheme is

P(n,r) = n * (n-1) * (n-2) * ... * (n-r-1)
        |<----------- r terms ----------->|

You can do this programmatically by starting with a product value of 1 and making a loop that is traversed r times.

You want to multiply the product by n the first time through the loop and n-1 the second time and n-2 the third time, etc.

Bottom line: If the loop counter is i, start with i = 0 and multiply by (n-i) each time through the loop. You never have to explicitly calculate the factorial of anything.


Next...

Originally Posted by andreas90

I tried the same method with each quadraplet being a String instead of an Edge array but I got again a java.lang.OutOfMemoryError exception

I don't know, exactly, what your "real" Edge object is, but let's suppose its object field is an array of four floats. (Each float takes four bytes of memory in Java.)



Now, here's the thing: I'll try to compile and execute a "toy" program that uses an Edge consisting of an array of four floats:

public class Z {
    public static void main(String [] args) {
        ArrayList<Edge> x = new ArrayList<Edge>();
 
        //
        // Do whatever you need to do to populate the ArrayList
        //
        //   In other words:
        //   Put code here to add Edges to the ArrayList
        //
        //       code, code, code, code, ...
        //
        // Suppose it turns out to have 110 elements
        //
 
        int n = x.size();
 
        int np = numPerms(n, 4); // Calculate P(n,4) with a scheme like the one I described
 
        System.out.println("For the ArrayList x:");
        System.out.printf("  Number of Edges    = %4d\n", x.size());
        System.out.printf("  Number of bytes    = %4d\n\n", new Edge().arraySizeInBytes()*x.size());
        System.out.printf("Number of permutations P(%d,4) = %d\n\n", n, np);
 
        ArrayList<Edge[]> ax = getQuadruplets(x);
 
        System.out.printf("For the ArrayList of Edge arrays, ax, with P(%d,4) elements:\n", n);
        System.out.printf("  Number of elements = %10d\n", ax.size());
        System.out.printf("  Number of Edges    = %10d\n", new Edge().arraySize()*ax.size());
        System.out.printf("  Number of bytes    = %10d\n", new Edge().arraySizeInBytes()*ax.size());

I created methods for my Edge class that report the size of the array and the number of bytes in the array

Now when I compile like this:

javac Z.java
javac Z

I get the following

For the ArrayList x:
  Number of Edges    =  110
  Number of bytes    = 1760
 
Number of permutations P(110,4) = 138556440
 
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at java.util.ArrayList.<init>(ArrayList.java:132)
	at Z.getQuadruplets(Z.java:53)
	at Z.main(Z.java:32)

Apparently the default heap space for the JVM is not large enough to hold an ArrayList consisting of 138556440 arrays of four floats.

As you already know, you can give it more heap space by using the -Xmx java command line option. How many bytes do you think will be needed by the ArrayList of P(110,4) arrays of floats?

To get 2500 Megabytes heap space, the command that I used is

java -Xmx2500m Z

And now the output is

For the ArrayList x:
  Number of Edges    =  110
  Number of bytes    = 1760
 
Number of permutations P(110,4) = 138556440
 
For the ArrayList of Edge arrays, ax, with P(110,4) elements:
  Number of elements =  138556440
  Number of Edges    =  554225760
  Number of bytes    = 2216903040

(This is for java version 1.6.0_24 on my 32-bit Centos 6.3 Linux workstation.)

For your program, if an Edge object takes more memory than an array of four floats, your requirements will be larger.

Note that the maximum heap size that the JVM can use is Operating System dependent and implementation dependent. For a 32-bit Linux system, the maximum is (probably) something between 2500 and 2600 Megabytes (roughly 2 Gigabytes), assuming you have a sufficiently large swap partition. For 64-bit Linux systems it is (probably) much larger, but, again, it will (probably) be limited by the size of the swap partition.

Note that if you ask for more heap space than your system supports, you will get an error message to that effect. For example, on my system:

 java -Xmx2700m Z
Error occurred during initialization of VM
Could not reserve enough space for object heap
Could not create the Java virtual machine.

The semi-final note:
The maximum amount of heap space is not (that's not) limited by the actual amount of physical RAM your system has, but, generally speaking, performance is better for larger amounts of RAM than for smaller amounts.

Originally Posted by andreas90

new approach (without trying to find all the permutations).

The final note: Maybe that's a good idea, if you can do it. My "toy" test program wasn't very useful, and, in fact, there were several problems that would make me abandon attempts to keep all of the more than 100 million permutations in memory at the same time.

I mean, just because it can allocate storage for all of those Edge arrays, doesn't mean that it can actually process them in a useful way and in a reasonable amount of time. I really wouldn't try it if there were any other way to approach the problem.



Cheers!

Z

Hello Z!

Thanks for the time you spent on my problem. I tried calculating P(n,r) as you suggested and it worked as I thought. I don't get a java.lang.OutOfMemoryError exception in the internal processes of the ArrayList as before. However I still get one. Unfortunately, my Edge keeps a lot more data and my 32-bit win7 machine can only accept a 1500m parameter in the -Xmx option. Therefore I'm still trying to get my new approach to work.

PS: Your posts and work is what this kind of forums is all about. Happy to see you here. Keep up the great work.

OK, a few things. If you want to store every single possible combination, you're going to have to post specs, specifcally, how much RAM you have. I'll take a guess at 3 gigs. Windows 7 takes about 1.5 gigs depending on what's running. I have 12 gigs of RAM and can't store, as a boolean (1-bit) an array larger than... well idk, but not large enough that I need. You're going to have to find another way. Now, my question to you, do you need to record how many combinations of something or the number of combinations. Also, are you looking for combinations or permutations as there a LOT more permutations for a set than there are combinations. There are also ways around the primitive types that allow the more range than a double and more precision than a long, but it depends on what you need to do.

Hello aesguitar!

You are right about my RAM, it's 3GB. As you can see from the code I posted I keep the permutations, not combinations. My new approach involves finding the combinations (which are far less than the permutations as you pointed out). I know my workarounds (even with combinations) are limited by my memory. I just want to be able to apply my methods in larger instances of the problem. ie now I can apply them in instances with 500 nodes approximately, I wish I could apply them in instances up to 1000 nodes - I know it's impossible with 5000 nodes.

Ok, what's your purpose is storing the combinations? Are you trying to find the number of combinations or permutations, or are you actually trying to store all the combinations for whatever reason? If you are simply trying to find the number of combinations or permutations, there are some easily code-able combinatric formulas that you can use.

Originally Posted by aesguitar

Ok, what's your purpose is storing the combinations? Are you trying to find the number of combinations or permutations, or are you actually trying to store all the combinations for whatever reason? If you are simply trying to find the number of combinations or permutations, there are some easily code-able combinatric formulas that you can use.

Unfortunately I need the combinations/permutations themselves. Finding the number of them was a "trick" to improve the time and memory usage. ie using an ArrayList with initial size (which is the number of permutations) to store all the permutations.

I saw you were using nested for loops

for(/*conditions blah blah blah*/)
{
     for(/*conditions blah blah blah*/)
     {
          for(/*conditions blah blah blah*/)
          {
               for(/*conditions blah blah blah*/)
               {
               }
          }    
     }
}

What you could try is every nth iteration of the top for loop, write the contents of the ArrayList to a text file. the clear the ArrayList. It'll solve the Java heap issue and it will save the permutations.

Originally Posted by aesguitar

What you could try is every nth iteration of the top for loop, write the contents of the ArrayList to a text file. the clear the ArrayList. It'll solve the Java heap issue and it will save the permutations.

Thanks for your suggestion.
Unfortunately, at some point I'll need all the permutations together in the ArrayList to do some stuff with them, so the exception may be avoided when I'm generating them but it will occur when I'll try to read the text file. Also, writing to and reading from the text file will effect the computational time of my program.

I'm marking this thread as solved as the first part of my problem (calculating P(n,r)) is solved and the second (OutOfMemoryError) cannot be solved with my approach. I'll start a new thread if I have problems with the new approach I'm working on.

Thanks again to anyone contributed to this thread.

Create an arraylist of files containing the permutations, then simply get the required permutations from the containing file.

Originally Posted by aesguitar

Create an arraylist of files containing the permutations, then simply get the required permutations from the containing file.

As I said in my previous post this will effect the computational time of the program.
In each run of the algorithm, the method that creates the permutations is called many times. Therefore the computational time will be increased if I write the permutations and then read them.
I should note that the computational time of the algorithm is very important since this is how I'm measuring how "good" it is (along with the results - the cost of the solution it returns).

The only other way I could think of is to create a 2d array. I don't know how that effects how much memory is available though.

I have given up the approach with the permutations since it seems like a dead end. I'm working on a different approach now.