Держите отсортированный список изменяемых элементов в актуальном состоянии

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] не вызвало каких-либо изменений в других элементах моего c асе (иначе я бы просто a.sort(key=len) все это).

Answer 1

Нет механизма, чтобы делать то, что вы хотите. Даже если вы измените список после изменения элемента, он будет иметь сложность O (nlogn). Но поскольку add() использует попросту за кулисами, у него есть только O (logn). Так что лучше сделать что-то, как вы предложили, то есть удалить элемент, который будет мутирован, и прочитать его. И если бы была функция, которая выполняла бы то, что вы хотели, она бы, вероятно, сделала нечто подобное за кулисами, потому что я не могу придумать лучшего способа, чем разделить пополам элемент, порядок сортировки которого мог измениться.

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

Вы также можете обобщить функциональность для различных методов изменения списка. Например, getattr(mylist, 'append') совпадает с mylist.append.