在python中，怎樣計算list的累積和？不能用loop或者library的function。

01-02

一道面試題，功能類似np中的cumsum()，但是不能用library或者loop，大家有什麼思路么？

不管是要求哪一種語言，這種類型的題目只能顯示出題人的低能。

無論用的是lambda還是map還是reduce還是eval還是別的什麼花哨玩意，本質到後面就是for loop。那些用reduce的答案，對不起題目禁止你使用庫函數，reduce你得自己寫。我倒要看看不用循環你怎麼寫reduce。說用遞歸的回去好好補補課，對不支持尾遞歸的絕大多數語言而言，沒哪個智商正常的程序員會用遞歸對付長度不定的容器類，分分鐘爆棧。

之所以說出題人低能，是因為出題的自己都沒有搞清楚「不能用loop」是什麼意思，考點在哪。用庫函數的reduce可不可以？如果可以，那就是用了loop，只不過你沒親自寫，庫函數幫你寫好了，你調用一下而已。以Python為例，官方內置reduce函數是這麼寫的：

def reduce(function, iterable, initializer=None): it = iter(iterable) if initializer is None: try: initializer = next(it) except StopIteration: raise TypeError("reduce() of empty sequence with no initial value") accum_value = initializer for x in it: accum_value = function(accum_value, x) return accum_value

你說倒數第三行是啥？

如果說調用而沒有親自寫for/while就算「沒有用loop」，那這不叫面試，叫玩文字遊戲。買兇殺人難道不算殺人？如果不可以，那要怎麼辦？用遞歸？腦子清楚的應聘者知道對未知長度的數組使用遞歸一定會有棧溢出的問題，這不是一個合格的解決方案。如果出題的接受了使用遞歸的面試者，恭喜你，你成功地招聘了一個不知道棧溢出是什麼意思的菜鳥。

其他奇技淫巧當然有。你可以無賴湊一個string出來"f" + "o" + "r"然後用eval。或者，你也可以玩out of the stack execution來避免爆棧的問題，也就是開一個線程做一次步進，再開個新線程做下一個步進。最蠢的，你還可以硬寫嘛，array[0], array[1]... 一直寫到int的上限。這些技巧有一個共同特點：實際開發中，如果誰這麼做，我一定炒他魷魚。

&>&>&> L = [1, 2, 3, 4, 5] &>&>&> reduce(lambda x, y: x + [x[-1] + y], L, [0])[1:] [1, 3, 6, 10, 15]

然而這是奇技淫巧。由於每累加一個數字，就要重新創建一個列表，所以複雜度是平方級的。

如果並不限定用one-liner，那麼可以把上述答案中的lambda換成如下函數：

def f(x,y): x.append(x[-1] + y) return x

append操作只是偶爾會給列表重新分配空間，每次append的均攤複雜度是常數，故reduce的複雜度為線性。但如果這麼寫，代碼就不比老老實實用for循環短多少了……

樓上諸位已經說得相當好了——不用循環、list comprehension 和 builtin function 的情況下，肯定只有遞歸。但是在這樣的前提下，假如輸入非常大，如何遞歸才能不爆棧呢？看起來在 CPython 3 下，__del__ 可以做到這一點。

編輯：用 traceback 可以看到 __del__ 裡面的 frame depth 總是低於五十幾，這是如何做到的呢？user defined instance 的 __del__ 具體的實現在 Objects/typeobject.c 的 subtype_dealloc 里。從中可以看出，CPython 3 有一個 trash can 機制，其一就是要保證 __del__ 不會 nest 太深（上面有一行 `#define PyTrash_UNWIND_LEVEL 50`，這也正好是我們觀測到的數據），否則的話將下一個需要 __del__ 的 object 放到 state-&>trash_delete_later 這個 linked list 里去，等目前所有的 __del__ 都結束之後再來將這個 tstate-&>trash_delete_later 清空，我們最核心的循環正是在清空的過程中做的。

class K(Exception): pass


def _tc(f, *xs): raise K(f, xs)
def run_tc(f, *xs):

    def keep(): pass

    r = None

    class R:

        def __del__(self):

            nonlocal f, xs, r

            try:

                r = f(*xs)

            except K as k:

                (f, xs) = k.args

                R()

    R()

    keep()

    return r
def foldl(f, z, xs, ix=0):

    try:

        x = xs[ix]

    except:

        return z

    else:

        return _tc(foldl, f, f(z, x), xs, ix + 1)
def tc(f):

    def f_(*xs):

        return run_tc(f, *xs)

    return f_
@tc

def cum_sum(xs):

    x, *xs = xs

    def f(z, x):

        z.append(z[-1] + x)

        return z

    return foldl(f, [x], xs)
print("cum_sum -&> %s" % cum_sum([1, 2, 3, 4, 5]))

# 值得一提的是，這樣寫我們並不會 stack overflow: def _sum_tail(n, s=0): if n &<= 0: return s else: return _tc(_sum_tail, n - 1, s + n) sum_tail = tc(_sum_tail) print("sum_tail -&> %s" % sum_tail(1000000))

這題目比「茴香豆的『茴』字有幾種寫法」略高一籌。

L = [1,2,3,4,5] t_sum = 0 def plus(x): global t_sum t_sum += x return t_sum

print map(lambda x: plus(x), L)

可惜python的+=不是個表達式

eval("+".join([str(i) for i in L]))

列表解析算循環不

reduce(lambda x,y : x+y, L,0)

既然不能用循環，那麼就用遞歸。

上面有很多大神用了reduce之類的東西，不過在我這種渣渣看來是很晦澀的東西。

def cumsum(L): #if L"s length is equal to 1 if L[:-1] == []: return L

ret = cumsum(L[:-1]) ret.append(ret[-1] + L[-1]) return ret

OUTPUT:

&>&>&> l = [1, 3, 6, 10, 15] &>&>&> cumsum(l) [1, 4, 10, 20, 35]

第一行判斷數組長度是否為1，不用len是因為怕len裡面有循環

以上

l = [...]

[sum(l[:n+1]) for n in range(len(l))]

看到很多題主提到reduce，稱其本質不過是個for loop，並且說用遞歸會爆棧，甚至搬出python的源代碼證明自己觀點，我只想一一點上反對。的確，reduce可以通過for loop實現，但是reduce的本質，實際上是通過divide and conquer來達到一個O(log(n))級別的並行時間複雜度(我們學校管他叫Span，但是我並不知道標準的中文翻譯)，這才是使map reduce在並行計算框架下如此必要的原因，絕非簡單炫技。

Reduce函數的定義如下：

其本質操作，是在最後一個遞歸情況下，將其拆成左右兩部分，分別進行遞歸，從而達到並行計算的目的。因此遞歸的層數是log(n)。

至於python源碼的實現，反正python都這麼爛了也無所謂再爛這麼點吧【笑，而且python本來就不是高性能語言，更加不會面向並行計算，這點性能損耗對python的設計目標來說也不是什麼大問題。但是python這麼寫，絕不代表reduce本身就應該如此，如果說出這道面試題的公司本來就要做大量並行計算，我覺得出這道題本身是無可厚非的，或者說，如果連reduce都認為只是一個簡單的for loop，那他在並行計算的道路上肯定是走不了多遠的。當然，如果考官自己也不是做這塊的人，只想單純刁難的話，那就和諸位誰說的一樣，和叫你寫四種「茴」是沒什麼區別的。

Reference: https://drive.google.com/file/d/0B4z2gzEmkDDCa1UyMmh3aktzVGs/view

知乎竟然把這作為第一個問題推薦給我……好吧，鑒於沒有一個正確答案，我就回答一下。

根據題主的要求，首先是求cumsum，大部分答案實現的是sum，不對。唯一實現對了的，可惜出現了for循環。

以下是我的方案：

map(sum, map(lambda x: map(lambda y:L[y], x), map(range, range(1, len(L) + 1))))

解釋：

L = [1,3,5] numpy.cumsum(L) = [1,4,9]

# the simplest idea is: map(sum, [ L[0:1], L[0:2], L[0:3] ]) # so, first need to generate ranges map(range, range(1, len(L) + 1)) # -&> [[0], [0,1], [0,1,2]] # after we have list of ranges, need to select elements by ranges map(lambda r : map(lambda i : L[i], r), ranges) # done.

希望可以看到更優美的答案。

更新：

沒想到這麼快就可以看到一個更短的正確答案 @王贇 Maigo 。在王兄答案里，其實列表並不是不斷的增長，而是每次都創建了新的列表。受啟發，想到一個內存效率更高的方案：

def f(x, y): x[y] = x[y-1] + y return x

reduce(f, L, L+[0])[:-1]

雖然滿足題目要求，但不如王兄答案簡潔。

再更新：

上面我的第二個答案是錯誤的，請參考評論。

按照上面思路正確的實現是：

def f(x, y): x[y[0]] = x[y[0]-1] + y[1] return x

L = [233,666,1024] reduce(f, enumerate(L), L+[0])[:-1]

但這樣就更加難看了一些。

下午早超市裡買蔬菜的時候想到這題，我突然好奇哪個答案是最快的……於是簡單做了一個benchmark,代碼如下：

import numpy as np import time


N = 1000
def f0(x, y):

    x[y[0]] = x[y[0]-1] + y[1]

    return x
def f1(x,y):

  x.append(x[-1] + y)

  return x
L = range(1000)
t = time.time()

for i in xrange(1000):

    reduce(f0, enumerate(L), L+[0])[:-1]

print time.time() - t
t = time.time()

for i in xrange(N):

    reduce(f1, L, [0])[1:]

print time.time() - t
t = time.time()

for i in xrange(N):

    [sum(L[:i]) for i in xrange(1, len(L) + 1)]

print time.time() - t
t = time.time()

for i in xrange(N):

    np.cumsum(L)

print time.time() - t

# results 0.240000009537 0.153000116348 3.97200012207 0.0450000762939

上述結果里，注意到這裡最慢的其實就是list comprehension，我在Python 2.7下測試的，估計在3.0下也會有類似結果。

我不理解累積和是啥意思。。。

猜測是想要reduce？

reduce(lambda x,y: x+y, L) 這樣就可以了，後面的0不是必須的，如果沒記錯的話……

=======================更新===================================

上面很多人用for loop 的 list comprehension，這我覺得應該不符合要求，如果一定要用eval的話，

我猜下面這樣的寫法也是可以的？

eval( "+".join( map( str,a ) ) )

會用reduce的話，map應該也會吧？

不好意思，有sum函數

面試官很有可能是希望你對"遞歸過程"有更深的了解，在此基礎上你可以跟他對尾遞歸的優化談笑風生。

——SICP

如果那麼說的話就是無解，不定長的迭代必有循環，要麼就是有特殊的演算法，吾等不知而已

import numpy as np

def cumsum(list):

return np.array(list).cumsum().tolist()

Julia:

&>&> L = [1, 2, 3, 2, 2] #表示無序，而不是順序

&>&> map(x-&>mapreduce(y-&>y,+,L[1:x]),collect(1:1:length(L)))

沒搞明白要考什麼

讓在下來回答??.????

剛接觸python不久，不用循環的話可以用這樣簡單的遞歸方法解決：（如有不妥請多指教）

主要是利用join，append方法和eval函數，遞歸一次用pop方法去掉最後一個元素指導x列表剩一個元素，這樣我們得到的我y累積和列表是反過來的，用reverse方法反序就好了。

函數奉上：

def test(x,y):

seq="+"

x=map(str,x)

y.append(eval(seq.join(x)))

x.pop()

if len(x)==0:

y.reverse()

else:

test(x,y)

#!/usr/bin/env python # -*- coding: utf-8 -*-


import timeit
L = range(100)[::3]
def test1():

    return reduce(lambda l, e: l + [l[-1]+e], L, [0])[1:]
def test2():

    return reduce(lambda l, e: l.append(l[-1]+e) or l, L, [0])[1:]

class consumor(object): def __init__(self, nums): self.nums = nums self.length = len(nums) def __iter__(self): self.cursor = 0 self.lastsum = 0 return self def next(self): if self.cursor &< self.length: cur_val = self.nums[self.cursor] self.cursor += 1 self.lastsum += cur_val return self.lastsum else: raise StopIteration() def test3(): return list(consumor(L)) print test1()==test2()==test3() print timeit.timeit(test1) print timeit.timeit(test2) print timeit.timeit(test3)

執行結果

jyf@brix:~/hack/python$ python consum.py True 9.76863884926 5.53098297119 14.5979530811