<pre><code>mylists = [ [1,3,5,7], [2,4,7,8], [11,15], [20] ]
import time
def timeit(f):
def wrapper(*args, **kw):
t = time.time()
res = f(*args, **kw)
print "%s took %s" % (f.func_name, time.time() - t)
return res
return wrapper
# merge two given lists
def merge(l, r):
if len(l) == 0:
return r
if len(r) == 0:
return l
if l[0] <= r[0]:
return [l[0]] + merge(l[1:], r)
else:
return [r[0]] + merge(l, r[1:])
def merge2(x,y):
if len(x) == 0:
return y
if len(y) == 0:
return x
#pop the lower one between the two biggest items
last = y.pop() if x[-1] < y[-1] else x.pop()
merged = merge2(x,y)
merged.append(last)
return merged
def merge3(xs, ys):
ms = []
i = 0
j = 0
while i < len(xs) and j < len(ys):
if xs[i] <= ys[j]:
ms.append(xs[i])
i = i + 1
else:
ms.append(ys[j])
j = j + 1
while i < len(xs) and j == len(ys):
ms.append(xs[i])
i = i + 1
while i == len(xs) and j < len(ys):
ms.append(xs[i])
j = j + 1
return ms
# divide and conquer
def lmerge(lists, m):
if len(lists) <= 1:
return lists
mid = len(lists) / 2
llists = lmerge(lists[:mid], m)
rlists = lmerge(lists[mid:], m)
# the bottom merge will have a list of list
if isinstance(llists[0], list):
llists = llists[0]
if isinstance(rlists[0], list):
rlists = rlists[0]
return m(llists, rlists)
@timeit
def a():
print lmerge(mylists, merge)
@timeit
def b():
print lmerge(mylists, merge2)
@timeit
def c():
print lmerge(mylists, merge3)
@timeit
def d():
print sorted(reduce(lambda x,y: x + y, mylists))
a()
b()
c()
d()
</code></pre>
<hr/>
^{pr2}$
<p>有点搞不清为什么merge3的提升和索引错误?在</p>
<p>merge,merge2,merge3应该有相同的输出(至少在我的脑海中是这样的),所以我不明白为什么它会引发索引错误,因为它适用于merge和merge2</p>
<p>编辑:如果有更好的合并算法,我可以有一个更好的合并算法吗?在</p>