时间戳

首页 > 解决方案 > 使可变元素的排序列表保持最新

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

问题描述

我可以使用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所以它知道我已经在 index 处进行了更改，0它会重新考虑 item 的位置0，比如a.update_sorting_of(0).
是否有另一种专门用于此的数据结构？
我应该自己编写并优化它吗？
我应该解决它a.add(a.pop(0))吗？
与专用解决方案相比，此解决方法如何？

我可以放心地假设，a[0]在我的情况下，变异并没有触发其他元素的任何变化（否则我会只是a.sort(key=len)整个事情）。

标签： pythonpython-3.xlistsortingmutable

解决方案

没有机制可以做你想做的事。即使你在改变一个元素后使用一个列表，它也会有 O(nlogn) 的复杂性。但是因为add()在幕后使用了 bisect，所以它只有 O(logn)。所以最好按照你的建议做一些事情，即删除要变异的元素并读取它。如果有一个功能可以满足您的要求，它可能会在幕后做类似的事情，因为我想不出比 bisect 更好的方法来放置排序顺序可能已更改的元素。

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

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

推荐阅读