例如，我有一個new_strings_feed()每秒回傳一個字串串列的方法，例如：
1s: ["this", "is"]
2s: ["this", "was", "example"]
3s: ["this", "is", "example"]
4s: ["is", "example"]
5s: ["is", "an","example", "that"]
6s: ["an", "example", "that", "return", "strings"] #
我想第二次得到這個資訊，但沒有松散的過去資訊。例如，如果我們在 sec 6 并且我列印我的串列：
while(True):
refresh_my_list(new_strings_feed(), mylist)
print(mylist)
time.sleep(1)
所以執行期間的 mylist 值應該是：
1s: ["this", "is"]
2s: ["this", "was","example"]
3s: ["this", "is", "example"]
4s: ["this", "is", "example"]
5s: ["this", "is", "an", "example", "that"]
6s: ["this", "is", "an", "example", "that", "return", "strings"] #
我嘗試了不同型別的比較，但我無法解決。
有人建議我如何實作我的“reflesh_my_list”，記住正在接收子串列？
input和 的例子output：
input: ["this", "is"]
output: ["this", "is"]
input: ["this", "was", "example"]
output: ["this", "was","example"]
input: ["this", "is", "example"]
output: ["this", "is", "example"]
input: ["is", "example"]
output: ["this", "is", "example"]
input: ["is", "an", "example", "that"]
output: ["this", "is", "an", "example", "that"]
input: ["an", "example", "that", "return", "strings"]
output: ["this", "is", "an" "example", "that", "return", "strings"]
uj5u.com熱心網友回復：
append 方法就是你要找的，不知道這個“refresh_my_list”函式是做什么的，但如果你有一個這樣的串列：
sample_array = ["this", "is", "an" "example", "that", "return", "strings"]
import time
output_array=[]
for item in sample_array:
output_array.append(item)
print(output_array)
time.sleep(1)
這應該做你想做的:)
uj5u.com熱心網友回復：
這是一個使用特里樹來存盤先前輸入的解決方案。
不是在特里存盤字串，而是以相反的順序存盤字串串列，因為我們需要后綴匹配，而不是前綴匹配。
輸出與問題中的示例輸出相匹配，所以我認為這就是所要求的 - 如果不是，請告訴我。
請參閱代碼注釋以獲取解釋。
inputs = [
["this", "is"],
["this", "was", "example"],
["this", "is", "example"],
["is", "example"],
["is", "an", "example", "that"],
["an", "example", "that", "return", "strings"]
]
class Trie:
END = object() # marker object that represents end of a list
def __init__(self):
self.root = {}
def add(self, item):
"""
Add an item to the trie
:param item: the item to add
:return: None
"""
node = self.root
for x in item:
node = node.setdefault(x, {}) # either get the existing dictionary or create an empty one
node[self.END] = None # mark the end of the sequence
def search(self, item):
"""
Search of all items sequences that have been added to the trie that begin with `item`
:param item: the item to search for
:return: a generator that gives all matching sequences
"""
node = self.root
# find the node that contains all entries that begin with this prefix
for x in item:
if x in node:
node = node[x]
else:
return
# list all possibilities, excluding the common prefix
yield from self.__iter__(node)
def __iter__(self, node=None, prefix=()):
node = self.root if node is None else node
for k, v in node.items():
if k is self.END:
yield prefix
else:
yield from self.__iter__(node=v, prefix=prefix (k,))
def main():
trie = Trie()
for inp in inputs:
# simulate a received input
print(f'{inp=}')
out = inp
# first try to match the entire input, then all but the last item, then all but the last 2
# e.g. try ['an', 'example', 'that', 'return', 'strings'] - this isn't in the trie.
# then, try ['an', 'example', 'that', 'return'] - this also isn't in the trie
# then, try ['an', 'example', 'that'] - this matches ['this', 'is', 'an', 'example', 'that']
for i in reversed(range(len(inp))):
# search in trie
complete_options = list(trie.search(reversed(inp[:i 1])))
# if there is a match in the trie
if complete_options:
# find the best match
best_complete_option = max(complete_options, key=len)
# concatenate the extra part onto the beginning
out = list(reversed(best_complete_option)) inp
# stop looping
break
# add the result to the trie
trie.add(reversed(out))
print(f'{out=}')
if __name__ == '__main__':
main()
尋找每個輸入相匹配的時間復雜度是O(n^2 m)其中n是串列的長度和m為級聯的額外部分。這n^2是因為它在回圈中n多次迭代for i in reversed(range(len(inp)))，并且在回圈內進行搜索，即O(n). 還有將搜索結果轉換為串列并找到最長的一個 - 這可以通過將搜索方法更改為始終首先列出更長的結果并從生成器中獲取第一項來消除：
class Trie:
...
def __iter__(self, node=None, prefix=()):
node = self.root if node is None else node
for k, v in node.items():
if k is not self.END:
yield from self.__iter__(node=v, prefix=prefix (k,))
if self.END in node:
yield prefix
...
def main():
...
for inp in inputs:
...
for i in reversed(range(len(inp))):
# search in trie
complete_options = trie.search(reversed(inp[:i 1]))
try:
best_complete_option = next(complete_options)
out = list(reversed(best_complete_option)) inp
# stop looping
break
except StopIteration:
# there were no complete_options
pass
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/341264.html