我正在尝试编写一种算法来定位从10×10网格中选择10个值的可能解决方案.没有两个值可以共享同一行或列.有10个！组合(刚刚超过3,600,000).
我的初始算法使用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中重写它.它已经运行了几个小时,检查了10 10个组合中的12亿个,没有对系统内存进行分类,平均使用的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
解决方法:
我运行了你的代码,并在几分钟内开始进入分页地狱.
现在,这是您的程序的命令行版本.我已经为每次测试删除了所有临时NSStrings和NSLog的创建,并且还没有遇到NSLog以进行成功的测试.这个版本创建的唯一对象是NSNumbers,正如我在关于mustISignUp的回答的评论中提到的那样,NSNumber对象没有堆积,因为你只创建了两个 – NSNumber对象被实现了,所以几乎每次你显然创建一个NSNumber对象,实际上只是重用以前创建的对象.
因此,看到你的程序消耗大量的内存是奇怪的.
当程序消耗大量内存时,下一步是使用Leaks模板在Instruments下运行它.这就是我做的.我每隔几秒就拍一次快照,仪器每次报告5-12 MB的内存增长.
查看其中一个快照的内容(显示自上一个快照以来分配的内容),我发现它都是非对象内存.查看一个分配的堆栈跟踪,我发现它是由… autorelease分配的,显然直接从main调用.
双击主堆栈框架,它将我带到了NSNumber对象的“创建”之一.从这一点,我推断,虽然它重用现有的对象,但它也保留并自动释放它们.
As documented,对象通过将自己添加到自动释放池来响应自动释放.这很重要,因为自动释放池的核心基本上是一个可变数组(在排出时释放所有内容).通常情况下,这并不重要,因为对象的总大小远远大于它们的位移,可以说,在池中,但在你的情况下,你有两个对象,你在池中添加了数百万次该计划的生命.
解决方案是将代码中的“创建”表达式提升为变量声明：
NSNumber *zero = [NSNumber numberWithInt:0];
NSNumber *one = [NSNumber numberWithInt:1];
并且在以前出现的各个变量的使用中替换它们.程序仍然很慢,但内存使用率现在持平.
我不知道这是否与你的问题有关,但也许是,无论如何,这是一个必要的改进.
此外,NSLog写入系统日志,该日志将转到磁盘.请考虑登录到NSTextView,甚至在自定义视图中绘制网格及其标记的位置.你必须将代码分解为不是一个长时间运行的循环,但这仍然是另一个必要的改进 – 无论如何你需要学习它,这是一个非常好的练习案例.