python - 保持可变元素的排序列表是最新的

Question

我可以使用sorted或list.sort在Python中对之前未排序的列表进行排序。

如果我希望列表在添加元素时保持排序，我可以使用 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不负责跟踪其包含的项目的更改并保持排序最新。

那么我该如何更新排序呢？
有消息可以发给a所以它知道我已经在索引 0 处进行了更改它重新考虑项目 0 的位置，例如a.update_sorting_of(0) .
是否有另一种数据结构专门用于此目的？
我应该自己编写并优化吗？
我应该解决这个问题吗a.add(a.pop(0))而是？
与专用解决方案相比，此解决方案如何？

我可以有把握地假设变异 a[0]在我的例子中没有触发其他元素的任何变化(否则我只会 a.sort(key=len) 整个事情)。

Answer 1

没有任何机制可以做你想做的事。即使你在改变一个元素后使用一个列表，它的复杂度也会是 O(nlogn) 。但由于 add() 在幕后使用了 bisect，因此它的时间复杂度仅为 O(logn)。因此，最好按照您的建议进行操作，即删除要突变的元素并重新添加它。如果有一个函数可以完成您想要的操作，它可能会在幕后执行类似的操作，因为我想不出比二等分更好的方法来放置排序顺序可能已更改的元素。

def mutate_element(sortedlist, index, value):
    temp = sortedlist.pop(index)
    temp.append(value)
    sortedlist.add(temp)

您还可以进一步概括各种列表变异方法的功能。例如 getattr(mylist, 'append') 与 mylist.append 相同。