相关疑难解决方法(0)

在讨论算法的时间复杂度时,"恒定摊还时间"是什么意思？

我正在尝试计算一些代码.首先我用了一个时间装饰器:

#!/usr/bin/env python

import time
from itertools import izip
from random import shuffle

def timing_val(func):
    def wrapper(*arg, **kw):
        '''source: http://www.daniweb.com/code/snippet368.html'''
        t1 = time.time()
        res = func(*arg, **kw)
        t2 = time.time()
        return (t2 - t1), res, func.__name__
    return wrapper

@timing_val
def time_izip(alist, n):
    i = iter(alist)
    return [x for x in izip(*[i] * n)]

@timing_val
def time_indexing(alist, n):
    return [alist[i:i + n] for i in range(0, len(alist), n)]

func_list = [locals()[key] for key in locals().keys()
             if callable(locals()[key]) and key.startswith('time')]
shuffle(func_list)  # …

假设您要编写一个产生对象列表的函数,并且事先知道此n列表的长度.

在python中,列表支持O(1)中的索引访问,因此可以预先分配列表并使用索引访问它而不是分配空列表并使用该append()方法.这是因为如果空间不足,我们可以避免扩展整个列表的负担.

如果我正在使用python,那么在任何情况下表演都不是那么相关,但是预先分配列表的更好方法是什么？

我知道这些可能的候选人:

• [None] * n →分配两个列表
• [None for x in range(n)]- 或者xrange在python2中→构建另一个对象

一个明显优于另一个？

如果我们是这样的话n = len(input)怎么办？既然input已经存在,[None for x in input]会有更好的表现[None] * len(input)吗？