Cocoa嵌套循环的最大深度？

Question

我试图写一个算法，找到从10x10网格中选择10个值的可能的解决方案。没有两个值可以共享同一行或列。有10个！略高于3600000。在

我的初始算法使用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亿个，没有占用系统内存，平均来说比obj-c代码少使用50%的CPU时间。我喜欢Cocoa应用程序的外观，UI的创建也非常出色，但是对于纯粹的可操作性，Python是很难击败的。在

Python代码如下所示：

^{pr2}$

Answer 1

您当前的问题与嵌套for循环的最大深度无关，只是基本的Cocoa内存管理。在当前的AutoreleasePool中创建并累积数百万个对象。在

有关详细信息，请尝试http://developer.apple.com/library/mac/#documentation/Cocoa/Conceptual/MemoryMgmt/Articles/mmAutoreleasePools.html

在这种情况下，使用NSNumber而不是常规int的开销是相当大的。在C语言中进行重写，在性能方面（如果坚持这种算法的话）会更好

这并不是说不能使用Objective-C来实现这一点，您只需了解所创建对象的生命周期，而不是将所有可用的内存都用于临时变量。在

Answer 2

必需免责声明：该算法不是一个好的算法，应该加以改进，您一般不应该依赖语言特性来使较差的算法可用。上面说：

Python版本之所以能更好地运行代码，是因为它使用了垃圾回收。当内存使用量达到某个限制后，Python系统会查看已分配的内存，以及释放代码不再需要的内存。在

您的Objective-C版本使用的是手动内存管理。在您的例子中，内存被标记为“autorelease”，这意味着当您当前的事件处理完成时，它将被释放（没有任何其他显式代码）以供重用—在您的代码中，整个循环是一个单独的“chunk”（这是一个技术术语；-），因此不会释放标记为“autorelease”的内存以供重用。在

现在macosx（但不是iOS）上的Objective-C支持垃圾收集。转到项目设置，查找“Objective-C垃圾回收”并将其设置为“支持”。现在运行您的代码，它的性能应该和Python版本一样糟糕，或者可能更好。。。在

具有讽刺意味的是，您的算法虽然不是最优的，但似乎并没有实际分配大量内存；正如其他人所指出的那样，NSNumber应该只为每个实际数值分配一个实例。糟糕的记忆性能似乎是“自动释放”工作方式的副作用。垃圾收集不应该受到这种副作用的影响，因此您的代码可能会在更少的内存中运行，并且很少（如果有的话）进行垃圾收集。在

Answer 3

我运行了你的代码，几分钟内，就开始进入寻呼地狱。在

现在，这是你程序的命令行版本。我删除了所有临时nsstring的创建和每个测试的NSLog，还没有遇到成功测试的NSLog。这个版本创建的唯一对象是NSNumbers，而且，正如我在mustISignUp的回答中所提到的，NSNumber对象不会堆积起来，因为您只创建了其中两个NSNumber对象，所以几乎每次您明显创建NSNumber对象时，实际上您只是重用以前创建的对象。在

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

当程序消耗大量内存时，下一步是使用Leaks模板在Instruments下运行它。我就是这么做的。我每隔几秒钟就进行一次扫描，仪器显示每次内存增长5-12 MB。在

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

双击main堆栈框架，我就看到了您对NSNumber对象的一个“创建”。由此，我推断，虽然它重用现有对象，但它也保留并自动释放它们。在

As documented，对象通过将自身添加到自动释放池来响应autorelease。这一点很重要，因为autorelease池的核心基本上是一个可变数组（当它被耗尽时，它会释放它的所有内容）。通常，这并不重要，因为对象的总大小远远超过了它们的位移，可以说，在池中，但是在你的例子中，你有两个对象，你在程序的生命周期中，每一个对象都被添加到池中数百万次。在

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

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

用变量代替它们以前出现过的任何地方。程序仍然很慢，但内存使用率现在是持平的。在

我不知道这是否与你的问题有关，但也许是，而且无论如何，这是一个必要的改进。在

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