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

Question

я имею в виду структуру с:

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

Я также имел связанный с этим вопрос о выполнении list(...).insert(...) который сейчас here.

Answer 1

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

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

Answer 2

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

Answer 3

Хотя я никогда еще не проверяли на «большой O» скорости базовых операций списка 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 lists are actually arrays (не скажем, скиписты и т. Д.). Ну, я думаю, они должны быть чем-то простым, но что касается меня, это имя немного вводит в заблуждение.

---

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

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

Upd. После обсуждения в комментариях, дайте мне ссылку здесь эти SO вопросы: How is Python's List Implemented и What is the runtime complexity of python list functions

Answer 4

Это не может быть трудно реализовать свой собственный список сортировки на 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]

Answer 5

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

performance comparison показывает тесты быстрее или наравне с сортированным списком типа blist. Также обратите внимание, что rbtree, RBTree и PyAVL предоставляют отсортированные типы dict и set, но не имеют отсортированного типа списка.

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

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

---

Установка:

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 

Answer 6

import bisect 

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

Answer 7

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