Public Group

# Performance issues with Permutations

This topic is 2766 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

There is a 16 element array, and 24 numbers to choose from, and this program cycles through every one of the (24 choose 16) permutations (approximately 700,000)

My thinking is that this should occur in less than a second. (especially seeing as how this is based on much more complicated code that for each of these permutations would be dealing with an 8x5 2d array and doing evaluations of the array at each node. And this more complex code only takes 50% longer.

 Module FastGridPermutation Dim evaluationCounter As Integer = 0 Sub Main() Dim nulls(15) As Integer For i = 0 To 15 nulls(i) = 0 Next Console.WriteLine("(24c16)") Dim startTime As Long = DateTime.Now.Ticks makeSimpleGridPermutations(nulls, 0) Dim endTime As Long = DateTime.Now.Ticks Console.WriteLine(((endTime - startTime) / 10000000) & " s") Console.ReadLine() End Sub Sub makeSimpleGridPermutations(ByVal nulls() As Integer, ByVal numNulls As Integer) Dim permutationContainsValueBool As Boolean = False If numNulls < 16 Then For i = 1 To 24 For j = 0 To numNulls If nulls(j) = i Then permutationContainsValueBool = True Next If Not permutationContainsValueBool Then makeSimpleGridPermutations(arrayModify(nulls, numNulls, i), numNulls + 1) Next Else evaluationCounter += 1 If (evaluationCounter Mod 1000000 = 0) Then Console.WriteLine(evaluationCounter) End If End Sub Function arrayModify(ByRef nulls As Integer(), ByVal index As Integer, ByVal value As Integer) As Integer() Dim nullsCopy(15) As Integer Array.Copy(nulls, nullsCopy, 16) nullsCopy(index) = value Return nullsCopy End Function End Module 

I know Array copying is slow, but there is no other way I know of to accomplish a recursive array-based algorithm, due to arrays always being passed by reference.

And besides, my other code is copying an 8x5 array and it is barely slower than this code.

How can I make this code faster? a 10x speedup should be possible.

Or is VB.NET just an extremely slow language?

##### Share on other sites
First of all, these are called "combinations", not "permutations". Indeed, generating 24 choose 16 combinations should be really fast. I don't know any VB, so I won't try to read your code. You don't need to copy arrays around to do this.

##### Share on other sites
This is some really fast code in C++ (it should be easy to translate to VB):
#include <iostream> int main() { int counter = 0; int combination[16]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}; while (1) { ++counter; // ... or do something more interesting here int i; for (i=15; i>=0; --i) { if (combination<(8+i)) break; } if (i<0) break; combination++; for (int j=i+1; j<16; ++j) combination[j] = combination + j - i; } std::cout << counter << '\n'; } 

##### Share on other sites
How often are you running this loop because if it is running millions of times as that evaluationCounter seems to suggest, the allocation and stack overhead might be what is killing your performance. Can you write this without the recursion and see if that matters.
Memory copies are slow, espectially when you are not hitting the chache which is likely with recursion.

As [color="#284b72"]alvaro's code above shows you do not need the recursion to do this.

##### Share on other sites

Memory copies are slow, espectially when you are not hitting the chache which is likely with recursion.

Can you explain that part? Why would we expect more cache misses when using recursion?

##### Share on other sites
Doing a quick conversion of your code to C# (since VB makes my head hurt), I get the MakeSimpleGridPermutations() method called over 16 million times during a run. I think small array copying issues are the least of your problems - you need to reduce the number of iterations to see a large performance increase. Actually, I never knew C# would allow such a deep recursion, I'm pretty amazed. Here is my converted code in case I got a piece of your logic wrong:

 class Program { static void Main(string[] args) { int[] nulls = new int[16]; long startTime = DateTime.Now.Ticks; MakeSimpleGridPermutations(nulls, 0); long endTime = DateTime.Now.Ticks; Console.WriteLine((endTime - startTime)/10000000); Console.WriteLine(evalCounter); Console.ReadLine(); } static long evalCounter = 0; static void MakeSimpleGridPermutations(int[] nulls, int numNulls) { bool PermuContainsValue = false; evalCounter++; // I changed the usage of this varaible to track total # of method calls if (numNulls < 16) { for (int i = 0; i < 24; i++) { for (int j = 0; j < numNulls; j++) { if (nulls[j] == i) { PermuContainsValue = true; } } if (!PermuContainsValue) { MakeSimpleGridPermutations(ModifyArray(nulls, numNulls, i), numNulls + 1); } } } } static int[] ModifyArray(int[] nulls, int index, int val) { int[] nullsCopy = new int[16]; Array.Copy(nulls, nullsCopy, 16); nullsCopy[index] = val; return nullsCopy; } 

##### Share on other sites
Actually, I never knew C# would allow such a deep recursion[/quote]

Maximum recursion depth is 16, not 16 million.

##### Share on other sites
Woops. You're right. They are indeed combinations. (assuming I understand the difference correctly)

combinations:
12
13
23

permutations:
12
13
23
21
31
32

I had to look up the definition. I'd thought it was the opposite is all.

I came up with my own algorithm for combinations since this post and my program is running 177 times faster for this implementation.

I think my algorithm is equivalent to the one used by the code alvaro posted, except it does it recursively. It actually looked almost identical then I made it recursive so the code would be more readable for the person I'm sending this code to to maintain.

##### Share on other sites
laztrezort, it's only depth 16 recursion. i think you're thinking of the width of the call tree

##### Share on other sites

[quote name='NightCreature83' timestamp='1332340911' post='4923939']
Memory copies are slow, espectially when you are not hitting the chache which is likely with recursion.

Can you explain that part? Why would we expect more cache misses when using recursion?
[/quote]
Yeah ignore that cahce thing my head must have been elsewhere.

laztrezort, it's only depth 16 recursion. i think you're thinking of the width of the call tree

The way the code is layed out you can actually call the function 16 * 24 + 1 times.

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 18
• 13
• 9
• 9
• 25