«Произвольный доступ O (1)» является чрезвычайно требовательным требованием, которое в основном накладывает основную хэш-таблицу - и я надеюсь, что вы имеете в виду только случайные ЧТЕНИЯ, потому что я думаю, что это может быть математически доказано, чем невозможно в общем случае иметь O (1) записи, а также (N) упорядоченную итерацию.
Я не думаю, что вы найдете предварительно упакованный контейнер, подходящий для ваших нужд, потому что они настолько экстремальны - доступ O (log N), конечно, будет иметь все значение в мире. Чтобы получить поведение big-O, которое вы хотите для чтения и итерации, вам нужно склеить две структуры данных, по существу, dict и кучу (или отсортированный список или дерево), и синхронизировать их. Хотя вы не укажете, я думаю, вы получите амортизированное поведение того типа, который вам нужен - если только вы действительно не готовы платить какие-либо потери производительности за вставки и удаления, что является буквальным следствием спецификации, которые вы выражаете, но в реальной жизни кажется маловероятным требованием.
Для чтения O (1) и амортизированной O (N) упорядоченной итерации, просто сохраните список всех ключей на стороне диктанта. E.g.:
class Crazy(object):
def __init__(self):
self.d = {}
self.L = []
self.sorted = True
def __getitem__(self, k):
return self.d[k]
def __setitem__(self, k, v):
if k not in self.d:
self.L.append(k)
self.sorted = False
self.d[k] = v
def __delitem__(self, k):
del self.d[k]
self.L.remove(k)
def __iter__(self):
if not self.sorted:
self.L.sort()
self.sorted = True
return iter(self.L)
Если вам не нравится «амортизированный порядок O (N)», вы можете удалить self.sorted и просто повторить self.L.sort() в __setitem__. Это делает записи O (N log N), конечно (в то время как у меня все еще были записи в O (1)). Любой из этих подходов жизнеспособен, и трудно представить, что один из них по своей сути превосходит другой. Если вы склонны делать кучу записей, то кучу итераций, тогда подход в приведенном выше коде является лучшим; если обычно это одна запись, одна итерация, другая запись, другая итерация, то это просто промывка.
Кстати, здесь используются бесстыдные преимущества необычных (и замечательных ;-) характеристик производительности сортировки Python (также называемой "timsort"): среди них сортировка списка, который в основном отсортирован, но с несколькими дополнительными элементами, прикрепленными в конце в основном O (N) (если привязанных элементов достаточно мало по сравнению с отсортированной префиксной частью). Я слышал, что Java быстро обретает подобный вид, так как Джош Блок был настолько впечатлен техническим разговором о Python, что он тут же начал кодировать его для JVM на своем ноутбуке. Большинство систем (включая, я полагаю, Jython на сегодняшний день и IronPython) в основном имеют сортировку как операцию O (N log N), не используя преимущества «в основном упорядоченных» входных данных; «Естественное слияние», которое Тим Питерс создал сегодня в Python, является чудом в этом отношении.