Есть ли у python отсортированный список?

Под этим я подразумеваю структуру с:

• O (log n) сложность для x.push()операций
• O (log n) сложность поиска элемента
• O (n) сложность для вычисления, list(x)которая будет отсортирована

У меня также был связанный с этим вопрос о производительности, list(...).insert(...)который сейчас здесь .

Стандартный список Python не сортируется ни в какой форме. Стандартный модуль heapq можно использовать для добавления O (log n) к существующему списку и удаления наименьшего из O (log n), но это не отсортированный список в вашем определении.

Существуют различные реализации сбалансированных деревьев для Python, которые отвечают вашим требованиям, например, rbtree , RBTree или pyavl .

Есть ли какая-то конкретная причина для ваших требований большого О? Или вы просто хотите, чтобы это было быстро? Модуль sortedcontainers - это чистый Python и быстрый (как в реализациях fast-as-C, таких как blist и rbtree).

В сравнении производительности показывает , что контрольные показатели быстрее или на одном уровне с отсортированного списка типа Blist в. Также обратите внимание, что rbtree, RBTree и PyAVL предоставляют отсортированный dict и типы наборов, но не имеют типа отсортированного списка.

Если производительность является требованием, всегда не забывайте проводить тесты. Модуль, который подтверждает утверждение о быстродействии с нотацией Big-O, должен вызывать подозрение, пока он также не покажет сравнительные тесты.

Отказ от ответственности: я являюсь автором модуля Python sortedcontainers.

Монтаж:

pip install sortedcontainers

Использование:

>>> from sortedcontainers import SortedList
>>> l = SortedList()
>>> l.update([0, 4, 1, 3, 2])
>>> l.index(3)
3
>>> l.add(5)
>>> l[-1]
5

Хотя я до сих пор никогда не проверял "большую" скорость базовых операций со списками Python, bisectстандартный модуль, вероятно, также стоит упомянуть в этом контексте:

import bisect
L = [0, 100]

bisect.insort(L, 50)
bisect.insort(L, 20)
bisect.insort(L, 21)

print L
## [0, 20, 21, 50, 100]

i = bisect.bisect(L, 20)
print L[i-1], L[i]
## 20, 21

PS. Ах, извините, bisectупоминается в упомянутом вопросе. Тем не менее, думаю, не будет большого вреда, если эта информация будет здесь)

PPS. И списки CPython на самом деле являются массивами (не, скажем, skiplists и т. Д.). Что ж, я думаю, это должно быть что-то простое, но как по мне, название немного вводит в заблуждение.

Итак, если я не ошибаюсь, скорости пополам / списку, вероятно, будут такими:

• для push (): O (n) в худшем случае;
• для поиска: если мы считаем, что скорость индексации массива равна O (1), поиск должен выполняться за O (log (n));
• для создания списка: O (n) должно быть скоростью копирования списка, иначе O (1) для того же списка)

Upd. После обсуждения в комментариях позвольте мне связать здесь эти вопросы SO: Как реализован список Python и какова сложность выполнения функций списка Python

import bisect

class sortedlist(list):
    '''just a list but with an insort (insert into sorted position)'''
    def insort(self, x):
        bisect.insort(self, x)

Хотя он (пока) не предоставляет пользовательской функции поиска, heapqмодуль может удовлетворить ваши потребности. Он реализует очередь кучи с использованием обычного списка. Вам нужно будет написать свой собственный эффективный тест членства, который использует внутреннюю структуру очереди (это можно сделать за O (log n) , я бы сказал ...). Есть один недостаток: извлечение отсортированного списка имеет сложность O (n log n) .

Я бы использовал модули biscectили sortedcontainers. У меня нет опыта, но я думаю, что heapqмодуль работает. Он содержитHeap Queue

Реализовать собственный список сортировки на Python может быть несложно. Ниже приведено подтверждение концепции:

import bisect

class sortlist:
    def __init__(self, list):
        self.list = list
        self.sort()
    def sort(self):
        l = []
        for i in range(len(self.list)):
            bisect.insort(l, self.list[i])
        self.list = l
        self.len = i
    def insert(self, value):
        bisect.insort(self.list, value)
        self.len += 1
    def show(self):
        print self.list
    def search(self,value):
        left = bisect.bisect_left(self.list, value)
        if abs(self.list[min([left,self.len-1])] - value) >= abs(self.list[left-1] - value):
            return self.list[left-1]
        else:
            return self.list[left]

list = [101, 3, 10, 14, 23, 86, 44, 45, 45, 50, 66, 95, 17, 77, 79, 84, 85, 91, 73]
slist = sortlist(list)
slist.show()
slist.insert(99)
slist.show()
print slist.search(100000000)
print slist.search(0)
print slist.search(56.7)

========= Результаты ============

[3, 10, 14, 17, 23, 44, 45, 45, 50, 66, 73, 77, 79, 84, 85, 86, 91, 95, 101]

[3, 10, 14, 17, 23, 44, 45, 45, 50, 66, 73, 77, 79, 84, 85, 86, 91, 95, 99, 101]

101

3

50