I am trying to write an algorithm that locates the possible solutions for choosing 10 values from a 10x10 grid. No two values can share the same row or column. There are 10! combinations (just over 3,600,000).
My initial algorithm uses 10 nested for loops and simply checks each possible combination of 10 squares. When I try to run the app on my MacBook it takes many, many minutes so to relieve the boredom I log each test to the console, that way I can watch the tests rack up.
The problem is that the app runs until test number 714271 and then freezes. This result is repeatable.
I assume it's a memory thing and some counter somewhere is exceeding its max allowed value but the number has no significance when I google it.
Code looks like this:
-(IBAction)findSolutions:(id)sender{
NSMutableArray* flags = [[NSMutableArray alloc]initWithObjects:[NSNumber numberWithInt:0], [NSNumber numberWithInt:0], [NSNumber numberWithInt:0], [NSNumber numberWithInt:0], [NSNumber numberWithInt:0], [NSNumber numberWithInt:0], [NSNumber numberWithInt:0], [NSNumber numberWithInt:0], [NSNumber numberWithInt:0], [NSNumber numberWithInt:0], nil];
NSMutableString* solutionsString = [[NSMutableString alloc]init];
int a,b,c,d,e,f,g,h,i,j,z,sum;
for(a=0;a<=9;a++){
for(b=0;b<=9;b++){
for(c=0;c<=9;c++){
for(d=0;d<=9;d++){
for(e=0;e<=9;e++){
for(f=0;f<=9;f++){
for(g=0;g<=9;g++){
for(h=0;h<=9;h++){
for(i=0;i<=9;i++){
for(j=0;j<=9;j++){
for(z=0;z<=9;z++){
[flags replaceObjectAtIndex:z withObject:[NSNumber numberWithInt:0]];
} //Clear the flags matrix
//Load the flags matrix
[flags replaceObjectAtIndex:a withObject:[NSNumber numberWithInt:1]];
[flags replaceObjectAtIndex:b withObject:[NSNumber numberWithInt:1]];
[flags replaceObjectAtIndex:c withObject:[NSNumber numberWithInt:1]];
[flags replaceObjectAtIndex:d withObject:[NSNumber numberWithInt:1]];
[flags replaceObjectAtIndex:e withObject:[NSNumber numberWithInt:1]];
[flags replaceObjectAtIndex:f withObject:[NSNumber numberWithInt:1]];
[flags replaceObjectAtIndex:g withObject:[NSNumber numberWithInt:1]];
[flags replaceObjectAtIndex:h withObject:[NSNumber numberWithInt:1]];
[flags replaceObjectAtIndex:i withObject:[NSNumber numberWithInt:1]];
[flags replaceObjectAtIndex:j withObject:[NSNumber numberWithInt:1]];
sum = 0;
for(z=0;z<=9;z++){
sum = sum + [[flags objectAtIndex:z]intValue];
} // sum the flags matrix. Will = 10 if all columns are filled
if (sum == 10) {
NSLog(@"Test no. %d, sum=%d, a=%d, b=%d, c=%d, d=%d, e=%d, f=%d, g=%d, h=%d, i=%d, j=%d",y,sum,a,b,c,d,e,f,g,h,i,j);
[solutionsString appendString:[NSString stringWithFormat:@"Test no. %d, sum=%d, a=%d, b=%d, c=%d, d=%d, e=%d, f=%d, g=%d, h=%d, i=%d, j=%d",y,sum,a,b,c,d,e,f,g,h,i,j]];
[txtSolutionsFound setStringValue:solutionsString];
} // These are possible solutions
NSLog(@"a=%d, b=%d, c=%d, d=%d, e=%d, f=%d, g=%d, h=%d, i=%d, j=%d",a,b,c,d,e,f,g,h,i,j);
}
}
}
}
}
}
}
}
}
}
}
FINAL UPDATE I have a confession to make. I gave up trying to get the code to work in obj-c and rewrote it in Python. It has now been running for a couple开发者_运维技巧 of hours, checked 1.2 billion of the 10^10 combinations, has not clagged up the system memory and on average is using 50% less CPU time than the obj-c code. I love the look of Cocoa apps and the creation of the UI is brilliant but for sheer workability, Python is hard to beat.
Python code looks like:
row0 = [164,116,106,76,122,46,109,86,7,134]
row1 = [70,170,108,25,182,77,134,192,60,26]
row2 = [14,108,140,130,90,46,6,154,168,90]
row3 = [138,48,130,127,54,2,112,78,76,98]
row4 = [86,65,110,22,64,82,46,62,146,94]
row5 = [70,194,20,152,76,162,54,98,122,50]
row6 = [91,0,116,230,32,138,203,175,104,88]
row7 = [68,222,87,124,99,209,28,147,108,72]
row8 = [51,85,74,40,132,98,118,159,70,44]
row9 = [30,122,92,190,8,77,152,7,106,70]
maxvalue = 0
flagmatrix = [0,0,0,0,0,0,0,0,0,0]
solutionmatrix = [0,0,0,0,0,0,0,0,0,0]
for a in range(0,10):
for b in range(0,10):
for c in range(0,10):
for d in range(0,10):
for e in range(0,10):
for f in range(0,10):
for g in range(0,10):
for h in range(0,10):
for i in range(0,10):
for j in range(0,10):
for z in range(0,10):
flagmatrix[z]=0
#This will clear the flag matrix
#Now load the matrix
flagmatrix[a]=1
flagmatrix[b]=1
flagmatrix[c]=1
flagmatrix[d]=1
flagmatrix[e]=1
flagmatrix[f]=1
flagmatrix[g]=1
flagmatrix[h]=1
flagmatrix[i]=1
flagmatrix[j]=1
sum=0
for flag in flagmatrix:
sum = sum+flag
if sum == 10:
print "solution found at ",a,b,c,d,e,f,g,h,i,j
solution = row0[a]+row1[b]+row2[c]+row3[d]+row4[e]+row5[f]+row6[g]+row7[h]+row8[i]+row9[j]
print "Solution = ", solution
if solution > maxvalue:
maxvalue = solution
solutionmatrix[1]=b
solutionmatrix[2]=c
solutionmatrix[3]=d
solutionmatrix[4]=e
solutionmatrix[5]=f
solutionmatrix[6]=g
solutionmatrix[7]=h
solutionmatrix[8]=i
solutionmatrix[9]=j
print "Current maxvalue = ", maxvalue
print "Final max value = ", maxvalue
print "Final solution matrix = ", solutionmatrix
Your immediate problem is nothing to do with the maximum depth of nested for loops, just basic Cocoa memory management. You create, and then accumulate millions of objects in the current AutoreleasePool.
For further info try http://developer.apple.com/library/mac/#documentation/Cocoa/Conceptual/MemoryMgmt/Articles/mmAutoreleasePools.html
In cases like this the overhead of using NSNumber instead of a regular int is considerable. You would be better off performance wise (if sticking with this algorithm) rewriting in C.
That's not to say you can't use Objective-C for this, you just have to understand the lifecycle of objects you create and not use up all available memory with what you intended to be temporary variables.
Required disclaimer: the algorithm is not a good one and should be improved, you should not in general rely on language features to make poor algorithms usable. That said:
The reason why the Python version runs your code better is because it is using garbage collection. After memory usage reaches a certain limit the Python system looks at the memory that has been allocated and releases for re-use memory that is no longer needed by your code.
Your Objective-C version is using manual memory management. In your case memory is being marked as "autorelease" which means it will be released (without any other explicit code) for re-use when your current event handling is finished - and in your code the whole loop is a single "chunk" (that's a technical term ;-)) and so no memory marked as "autorelease" is released for re-use.
Now Objective-C on Mac OS X (but not iOS) supports garbage collection. Go to your project settings, look for "Objective-C Garbage Collection" and set it to "Supported". Now run your code, it should perform as badly as the Python version, or maybe a lot better...
Ironically your algorithm, non-optimal as it is, does not appear to actually allocate a lot of memory; as others have pointed out NSNumber should only allocate one instance per actual numeric value. The poor memory-performance appears to be a side-effect of the way "autorelease" is working. Garbage collection should not suffer from that side-effect and so your code will probably run in a lot less memory and do little, if any, garbage collection.
I ran your code, and, within a few minutes, began to enter paging hell.
Now, this was in a command-line version of your program. I had removed all creation of temporary NSStrings and the NSLog for every test, and had not yet encountered the NSLog for a successful test. The only objects this version created were NSNumbers, and, as I mentioned in my comment on mustISignUp's answer, the NSNumber objects do not pile up because you only create two of them—NSNumber objects are interned, so just about every time you apparently create an NSNumber object, you are actually only reusing an object previously created.
So seeing your program consume a ton of memory was odd.
The next step when your program consumes a ton of memory is to run it under Instruments, using the Leaks template. That's what I did. I took a Heapshot every few seconds, and Instruments reported 5–12 MB of memory growth each time.
Looking at the contents of one of the Heapshots (showing what had been allocated since the previous one), I found that it was all non-object memory. Looking at the stack trace for one allocation, I found that it was allocated by… autorelease, called apparently directly from main.
Double-clicking on the main stack frame, it took me to one of your “creations” of an NSNumber object. From this, I inferred that although it reuses existing objects, it also retains and autoreleases them.
As documented, objects respond to autorelease by adding themselves to the autorelease pool. That's significant because the autorelease pool, at its heart, is basically a mutable array (that releases all of its contents when it gets drained). Ordinarily, this doesn't count for much because the total size of the objects far outweighs their displacement, so to speak, in the pool, but in your case, you have two objects that you were adding to the pool millions of times each over the life of the program.
The solution was to hoist the “creation” expressions out of the code into variable declarations:
NSNumber *zero = [NSNumber numberWithInt:0];
NSNumber *one = [NSNumber numberWithInt:1];
and replace them everywhere they'd formerly appeared with uses of the variables. The program's still dog slow, but memory usage is now flat.
I have no idea whether that's relevant to your problem, but maybe it is, and at any rate, it's a necessary improvement.
Also, NSLog writes to the system log, which goes to disk. Consider logging into an NSTextView instead, or even drawing the grid and its marked places in a custom view. You'll have to break up the code to not be a single long-running loop, but that's another necessary improvement anyway—it's something you'll need to learn anyway, and this is a very good practice case.
This is much related to the N-Queens-Problem (which also checks diagonals, so it will be more a N-Rook-Problem).
By all means, this heavy work shouldn't be done on the main thread (which will make the application unresponsive). You a background worker for this (or several, or GCD).
Algorithmically, there is probably lots of things to improve. First thing to come to mind is to check every new item as soon as it is placed, so that you don't have to do the inner loops at all.
Technically no restriction on the number of fors that I'm aware of - although other code structures might be easier.
![Interactive visualization of a graph in python [closed]](https://www.devze.com/res/2023/04-10/09/92d32fe8c0d22fb96bd6f6e8b7d1f457.gif)
加载中,请稍侯......
精彩评论