logo标签列表

Cocoa - 嵌套循环的最大深度是多少？

pythonobjective-ccocoa
3
我正在尝试编写一个算法，用于在10x10网格中选择10个数的所有可能解决方案。不能有两个值共享同一行或列。共有10！种组合（略大于3,600,000）。
我的初始算法使用了10个嵌套的for循环，并简单地检查了每个可能的10个方块的组合。当我在我的MacBook上尝试运行应用程序时，需要多次多次的计算，为了缓解无聊，我将每个测试记录到控制台中，这样我就可以观察到测试结果的增加。
问题在于，该应用程序一直运行到测试编号714,271，然后就会冻结。这个结果是重复出现的。
我认为这是内存问题，在某些计数器超过其允许的最大值，但当我谷歌这个数字时，它没有任何意义。
代码如下:
-(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
1
也许如果您描述一下您的最终目标（10x10网格，什么是“解决方案”等），我们可以建议比蛮力更好的方法。有许多不同类型的搜索算法（通常就是您正在进行的搜索），每种算法都针对特定类型的场景进行了优化。这些是基本且至关重要的编程概念，您至少应该知道它们的存在，以备不时之需（就像现在-您真的需要它们）。 - Joshua Nozzi
1
没有看到代码，我们最多只能告诉你“你做错了” ;) - Ken Aspeslagh
感谢您查看。再次强调一下，我正在尝试定位10个单元格的组合，使得任何两个单元格都不共享同一行或列。选择10个单元格（每行一个）而没有限制的总组合数是10^10。允许的解决方案数量是10！我只需要能够识别它们。 - Andrew H
当你在调试器中停止了冻结的程序，你看到了什么？ - Peter Hosey
此外，当您说“选择10个值”时，您是否只指位置？您的代码仅标记网格中的位置，并且仅使用值0和1；它似乎没有放置10个不同的值。 - Peter Hosey
据我所知，这种编程语言并没有最大嵌套深度限制，但是Xcode有：http://imgur.com/q25Wl - Peter Hosey
4个回答
2
你的直接问题与嵌套for循环的最大深度无关，而是基本的Cocoa内存管理。你创建了数百万个对象并在当前自动释放池中累积这些对象。
更多信息请参见http://developer.apple.com/library/mac/#documentation/Cocoa/Conceptual/MemoryMgmt/Articles/mmAutoreleasePools.html 在这种情况下，使用NSNumber而不是常规int的开销相当大。如果坚持使用此算法，从性能上讲，最好重写为C语言。
这并不意味着你不能使用Objective-C来解决这个问题，只是你必须理解你所创建对象的生命周期，并不要使用所有可用内存来存储你打算作为临时变量的东西。
谢谢您。到目前为止，我的Cocoa编程使我避免了内存管理的问题。如果我继续采用这种“蒸汽锤”方法，是否有一种方法可以在进行操作时释放有问题的对象，或者我需要重新考虑我的策略？ - Andrew H
提问者代码创建的NSNumber对象总数为10（如果实际填入10个不同的值，则是10）。 NSNumber按值进行内部化；这是一个未记录的好处，但仍然很好，特别是在这种情况下。临时字符串才是真正堆积起来的东西；使用-[NSString appendFormat：]可能会解决这个问题。 - Peter Hosey
2
必要的免责声明：该算法并不好，应该加以改进。通常情况下，您不应该依靠语言特性来使不良算法可用。话虽如此：

Python版本运行您的代码更好的原因是它使用了垃圾回收。当内存使用量达到某个限制时，Python系统会查看已分配的内存，并释放不再需要的内存以供您的代码重复使用。

您的Objective-C版本正在使用手动内存管理。在您的情况下，内存被标记为“自动释放”，这意味着当您当前的事件处理完成时，将无需任何其他显式代码即可将其释放以供重复使用。在您的代码中，整个循环是一个单一的“块”（这是一个技术术语;-)），因此没有标记为“自动释放”的内存可以释放以供重复使用。

现在，Mac OS X上的Objective-C（但不是iOS）支持垃圾回收。转到您的项目设置，查找“Objective-C Garbage Collection”，并将其设置为“Supported”。现在运行您的代码，它应该像Python版本一样或者表现得更好...

具有讽刺意味的是，您的算法虽然不够优化，但似乎并没有实际分配大量内存；正如其他人指出的那样，NSNumber应该仅为每个实际数字值分配一个实例。不良的内存性能似乎是“自动释放”方式的副作用。垃圾回收不应受此副作用的影响，因此您的代码可能会在更少的内存中运行，并且几乎不进行任何垃圾回收。

1

我运行了你的代码，几分钟后就开始陷入分页地狱。

这是在你程序的命令行版本中。我已经删除了所有临时NSString的创建和每个测试的NSLog，并且还没有遇到成功测试的NSLog。这个版本只创建了NSNumbers，正如我在mustISignUp的回答中提到的，NSNumber对象不会堆积，因为你只创建了两个NSNumber对象，NSNumber对象是内部化的，所以每次你看起来创建NSNumber对象时，实际上只是重新使用先前创建的对象。

所以看到你的程序消耗大量内存是奇怪的。

当你的程序消耗大量内存时，下一步是使用Instruments运行它，使用Leaks模板。那就是我做的。我每隔几秒钟拍摄一个Heapshot，Instruments报告每次增长5-12 MB的内存。

查看其中一个Heapshot的内容（显示自上一个Heapshot以来分配的内容），我发现它全部都是非对象内存。查看一个分配的堆栈跟踪，我发现它是由...autorelease分配的，显然直接从main调用。

双击 main 栈帧，它将带我到你创建的 NSNumber 对象之一。从这里，我推断出虽然它重用现有对象，但也会保留并自动释放它们。

如文档所述，对象通过响应 autorelease 将自己添加到 autorelease 池中。这很重要，因为 autorelease 池在其核心上基本上是一个可变数组（当它被排空时会释放其所有内容）。通常，这并不重要，因为对象的总大小远远超过了它们在池中的位移，但在你的情况下，你有两个对象，在程序的生命周期内每个对象都被添加到池中数百万次。

解决方案是将“创建”表达式提升到代码中的变量声明中：

NSNumber *zero = [NSNumber numberWithInt:0];
NSNumber *one = [NSNumber numberWithInt:1];

并且用变量的方式替换它们在先前出现的所有位置。程序仍然很慢，但内存使用现在是平稳的。

我不知道这是否与您的问题有关，但也许有，无论如何，这是必要的改进。

此外，NSLog 写入系统日志，而系统日志会写入磁盘。考虑将日志记录到 NSTextView 中，甚至可以在自定义视图中绘制网格及其标记位置。你需要将代码分解成不是单一长时间运行的循环，但这是另一个必要的改进——这是你必须学习的东西，而这是一个非常好的实践案例。

哇！这真是一份详细的回复。感谢您的所有努力。我必须承认，您所做的大部分工作都超出了我的理解范围。我要说的是，虽然实现了向NSTextView记录日志，但构建GUI并不是首要考虑的问题，因此我使用了NSLog来使代码正常运行。我不知道它会消耗资源。我会继续努力编写我的代码。 - Andrew H
NSLog在普通使用中不会“消耗资源”，但如果你往其中倾倒了成千上万条日志信息，就会拖垮syslogd。 - Peter Hosey
0

这与N皇后问题有很大关系（它也检查对角线，所以更像是N车的问题）。

无论如何，这项繁重的工作都不应在主线程上完成（这会使应用程序无响应）。 您可以为此使用后台工作者（或多个，或GCD）。

从算法上讲，可能有很多需要改进的地方。首先想到的是，只要放置新项目，就立即检查每个新项目，这样您根本不需要执行内部循环。

我不知道有任何关于for数量的技术限制 - 尽管其他代码结构可能更容易。

谢谢。...线程...我必须承认，我还没有达到那个编程水平。也许有一天。 - Andrew H
而且 - 正如其他人正确指出的那样 - 您的问题与大量自动释放的对象有关。 - Eiko
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接