最近，我正在嘗試撰寫一個函式，以在任意深度嵌套序列中的任何位置查找原始值，并回傳到達那里的路徑（按順序作為每個連續嵌套序列中的索引串列）。我遇到了一個非常意外的障礙：該函式正在尋找結果，但沒有回傳它！該函式不是正確的輸出，而是不斷回傳應該只在嘗試查找不在序列中的專案時才產生的輸出。
通過在函式中的不同點放置print陳述句，我發現問題在于，在實際找到該專案的遞回呼叫之后，其他沒有找到該專案的人也在回傳，并且顯然比找到它的時間晚. 這意味著最終結果將從“成功”值重置為“失敗”值，除非“成功”值是最后遇到的事情。
我嘗試通過在函式中添加一個額外的條件來解決這個問題，以便在成功的情況下盡早回傳，試圖搶占導致最終結果不正確的額外的、不必要的遞回呼叫。現在，這就是我遇到問題根本原因的地方：
沒有辦法事先知道哪個遞回呼叫（如果有的話）會找到該專案，一旦其中一個找到它，它就無法與其他人“交流”！
我能想出的避免這個更深層次問題的唯一方法是完全重構函式，當且僅當遇到“成功”條件時，使用“成功”輸出“設定”自身外部的變數。外部全域變數開始設定為“未能按順序查找專案”值，并且除了“成功”情況外不會重置。所有其他遞回呼叫只是return不做任何事情。這看起來非常丑陋和低效，但它確實有效。
第一次嘗試
# ITERATIVE/RECURSIVE SEQUENCE TRAVERSER (First Attempt)
# Works on 'result1' but not on 'result2'
# Searches for 'item' in sequence (list or tuple) S, and returns a tuple
# containing the indices (in order of increasing depth) at which the item
# can be found, plus the depth in S at which 'item' was found.
# If the item is *not* found, returns a tuple containing an empty list and -1
def traverse(S, item, indices=[], atDepth=0):
# If the sequence is empty, return the 'item not found' result
if not S:
return ([], -1)
else:
# For each element in the sequence (breadth-first)
for i in range(len(S)):
# Success condition base case: found the item!
if S[i] == item:
return (indices [i], atDepth)
# Recursive step (depth-first): enter nested sequence
# and repeat procedure from beginning
elif type(S[i]) in (list, tuple):
return traverse(S[i], item, indices [i], atDepth 1)
# Fail condition base case: searched the entire length
# and depth of the sequence and didn't find the item, so
# return the 'item not found' result
else:
print("We looked everywhere but didn't find " str(item) " in " str(S) ".")
return ([], -1)
L = [0, 1, 2, [3, (4, 5, [6, 6.25, 6.5, 6.75, 7])], [[8, ()]], (([9], ), 10)]
result1 = traverse(L, 7)
result2 = traverse(L, 9)
print("-------------------------------------------")
print(result1)
print("-------------------------------------------")
print(result2)
第二次嘗試
# ITERATIVE/RECURSIVE SEQUENCE TRAVERSER (Second Attempt)
# Does not work on either test case
# Searches for 'item' in sequence (list or tuple) S, and returns a tuple
# containing the indices (in order of increasing depth) at which the item
# can be found, plus the depth in S at which 'item' was found.
# If the item is *not* found, returns a tuple containing an empty list and -1
def traverse(S, item, indices=[], atDepth=0, returnValue=None):
# If the sequence is empty, return the 'item not found' result
if not S:
print("Sequence S is empty.")
return ([], -1)
# --- ATTEMPTED FIX:
# If the item is found before the end of S is reached,
# do not perform additional searches. In addition to being
# inefficient, doing extra steps would cause incorrect false
# negatives for the item being in S.
# --- DOES NOT WORK: the underlying issue is that the multiple recursive
# calls generated at the same time can't communicate with each other,
# so the others don't 'know' if one of them already found the item.
elif returnValue:
print("Inside 'elif' statement!")
return returnValue
else:
# For each element in the sequence (breadth-first)
for i in range(len(S)):
# Success condition base case: found the item!
if S[i] == item:
# Return the depth and index at that depth of the item
print("--- Found item " str(item) " at index path " str(indices) " in current sequence")
returnValue2 = (indices [i], atDepth)
print("--- Item " str(item) " is at index path " str(returnValue2) " in S, SHOULD RETURN")
#return returnValue2 # THIS DIDN'T FIX THE PROBLEM
#break # NEITHER DID THIS
# Recursive step (depth-first): enter nested sequence
# and repeat procedure from beginning
elif type(S[i]) in (list, tuple):
# CANNOT USE 'return' BEFORE RECURSIVE CALL, as it would cause any items
# in the outer sequence which come after the first occurrence of a nested
# sequence to be missed (i.e. the item could exist in S, but if it is
# after the first nested sequence, it won't be found)
traverse(S[i], item, indices [i], atDepth 1, returnValue) # CAN'T USE 'returnValue2' HERE (out of scope);
# so parameter can't be updated in 'if' condition
# Fail condition base case: searched the entire length
# and depth of the sequence and didn't find the item, so
# return the 'item not found' result
else:
print("We looked everywhere but didn't find " str(item) " in " str(S) ".")
return ([], -1)
L = [0, 1, 2, [3, (4, 5, [6, 6.25, 6.5, 6.75, 7])], [[8, ()]], (([9], ), 10)]
result1 = traverse(L, 7)
result2 = traverse(L, 9)
print("-------------------------------------------")
print(result1)
print("-------------------------------------------")
print(result2)
第三次也是最后一次嘗試——作業，但不理想！
# ITERATIVE/RECURSIVE SEQUENCE TRAVERSER (Third Attempt)
# This 'kludge' is ** HIDEOUSLY UGLY **, but it works!
# Searches for 'item' in sequence (list or tuple) S, and generates a tuple
# containing the indices (in order of increasing depth) at which the item
# can be found, plus the depth in S at which 'item' was found.
# If the item is *not* found, returns nothing (implicitly None)
# The results of calling the function are obtained via external global variables.
# This 3rd version of 'traverse' is thus actually a void function,
# and relies on altering the global state instead of producing an output.
# ----- WORKAROUND: If the result is found, have the recursive call that found it
# send it to global scope and use this global variable as the final result of calling
# the 'traverse' function.
# Initialize the global variables to the "didn't find the item" result,
# so the result will still be correct if the item actually isn't in the sequence.
globalVars = {'result1': ([], -1), 'result2': ([], -1)}
def traverse(S, item, send_output_to_var, indices=[], atDepth=0):
# If the sequence is empty, return *without* doing anything to the global variable.
# It is already initialized to the "didn't find item" result.
if not S:
return
else:
# For each element in the sequence (breadth-first)
for i in range(len(S)):
# Success condition base case: found the item!
if S[i] == item:
# Set the global variable to the index path of 'item' in 'S'.
globalVars[send_output_to_var] = (indices [i], atDepth)
# No need to keep on doing unnecessary work!
return
# Recursive step (depth-first): enter nested sequence
# and repeat procedure from beginning
elif type(S[i]) in (list, tuple):
# Don't use 'return' before the recursive call, or it will miss items
# in the outer sequence after a nested sequence is encountered.
traverse(S[i], item, send_output_to_var, indices [i], atDepth 1)
# Fail condition base case: searched the entire length
# and depth of the sequence and didn't find the item.
else:
# Return *without* setting the global variable, as it is
# already initialized to the "didn't find item" result.
return
L = [0, 1, 2, [3, (4, 5, [6, 6.25, 6.5, 6.75, 7])], [[8, ()]], (([9], ), 10)]
traverse(L, 7, 'result1')
traverse(L, 9, 'result2')
print("-------------------------------------------")
print(globalVars['result1'])
print("-------------------------------------------")
print(globalVars['result2'])
我想知道我是否遺漏了什么，實際上有一種方法可以在不使用外部變數的情況下完成這項作業。最好的解決方案是以某種方式“關閉”所有其他遞回呼叫，一旦它們中的一個回傳成功結果，但我不相信這是可能的（我很想錯了！）。或者可能是某種“優先佇列”延遲return“成功”案例遞回呼叫（如果存在）直到所有“失敗”案例遞回呼叫都回傳之后？
我看了這個類似的問題：Recursively locate nested dictionary contains a target key and value 但是雖然ggorlen在這里接受的答案https://stackoverflow.com/a/59538362/18248018解決了 OP 的問題，甚至提到了似乎是這樣的問題問題（“匹配的結果沒有正確地傳遞到呼叫堆疊”），它是為執行特定任務而定制的，并且沒有提供我正在尋找的更一般情況的洞察力。
uj5u.com熱心網友回復：
您的第一次嘗試幾乎是完美的，唯一的錯誤是您回傳在當前深度搜索第一個串列/元組的結果，無論是否item找到。相反，您需要檢查一個肯定的結果，并且只有當它是一個時才回傳。這樣，您就可以不斷迭代當前深度，直到找到item或根本找不到它。
所以你需要改變：
return traverse(S[i], item, indices [i], atDepth 1)
類似于：
t = traverse(S[i], item, indices [i], atDepth 1)
if t != ([], -1):
return t
完整代碼：
def traverse(S, item, indices=[], atDepth=0):
# If the sequence is empty, return the 'item not found' result
if not S:
return ([], -1)
else:
# For each element in the sequence (breadth-first)
for i in range(len(S)):
# Success condition base case: found the item!
if S[i] == item:
return (indices [i], atDepth)
# Recursive step (depth-first): enter nested sequence
# and repeat procedure from beginning
elif type(S[i]) in (list, tuple):
t = traverse(S[i], item, indices [i], atDepth 1)
if t != ([], -1):
return t
# Fail condition base case: searched the entire length
# and depth of the sequence and didn't find the item, so
# return the 'item not found' result
else:
print("We looked everywhere but didn't find " str(item) " in " str(S) ".")
return ([], -1)
兩個測驗用例的輸出：
>>> traverse(L, 7)
([3, 1, 2, 4], 3)
>>> traverse(L, 9)
We looked everywhere but didn't find 9 in [6, 6.25, 6.5, 6.75, 7].
We looked everywhere but didn't find 9 in (4, 5, [6, 6.25, 6.5, 6.75, 7]).
We looked everywhere but didn't find 9 in [3, (4, 5, [6, 6.25, 6.5, 6.75, 7])].
We looked everywhere but didn't find 9 in [8, ()].
We looked everywhere but didn't find 9 in [[8, ()]].
([5, 0, 0, 0], 3)
正如@FreddyMcloughlan 指出的那樣，注意atDepth只是回傳串列的長度減去1。因此您可以從函式呼叫中洗掉該引數并使用：
def traverse(S, item, indices=[]):
# If the sequence is empty, return the 'item not found' result
if not S:
return ([], -1)
else:
# For each element in the sequence (breadth-first)
for i in range(len(S)):
# Success condition base case: found the item!
if S[i] == item:
return (indices [i], len(indices))
# Recursive step (depth-first): enter nested sequence
# and repeat procedure from beginning
elif type(S[i]) in (list, tuple):
t = traverse(S[i], item, indices [i])
if t != ([], -1):
return t
# Fail condition base case: searched the entire length
# and depth of the sequence and didn't find the item, so
# return the 'item not found' result
else:
print("We looked everywhere but didn't find " str(item) " in " str(S) ".")
return ([], -1)
uj5u.com熱心網友回復：
我會以不同的方式撰寫它，使用遞回呼叫的結果來決定是立即回傳還是繼續搜索。如果找到該專案，我的版本將回傳一個非空的索引串列，None否則。
def traverse(S, item):
for i, element in enumerate(S):
if element == item:
return [i]
if type(element) in (list, tuple):
if indices := traverse(element, item):
indices.insert(0, i)
return indices
您的兩次測驗的結果（在線試用！）：
[3, 1, 2, 4]
[5, 0, 0, 0]
我沒有傳入串列，而是僅從專案的位置向后構建串列（或者如果它不存在，那么我根本不構建任何串列）。盡管插入 at0使其成為二次方，但作業量要少得多，盡管比復制切片要快得多。如果您希望它是線性的，您可以將此遞回函式包裝在另一個函式中，并讓遞回函式附加索引并讓包裝函式反轉串列，然后再將其回傳給原始的外部呼叫者。如果需要，包裝函式還可以讓您將“非空串列或None”結果轉換為其他內容（例如具有深度的對）。
uj5u.com熱心網友回復：
由于在評論中討論了將函式重構traverse為迭代而不是遞回，為了完整起見，這里也是該版本：
# Iterative-only version of the same function from the question
def traverse(S, item):
indices = []
sequence = S
depth = 0
# By definition, if the sequence is empty, you won't find any items in it.
# Return the 'item not found' result.
if not S:
return ([], -1)
else:
# You have to start somewhere :D
indices.append(0)
while depth > -1:
# Go back up one level once the end of a nested sequence is reached.
while indices[depth] == len(sequence):
depth -= 1
# If the depth ever gets below 0, that means that we've scanned
# the entire length of the outermost sequence and not found the
# item. Return the 'failed to find item' result.
if depth == -1:
return ([], -1)
# Remove the entry corresponding to index in the innermost
# nested sequence we just exited
indices.pop()
# Reset 'sequence' using the outermost sequence S and the indices
# computed so far, to get back to the sequence which contained
# the previous one
sequence = S
for i in range(len(indices) - 1):
sequence = sequence[indices[i]]
indices[depth] = 1
# And return to the top of the outer 'while' loop to re-check
# whether to go down another level
continue
# Success: found the item at depth 'depth', in sequence 'sequence',
# at index 'indices[depth]` inside that sequence. Return 'indices'
# and 'depth'.
if sequence[indices[depth]] == item:
return (indices, depth)
# Recursion replacement: enter the nested subsequence and increase the depth
# as long as the nested subsequence is not empty. If it is empty, treat it
# as if it were a non-sequence type.
elif (type(sequence[indices[depth]]) in (list, tuple)) and (sequence[indices[depth]]):
sequence = sequence[indices[depth]]
depth = 1
indices.append(0)
# The item being compared is not a sequence type and isn't equal to 'item', so increment
# the index without increasing the depth
else:
indices[depth] = 1
# If all of S has been searched and item was not found,
# return the 'failed to find item' result
return ([], -1)
L = [0, 1, 2, [3, (4, 5, [6, 6.25, 6.5, 6.75, 7]), 7.5], [[8, ()]], (([9], ), 10)]
# Demonstrating the function's use: search for numbers from 0 to 10 in list L,
# in increments of 0.5
for i in range(21):
outputString = "Looking for " (str(i/2) if (i/2 % 1) else str(int(i/2))) " in L: "
indices, depth = traverse(L, i/2)
if indices:
print(outputString "found at depth " str(depth) " by index path " str(indices))
else:
print(outputString "Not found.")
我聽說迭代演算法比遞回演算法更快，所以我嘗試使用time.time(). 對于所有 3 個，我使用了相同的“忙碌作業”測驗，如下所示：
L = [0, 1, 2, [3, (4, 5, [6, 6.25, 6.5, 6.75, 7]), 7.5], [[8, ()]], (([9], ), 10)]
startTime = time.time()
for i in range(1000):
for j in range(21):
traverse(L, j/2)
finishedAt = time.time()
print("[WHICH VERSION] took " str(finishedAt - startTime) " seconds")
并得到了這些結果：
對于應用了尼克修復的原始遞回函式：
Original recursive version took 0.14863014221191406 seconds
對于凱利的遞回版本：
Quadratic recursive version took 0.11344289779663086 seconds
對于迭代版本：
Iterative version took 0.1890261173248291 seconds
正如我所料，Kelly 的版本比原來的功能更快，它具有我原來的功能沒有的優化。我還沒有實作帶有反轉串列的外包裝函式的線性版本，但我希望這會更快。
不幸的是，迭代版本似乎實際上比沒有優化的遞回函式的原始版本慢，所以我想我會把它帶到代碼審查站點，看看它可以改進的地方......
參考文獻：帶有錯誤修復的原件：請參閱尼克的答案： https ://stackoverflow.com/a/72180834/18248018
Kelly的遞回版本： https ://stackoverflow.com/a/72189848/18248018
迭代版本：見上文
uj5u.com熱心網友回復：
您需要隨時堆疊索引，并為遞回函式分配成功標志。當您執行遞回呼叫時，您推送新索引。當函式回傳時，如果失敗，則彈出并繼續搜索，如果成功，則只回傳成功。最后，堆疊將是空的或充滿解決方案。
堆疊可以是全域變數，也可以作為引數傳遞。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/472653.html