提问人：iago-lito 提问时间：3/19/2020 更新时间：3/19/2020 访问量：661
使可变元素的排序列表保持最新
Keep sorted list of mutable elements up to date
问：
我可以在 python 中使用 or 对以前未排序的列表进行排序。sortedlist.sort
如果我希望我的列表在添加元素时保持排序，我可以使用模块中的 SortedList。sortedcontainers
但是，我发现没有现成的方法来保持此列表的排序，因为其中的元素会发生变化。
from sortedcontainers import SortedList
a = SortedList([], key=len) # sort elements by their length.
a.add([3,3,3]) # add in..
a.add([1]) # .. random..
a.add([2,2]) # .. order.
print(a) # [[1], [2, 2], [3, 3, 3]] still sorted, okay.
# Now, mutate one element.
a[0].append(1)
a[0].append(1)
print(a) # [[1, 1, 1], [2, 2], [3, 3, 3]] not sorted, not okay.
我了解不负责跟踪其中包含的项目的更改并保持排序最新。SortedList
那么，如何更新排序呢？
是否有我可以发送的消息，以便它知道我在索引处进行了更改，并重新考虑项目的位置，例如 .
是否有其他数据结构专门用于此？
我应该自己编写并优化它吗？
我应该解决它吗？
此解决方法与专用解决方案相比如何？a00a.update_sorting_of(0)a.add(a.pop(0))
我可以有把握地假设，在我的情况下，变异没有引发其他元素的任何变化（否则我只会整个事情）。a[0]a.sort(key=len)
答：
2赞
Reti43
3/19/2020
#1
没有机制可以做你想做的事。即使你在改变一个元素后求助于一个列表，它也会有 O（nlogn） 的复杂性。但是因为在幕后使用平分，所以它只有 O（logn）。因此，最好按照您的建议执行操作，即删除要更改的元素并重新添加它。如果有一个函数可以做你想要的，它可能会在幕后做类似的事情，因为我想不出比平分更好的方法来放置一个排序顺序可能已经改变的元素。add()
def mutate_element(sortedlist, index, value):
temp = sortedlist.pop(index)
temp.append(value)
sortedlist.add(temp)
您还可以进一步推广各种列表更改方法的功能。例如，与 相同。getattr(mylist, 'append')mylist.append
评论
0赞
iago-lito
3/19/2020
这基本上围绕着“消息”。我知道没有更好的方法可以做到这一点，而且它已经很好了。谢谢:)a.add(a.pop(0))
1赞
Reti43
3/19/2020
@iago-lito，我看到了这一点，但我不清楚你是在总结方法的同时遗漏了关键步骤，还是没有意识到这并不完全符合你想要的，所以我发布了答案。答案的要点，虽然没有明确说明，但由于诉诸列表比重新输入突变元素更昂贵，即使有一种方法可以做你想做的事，它可能会在幕后做一些类似的事情。a.add(a.pop(0))
0赞
iago-lito
3/19/2020
你明白我的意思:)我也同意，一个专用的、最优的方法基本上会做类似的事情。更进一步，你认为做和做之间会有区别吗？那将是一个偷偷摸摸/危险的区别，所以最好确定 X）temp=a.pop(0); temp.append(1); a.add(temp)a[0].append(1); a.add(a.pop(0))
1赞
Reti43
3/19/2020
没有区别，因为当您再次调用时，元素已更改为新大小。但就我个人而言，我认为第一种方法的意图更清楚。顺便说一句，如果你正在处理很多元素，你只需要删除并重新添加一个元素，如果.否则，就地修改不会影响排序顺序。但这是特定于排序功能的，所以我省略了它。a.add()index + 1 < len(a) and len(a[index]) == len(a[index+1])len
评论
a.add(a.pop(0))__getitem__append