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
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.
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.
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;
}
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.
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;
}
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.
[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.
