Sunday, September 07, 2008

程序开发中避免堆栈溢出的新思路(stackless python)

一、单递归调用堆栈溢出
让我们在python中写一个递归函数来计算阶乘:
def fac(x):
  if n == 0:return 1
  else:return x*fac(x-1)

熟悉编程的人马上就能看出来程序的问题,当x的数值超过一定值的时候,
就会堆栈溢出。

解决办法便是不使用递归函数来实现这个要求,而使用FP风格的编程方法:

reduce(lambda n m :n*m,range(1,x+1))

这里是从左往右依次相乘,没有使用递归(操作系统没有创建栈来保持函数调用状态)。


二、循环递归调用堆栈溢出:

def func1():
  print 'func1'
  func2()

def func2():
  print 'func2'
  func1()

func1()

这样的程序也很明显会堆栈溢出,解决办法是使用并发处理里的微进程技术:

import stackless
channel_1 = stackless.channel()
channel_2 = stackless.channel()
def func1():
  while channel_1.receive():
   print 'func1'
   channel_2.send('heelo,func2,it's your turn')

def func2():
  while channel_2.receive():
   print 'func1'
   channel_1.send('heelo,func1,it's your turn')


stackless.tasklet(func1)()
stackless.tasklet(func2)()
stackless.tasklet(channel_1.send)('go')
stackless.run()

stackless中用channel来使微进程通讯,两个微进程(任务)互相使用channel来调用对方,
真各个过程中并未使用递归调用的函数,也不存在压栈出栈的操作。

Tags: 溢出, python