Cocoa - 嵌套循环的最大深度？
我正在尝试写一个算法，目的是在一个10x10的网格中找到选择10个值的可能方案。要求是没有两个值可以在同一行或同一列。总共有10!种组合（大约360万种）。
我最开始的算法使用了10个嵌套的for循环，简单地检查每一种可能的10个方格组合。当我在我的MacBook上运行这个程序时，花了很多很多分钟，所以为了打发时间，我把每次测试的结果记录到控制台，这样我就可以看到测试数量在不断增加。
问题是程序运行到第714271次测试时就卡住了。这种情况是可以重复出现的。
我猜这可能是内存的问题，某个计数器的值超过了它允许的最大值，但我在网上查这个数字时没有找到任何有意义的信息。
代码大概是这样的：
-(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);
}
}
}
}
}
}
}
}
}
}
}
最终更新 我得坦白一下。我放弃了在obj-c中让代码正常工作，改成用Python重写了。现在它已经运行了几个小时，检查了12亿个组合（总共10^10种），没有占用系统内存，而且平均使用的CPU时间比obj-c代码少了50%。我喜欢Cocoa应用的外观，UI的创建也很棒，但就可操作性而言，Python真是无与伦比。
Python代码大概是这样的：
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
4 个回答
需要说明的是：这个算法并不好，需要改进。一般来说，不应该依赖语言特性来让糟糕的算法变得可用。不过，话说回来：
Python版本运行你的代码更好的原因是它使用了垃圾回收。当内存使用达到一定限度时，Python系统会检查已经分配的内存，并释放那些你的代码不再需要的内存，以便重新使用。
而你的Objective-C版本使用的是手动内存管理。在你的代码中，内存被标记为“自动释放”，这意味着当你当前的事件处理完成后，这部分内存会被释放（不需要其他明确的代码）。但是在你的代码中，整个循环被视为一个“块”（这是一个技术术语；-）），所以没有标记为“自动释放”的内存被释放以供重新使用。
现在，Objective-C在Mac OS X（但不包括iOS）上支持垃圾回收。你可以去项目设置中，找到“Objective-C垃圾回收”，然后将其设置为“支持”。现在运行你的代码，它的表现应该和Python版本一样糟糕，或者可能会好很多……
讽刺的是，尽管你的算法不够优化，但似乎并没有实际分配很多内存；正如其他人所指出的，NSNumber每个实际的数字值只应该分配一个实例。糟糕的内存性能似乎是“自动释放”工作方式的副作用。垃圾回收不应该受到这个副作用的影响，因此你的代码可能会在使用更少的内存的情况下运行，并且几乎不需要进行垃圾回收。
你现在遇到的问题和嵌套的for循环最大深度没有关系，主要是关于Cocoa的内存管理。你创建了很多对象，然后把它们都放在当前的自动释放池里，结果累积了几百万个对象。
想了解更多信息，可以查看这个链接：http://developer.apple.com/library/mac/#documentation/Cocoa/Conceptual/MemoryMgmt/Articles/mmAutoreleasePools.html
在这种情况下，使用NSNumber而不是普通的int会消耗更多的资源。如果你继续使用这个算法，性能上你最好用C语言重写。
这并不是说你不能用Objective-C来做这个，只是你需要理解你创建的对象的生命周期，不要把本来打算临时使用的变量占用掉所有可用的内存。
我运行了你的代码，几分钟后就开始陷入了分页的麻烦。
这是在你程序的命令行版本中。我去掉了所有临时 NSString 的创建和每次测试的 NSLog，也还没有遇到成功测试的 NSLog。这个版本只创建了 NSNumber 对象，正如我在对 mustISignUp 的回答评论中提到的，NSNumber 对象不会堆积，因为你只创建了两个——NSNumber 对象是被管理的，所以每次你看似创建一个 NSNumber 对象时，实际上只是重复使用之前创建的对象。
所以看到你的程序消耗大量内存是很奇怪的。
当你的程序消耗大量内存时，下一步就是用 Instruments 工具运行它，选择 Leaks 模板。我就是这么做的。我每隔几秒拍一次 Heapshot，Instruments 报告每次内存增长 5-12 MB。
查看其中一个 Heapshot 的内容（显示自上一个 Heapshot 以来分配的内存），我发现这些都是非对象内存。查看一个分配的堆栈跟踪，我发现它是通过… autorelease 分配的，显然是直接从 main 调用的。
双击 main 的堆栈帧，它带我到了你“创建”的一个 NSNumber 对象。从这里我推断，虽然它重用了现有对象，但它也会保留并自动释放它们。
正如文档所述，对象通过 autorelease 方法将自己添加到自动释放池中。这很重要，因为自动释放池本质上就是一个可变数组（当它被清空时会释放所有内容）。通常，这并不算什么，因为对象的总大小远远超过它们在池中的占用空间，但在你的情况下，你有两个对象在程序运行期间被添加到池中数百万次。
解决方案是把“创建”表达式提取到变量声明中：
NSNumber *zero = [NSNumber numberWithInt:0];
NSNumber *one = [NSNumber numberWithInt:1];
然后在它们之前出现的地方用变量替换。程序仍然很慢，但内存使用现在保持平稳。
我不知道这是否与你的问题有关，但也许是的，无论如何，这是一个必要的改进。
另外，NSLog 会写入系统日志，这会占用磁盘空间。考虑改为写入 NSTextView，或者在自定义视图中绘制网格及其标记的位置。你需要把代码拆分，不要让它成为一个长时间运行的循环，但这也是另一个必要的改进——这是你需要学习的东西，而且这是一个很好的实践案例。