Кто-нибудь знает эту структуру данных Python?

Question

Класс Python имеет шесть требований, перечисленных ниже.Только полужирные термины должны читаться как требования.

---

1. Близко к O (1) производительности для стольких из следующих четырех операций.
2. Сохранение порядка сортировки при вставке объекта в контейнер.
3. Возможность просмотра последнего значения (наибольшее значение), содержащегося в объекте.
4. С учетом всплывающих с обеих сторон (получение наименьшего или наибольшего значения).
5. Возможность получения общего размера или количества объектов
6. Готовое решение , подобное коду в стандартной библиотеке Python.

---

Что осталось здесь по историческим причинам (помощьлюбопытно и доказать, что исследование было проведено).

---

Просматривая стандартную библиотеку Python (в частности, раздел о типах данных), я все еще не нашел класс, который удовлетворяет требованиям к требованиям таблицы фрагментации,collections.deque близко к тому, что требуется, но не поддерживает сортировку содержащихся в нем данных.Он обеспечивает:

1. Эффективное добавление и всплытие по обе стороны от deque с производительностью O (1) .
2. Попса с обеих сторон для данных, содержащихся в объекте.
3. Получение общего размера или количества объектов, содержащихся в нем.

Реализация неэффективного решения с использованием списков будет тривиальной, но найти класс, который хорошо работает, было бы гораздо более желательно.В растущей симуляции памяти без верхнего предела такой класс может хранить индексы пустых (удаленных) ячеек и понижать уровни фрагментации.Модуль bisect может помочь:

1. Помогает сохранять массив в отсортированном порядке при вставке новых объектов в массив.
2. Готовое решение для хранения списков, отсортированных по мере добавления объектов.
3. Позволит выполнить array[-1] до , чтобы просмотреть последнее значение в массиве.

Последний кандидаткоторый не смог полностью удовлетворить требования и оказался наименее многообещающим, был модуль heapq.Поддерживая то, что выглядело как эффективные вставки, и гарантируя, что array[0] было наименьшим значением, массив не всегда находится в полностью отсортированном состоянии.Больше ничего не было найдено.

---

Кто-нибудь знает о классе или структуре данных в Python, которые приближаются к этим шести требованиям?

Answer 1

Ваши требования:

1. O (1) с каждого конца
2. Эффективный len
3. Сортированный порядок
4. Посмотрите на последнее значение

, для которого вы можете использовать deque с пользовательским insert методом, который вращает деку, добавляет к одному концу и разворачивает.

>>> from collections import deque
>>> import bisect
>>> class FunkyDeque(deque):
...     def _insert(self, index, value):
...             self.rotate(-index)
...             self.appendleft(value)
...             self.rotate(index)
...
...     def insert(self, value):
...             self._insert(bisect.bisect_left(self, value), value)
...
...     def __init__(self, iterable):
...             super(FunkyDeque, self).__init__(sorted(iterable))
...
>>> foo = FunkyDeque([3,2,1])
>>> foo
deque([1, 2, 3])
>>> foo.insert(2.5)
>>> foo
deque([1, 2, 2.5, 3])

Обратите внимание, что требования 1, 2 и 4 все вытекают непосредственно из того факта, что базовая структура данных является deque, а требование 3 выполняется из-за способа вставки данных.(Обратите внимание, что вы можете обойти требование сортировки, позвонив, например, _insert, но это не относится к делу.)

Answer 2

Большое спасибо katrielalex за вдохновение, которое привело к следующему классу Python:

import collections
import bisect

class FastTable:

    def __init__(self):
        self.__deque = collections.deque()

    def __len__(self):
        return len(self.__deque)

    def head(self):
        return self.__deque.popleft()

    def tail(self):
        return self.__deque.pop()

    def peek(self):
        return self.__deque[-1]

    def insert(self, obj):
        index = bisect.bisect_left(self.__deque, obj)
        self.__deque.rotate(-index)
        self.__deque.appendleft(obj)
        self.__deque.rotate(index)

Answer 3

blist.sortedlist

1. Близко к производительности O (1) для многих из следующих четырех операций.
2. Сохранение порядка сортировки при вставке объектав контейнер.
3. Возможность просмотра последнего значения (наибольшее значение), содержащегося в объекте.
4. Возможность всплывающих окон с обеих сторон (получение наименьшего или наибольшего значения).
5. Возможность получения общего размера или количества сохраняемых объектов.
6. Готовое решение, подобное коду в стандартной библиотеке Python.

Это дерево B +.