内存有效递归

我已经在C＃中编写了一个应用程序，用于生成可以以字母，数字和少数特殊字符组合存在的所有单词。内存有效递归

问题是，它不是内存有效的，因为它正在适应递归以及像List这样的一些集合。

有什么办法可以让它在有限的内存环境下运行？

Umair

来源

2010-07-28 Neutralizer

好吧，让我们看看你有什么.. – tzaman 2010-07-28 22:18:00

递归处理树木，图形时可以很整洁。 – 2010-07-28 22:23:29

@Hamish递归可以是整齐的，但不是在这个问题的背景下。直接递归可能需要大量堆栈空间和大量堆栈框架“推送和弹出”。这个网站的名称与此场景有关联... – 2010-07-28 22:44:34

将其转换为iterative function.

来源

2010-07-28 22:17:46

编写内存高效递归算法的关键是限制堆栈上的数据量。当你不能这样做时，唯一真正的解决方案是切换到迭代。 – ConsultUtah 2010-07-28 22:19:42

取决于。如果您使用堆栈空间来维护状态，只需切换到迭代不会有帮助。你必须以某种方式重构你的算法。如果它使用堆栈空间，因为你有一个尾部调用，编译器没有优化，那么你切换到迭代将做到这一点，但我会责怪编译器在这种情况下。 – Claudiu 2010-07-28 22:21:42

也同意。递归只在你的编译器被构建为优化它时才缩放（比如在面对尾递归时扔掉旧堆栈，即递归调用是函数的最后一件事，LISP例如真正欣赏） – Nicolas78 2010-07-28 22:22:36

那么，你显然不能存储在内存中的中间结果（除非你有某种荒谬的计算机在您的处置）;你将不得不将结果写入磁盘。

递归深度不是所考虑字符数量的结果 - 它取决于您愿意考虑的最大字符串长度。

例如，我安装了python 2.6.2，它的默认递归限制设置为1000.可以，我应该能够生成所有可能的1-1000长度的字符串，给定一个字符集在这个限制内（现在，我认为递归限制适用于总堆栈深度，所以实际限制可能小于1000）。

编辑（添加Python示例）： 下面的Python代码片段将产生你问什么（限制本身给定的运行栈限制）：

from string import ascii_lowercase 

def generate(base="", charset=ascii_lowercase): 
    for c in charset: 
     next = base + c 
     yield next 
     try: 
      for s in generate(next, charset): 
       yield s 
     except: 
      continue 

for s in generate(): 
    print s

一个基本上可以产生相同的在C＃中尝试/捕获StackOverflowException。当我输入这个更新时，脚本正在运行，咀嚼我的一个内核。但是，内存使用量不会超过7MB。现在，我只打印stdout，因为我对捕获结果不感兴趣，但我认为它证明了上述观点。）

补遗例如： 有趣注：查找运行的进程越近，蟒实际上是I /结合上述示例O操作。它只使用我的CPU的7％，而核心的其余部分绑定在我的命令窗口中显示结果。最小化窗口允许python爬到总CPU使用率的40％，这是在2核心机器上。

来源

2010-07-28 23:41:45

不幸的是C＃编译器不执行tail call optimization，这是你想在这种情况下发生的事情。 CLR支持它，kinda，但你不应该依赖它。

也许是左边的字段，但也许你可以在F＃中编写程序的递归部分？这样，您可以利用保证的尾部调用优化和重用C＃代码的位。虽然陡峭的学习曲线，F＃是这些组合任务更适合的语言。

来源

2010-07-28 23:52:22

还有一点需要考虑：当你连接或使用其他方法在C＃中生成一个字符串时，它占用了自己的内存并可能会停留一段时间。如果您生成数百万个字符串，您可能会注意到一些性能拖延。

如果你不需要保留你的许多字符串，我会看看是否有避免产生字符串。例如，也许你有一个字符数组，当你在字符组合中移动时你会不断更新字符数组，如果你将它们输出到一个文件中，你一次只能输出一个字符，所以你不必编译串。

来源

2010-07-29 15:15:25

呃...我不确定我是谁，但我得到了解决方案。我正在使用多个进程与用户和其他用户进行交互以查找单词组合。另一个过程找到5000个单词，保存并退出。通过WCF实现沟通。当进程退出时，这看起来相当不错=释放内存。

来源

2010-07-30 09:02:49 Neutralizer

内存有效递归

回答

相关问题