Tuesday, December 23, 2008

python提取列表里重复数据性能优化

列表内容限于文本或者数字。

def foo(alist):
    """
        extract the repeat item out of a list
    """
    d = dict()
    sd = dict()
    for i in alist:
        if id(i) not in d:
            d[id(i)] = ''
        else:
            sd[i] = ''
    return sd.keys()

因为在python里相同的串或者数字为同一个对象,所以使用id来作为hash算法,放到字典里去做对比,而不是直接对比内容本身,因而提高一定的性能。

Tags: python, 算法


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