我如何更新字符串列表与字符串的饲料每秒钟?

Question

例如，我有一个方法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"] #

我想得到这个信息非常快，但没有松散的过去的信息。例如，如果我们在第六节，我打印我的列表:

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"]

Answer 1

这是一个使用尝试来存储以前输入的解决方案。

不是在树中存储字符串，而是以相反的顺序存储字符串列表，因为我们需要后缀匹配，而不是前缀匹配。

输出与问题中的示例输出匹配，所以我认为这是所要求的-如果不是，请告诉我。

请参见代码注释。

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是因为它在for i in reversed(range(len(inp)))循环中对n进行了多次迭代，并在循环中进行了搜索，即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

Answer 2

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)

这应该做你想要的:)