我想把兩個長度不同的串列中的每一個其他元素合并成一個串列。我不允許使用內置函式 zip，必須使用遞回。
從 print(zippa([1, 3, 5], [ 2, 4, 6, 8, 10]) 的結果應該是。 [1, 2, 3, 4, 5, 6, 8, 10]/code>.
這是我目前的代碼：
這是我目前的代碼。
def zippa（l1, l2）。
if len(l1) == 0:
return l2[0] zippa(l1,l2[1:] )
elif len(l2) == 0:
return l1[0] zippa(l1[1:], l2)
elif len(l1) ==0 and len(l2) == 0:
return 0: return
else:
return zippa(l1[1:0],l2) zippa(l1,l2[1:0] )
我不明白如何將這些值弄回一個串列中。
elif的順序是否重要？
uj5u.com熱心網友回復：
我不允許使用內置函式
zip，必須使用遞回。
這是很不幸的。你的教授或導師（抱歉，假設這是一個學術專案；如果不是，同樣的情緒也適用）正在強迫你錯誤地應用遞回。這就像試圖用一瓶香檳酒而不是滅火器來滅火。當你完成這門課的時候，請使用內置程式和迭代！
一般來說，迭代幾乎總是 Python 中對串列進行操作的正確工具。還有一些問題，遞回實際上是合適的，比如遍歷一棵樹，因為遞回的步驟將問題分解為一個次線性的因素。這里并沒有發生分裂和征服的情況。
為什么遞回不能替代迭代的一些原因：
sys.setrecursionlimit是一個不安全的黑客。
有些語言支持尾部呼叫優化，自然適合撰寫這樣的演算法，但是Python 并不是其中之一
。話雖如此，但我知道這是一個教學練習，所以讓我們一起玩，并學習一些關于遞回的知識。
在深入研究之前，我還想提供一些一般的編程提示。
當你在演算法上遇到困難時，試著簡化問題。看看你能否合并兩個長度相等的串列，然后，一旦成功，就添加串列長度不同的額外要求。這將消除對一個串列為空而另一個不為空的檢查，一般來說，這將使問題更容易掌握。當你去解決完整的問題時，你已經擁有了最小的子問題的作業代碼，以及你從解決較小的問題空間中獲得的經驗和模式。
這里的代碼看起來就像你跳到了前面，在沒有測驗的情況下就寫了出來，并且做出了一系列的決定和假設，而這些決定和假設單獨來看并沒有意義。采取更小的步驟。
列印（或使用除錯器）以檢查每一幀的值。在小的例子上解決演算法問題。
重要的閱讀。Eric Lippert - 如何除錯小程式.
。讓我們來檢查一下代碼中的一些小問題，并建立起更大的問題。
elif之類的順序是否重要？
如果分支條件都是不相干的，那么順序就不重要了，例如：
如果分支條件都是不相干的，那么順序就不重要了。
if foo == "a"/span>: return 0: return
if foo == "b"/span>: return 1: 鈾?
if foo == "c"/span>: return 2
由于foo不可能同時是"a"、"b"和"c"，這些分支是互斥的。當你能得到它時，這是一個很好的簡化假設（上面的代碼可以被重構為一個表格查詢，完全洗掉條件鏈）。
但是如果你有依賴性的檢查，例如
if len(l1) ==0:
pass # l1必須是空的；l2可能是也可能不是。
elif len(l2) == 0。
pass # l2必須是空的，并且l1已知是不空的。
# 否則將采取`len(l1) == 0`分支。
elif len(l1) ==0 and len(l2) == 0:
pass # unreachable, we've already covered cases。
# 其中一個或另一個是空的。
那么順序確實很重要。應該首先檢查兩個都是空的情況（你可以簡單地使用if lst:和if not lst:來Python地檢查它們的空性）。
考慮其中一個串列為空的情況：
if len(l1) == 0:
return l2[0] zippa(l1,l2[1:] )
在這一點上，你可以直接 回傳 l2 -- 當一個串列為空時，你需要做的是回傳非空的那個串列，而不是逐個切分。由于你的分支的順序，l2并不保證有一個元素 -- 它很可能是空的。
接下來，代碼
elif len(l1) == 0 and len(l2) == 0:
return 0 # ?!
有一個不一致的型別。我們試圖回傳一個串列，所以兩個空串列的基本情況被合并為一個空串列，而不是整數0。這應該是return []，所以呼叫者在兩個串列上使用 來連接它們，而不是[] 0，這會引發一個TypeError。一個型別化的語言不會讓你這樣寫，即使在一個動態型別化的語言中，混合型別通常也是一種反模式，即使它可以作業。
在主要的遞回案例代碼中，分片l1[1:0]總是給出一個空串列。將問題分解成一個小塊，并在副本中進行嘗試，以測驗我們的假設，我們看到：
[1,2,3] [1: 0]
[]
很明顯，這不是你的本意。看起來你想在這里對 "交替 "模式進行編碼，所以你可能只是想把第一個元素作為一個串列砍掉：
[1,2,3] [0: 1]
[1] 。
[1,2,3] [：1]
[1]
其次，我不清楚zippa(l1[:1],l2) zippa(l1,l2[:1])模式如何運作。我們有一個無限回圈，因為第一個元素一旦出現，就不會被任何邏輯洗掉。對于線性串列演算法來說，產生1個以上的遞回呼叫并合并結果是沒有必要的。在一次呼叫中合并兩個串列中的每一個元素似乎是最簡單的，在遞回中沒有任何規則說你不能這樣做。
回到切分問題上，這是不必要的二次復雜性 -- 大量的額外作業只是為了將演算法塞進遞回作業中。我們可以通過在遞回呼叫中傳遞一個索引作為第三個引數來解決復雜性問題和切片問題。這可以是一個默認引數，也可以在內部函式或輔助函式中添加。
作為最后一個優化點，它也使代碼更加簡單：串列上的每一個 運算子都會分配一個全新的串列！如果我們在每一幀上都這樣做，那么我們的代碼就會更簡單。如果我們在每一幀上都這樣做，我們又回到了二次方的復雜性。如果要將合并串列用于任何非瑣碎的目的，那么它必須只涉及恒定數量的分配（最好是一個）。這可以通過在遞回呼叫中傳遞單個結果串列來實作，并在第一次呼叫中分配一次。
下面是代碼：
def merge_iterables（a, b, i=0, result=None）。)
if 結果是 None。
結果 = []
if i < len(a) and i < len（b）:
result.append(a[i])
result.append(b[i])
merge_iterables(a, b, i 1, result)
else:
result.extend(a[i:])
result.extend(b[i:])
return result
如果你不喜歡將這些引數暴露給呼叫者，可以使用一個內部函式或輔助函式，典型的遞回：
def merge_iterables（a, b）。
結果 = []
def merge（i=0）。
if i < len(a) and i < len（b）:
result.append(a[i])
result.append(b[i])
merge(i 1)
else:
result.extend(a[i:])
result.extend(b[i:])
合并()
return result
注意，雖然我在做切片，但這是在一次性的基本情況下，所以這是恒定的復雜性（無論如何，其中一個或兩個切片是空的）。你可以使用一個傳統的range回圈來避免這些分配，但這是一個不成熟的優化。
雖然這不是你任務的一部分，但是像這樣的演算法應該可以推廣到任何數量的串列。通過添加一個回圈，這很容易：
def merge_iterables（*its）。
結果 = []
def merge（i=0）。
for x in its:
if i < len（x）。
result.append(x[i])
if any(i < len(x) for x in its) 。
merge(i 1)
合并()
return result
這里的時間和空間復雜度是O(nm)。
最后，生成器是處理像這樣的可迭代演算法的一種Pythonic方法。itertools使用生成器來處理所有的事情，效仿它是很好的。生成器給了呼叫者最大的靈活性：他們可以使用相同的演算法來合并，比如說，一個可迭代的前半部分，或者以一種記憶體效率高的方式，隨著時間的推移，懶散地進行合并（這些用例是你希望你的演算法使用恒定空間的部分動機！）
def merge_iterables（*its）。
def merge(i=0) 。
for x in its:
if i < len（x）。
yield x[i] 。
if any(i < len(x) for x in its) 。
yield from merge(i 1)
yield from merge()
if __name__ == "__main__"/span>:
print(list(merge_iterables([1,2], [4, 5,6,7], "a", "xyz") )
# => [1, 4, 'a', 'x', 2, 5, 'y', 6, 'z', 7]/span>
說了這么多，對于遞回來說，這仍然是一個臆造的、糟糕的用例（如果有任何疑問的話，可以在一個 1000 元的串列上試試），所以你可能想看看我在經典主題 以交替方式結合兩個串列的神話式方法？中建議的問題解決方案。
讓我們以該答案中的一些代碼和本答案中的代碼以及這個其他答案中給出的二次解決方法為基準
。import argparse
import copy
import dis
import inspect
import random
import sys
import timeit
from itertools import zip_longest
sys.setrecursionlimit(1350) # 只是為了測驗。
def merge_pythonic（*its）。
return [x for y in zip_longest(*its) for X in y if x is not None ]
def merge_iterables（*its）。
結果 = []
def merge（i=0）。
for x in its:
if i < len（x）。
result.append(x[i])
if any(i < len(x) for x in its) 。
merge(i 1)
合并()
return result
def zippa（*its）。
if len(its) == 0:
return []
head_list, *rest_its = its
if head_list:
head, *rest = head_list
return [head] zippa(*rest_its, rest)
else:
return zippa(*rest_its)
if __name__ == "__main__"/span>:
parser = argparse.ArgumentParser()
parser.add_argument("-n", type=int, default=1300)
parser.add_argument("-m"/span>, type=int, default=1300)
parser.add_argument("--trials", type=int，default=1000)
parser.add_argument("-dis", action="store_true")
args = parser.parse_args()
n = args.n
m = args.m
trials = args.tries
namespace = dict(its=[隨機。 sample(range(n), k=n) for _ in range（m）]
funcs_to_test = [x for x in locals().values()
if callable(x) and x.__module__ == __name__ ]
print(f"{'-'/span> * 30}
n = {n}, {trials} 審判
{'-'/span> * 30}
")
for func in funcs_to_test:
fname = func.__name__
fargs = ", ".join(inspection.signature(func).parameters)
stmt = f"{fname}（{fargs}）"。
setup = f "from __main__ import {fname}"
time = timeit.timeit(sttmt, setup, number=trials, globals=namespace)
print( inspect.getsource(globals().get(fname))
if args.dis:
dis.dis(globals() .get(fname))
print(f "time (s) => {'%.16f' % time})
{'-' * 30 }
")
即使有一個不幸的限制，即我們不能使用比一千多個元素更大的測驗（唉！遞回！），結果也很明顯：內置程式粉碎了遞回方法，二次元并沒有像預測的那樣擴展，即使是在微小的輸入上（現實世界的可迭代元素往往是幾十萬、幾百萬或幾十億或更多）：
------------------------------
n=1300，m=1300，1000次試驗
------------------------------
def merge_pythonic(*its):
回傳 [x for y in zip_longest(*its) for x in y if x is not None]
時間（s）=> 0.4278396000000000
------------------------------
def merge_iterables(*its):
結果 = []
def merge(i=0):
for x in its:
if i < len(x):
result.append(x[i])
if any(i < len(x) for x in its):
merge(i 1)
合并()
回傳結果
時間（s）=> 4.4487939000000001
------------------------------
def zippa(*its):
if len(its) == 0:
回傳 []
head_list, *rest_its = its
如果 head_list:
head, *rest = head_list
回傳 [head] zippa(*rest_its, rest)
否則。
回傳zippa(*rest_its)
時間（s）=> 40.0880948000000004
------------------------------
uj5u.com熱心網友回復：
處理串列遞回的一個經典方法是分割出串列的頭部，然后對其余部分進行處理。這是你在函式式語言中隨處可見的一種模式，它使遞回成為一等公民。在 Python 中它不是一等公民，但是你仍然可以使用 Python 來學習這些技術。
在這里我們做了一個可以壓縮任何數量的串列的函式。這很方便，因為一旦你用完了短的串列，你可以繼續呼叫它，直到沒有更多的串列，而不需要大量的 if/else。
def zippa（*lists）。
if len(lists) == 0:
return [] 。
head_list, *rest_lists = lists
if head_list:
head, *rest = head_list
return [head] zippa(*rest_lists, rest)
else:
return zippa(*rest_lists)
print(zippa([1, 3, 5], [2, 4, 6, 8, 10] ）。)
這個任務中唯一真正復雜的是你要處理多個串列。但是想法是一樣的，每個呼叫負責獲取第一個串列，然后從串列中獲取第一個元素。然后用遞回的結果回傳該元素。
這是在遞回程序中通過旋轉串列來實作的。通過最后傳入原始的第一個串列的其余部分。zippa(*rest_lists, rest)
這與一個精心選擇的基本案例一起，允許你傳遞任何數量的串列，這反過來又使代碼更簡單。你不需要處理索引或輔助引數。
# works with a single list。
print(zippa([1, 3, 5] )
# [1, 3, 5]/span>
# or multiple:
print(zippa([1, 3, 5], [ 2, 4, 6, 8, 10] , [0, 0, 0, 0])
# [1, 2, 0, 3, 4, 0, 5, 6, 0, 8, 0, 10]/span>
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/319334.html
標籤：
上一篇：堆疊中的方法呼叫如何被執行-遞回
下一篇：無法從空值讀取作業表范圍