Jump to content
  • Advertisement
Sign in to follow this  
sooner123

Performance issues with Permutations

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!