Что такое структура данных, которая имеет O (1) для, добавляют, предварительно ожидают и получают элемент в каком-либо местоположении?
Ориентация объекта:
struct Class {
size_t size;
void * (* ctor) (void * self, va_list * app); // constructor method
void * (* dtor) (void * self); // destructor method
void (* draw) (const void * self); // draw method
};
( Источник кода )
5 ответов
Вам нужна двусторонняя очередь. Это реализовано так, как вы хотите, в C ++ STL, то есть вы можете индексировать его, но не в Java, как вы заметили. Вы могли бы создать свой собственный из стандартных компонентов, используя два массива и сохраняя значение «ноль». Это может привести к неэффективной трате памяти, если вы в конечном итоге продвинетесь далеко от нуля, но если вы зайдете слишком далеко, вы можете переустановить и позволить двухсторонней очереди ползать в новый массив.
Более элегантное решение, которое на самом деле не требует такая хитрость в управлении двумя массивами состоит в том, чтобы наложить круговой массив на заранее выделенный массив. Это потребует реализации push_front, push_back и изменения размера массива за ним, но условия для изменения размера и тому подобное будут намного чище.
Если вы обрабатываете добавление к Vector / ArrayList как O (1) - что на самом деле не так, но на практике может быть достаточно близким -
(РЕДАКТИРОВАТЬ - чтобы уточнить - добавление может быть амортизированным постоянным временем , то есть - в среднем, добавление будет O (1), но может быть немного хуже по пикам. В зависимости от контекста и точного задействованы константы, такое поведение может быть смертельным.)
(Это не Java, а какой-то выдуманный язык ...).
Один вектор, который будет называться «Вперед». Второй вектор, который будет называться «Назад».
При запросе добавления -
Forward.Append () .
Когда вас попросят добавить -
Backwards.Append () .
При запросе запроса -
if ( Index < Backwards.Size() )
{
return Backwards[ Backwards.Size() - Index - 1 ]
}
else
{
return Forward[ Index - Backwards.Size() ]
}
(а также проверить, выходит ли индекс за границы).
deque (двусторонняя очередь) может быть реализована для обеспечения всех этих операций за время O (1), хотя не все реализации это делают. Я никогда не использовал Java ArrayDeque, поэтому я подумал, что вы шутите о том, что он не поддерживает произвольный доступ, но вы абсолютно правы - как «чистая» двухсторонняя очередь, она обеспечивает легкий доступ только с концов. Я понимаю, почему, но это точно раздражает ...
Для меня идеальный способ реализовать чрезвычайно быструю двухстороннюю очередь - использовать кольцевой буфер , тем более что вас интересует только добавление удаления спереди и сзади. Я не сразу знаю один на Java, но я написал его на Objective-C как часть среды с открытым исходным кодом. Вы можете использовать код как есть или как образец для реализации своего собственного.
Вот портал WebSVN для кода и относящаяся к документация . Настоящее мясо находится в файле CHAbstractCircularBufferCollection.m - ищите методы appendObject: и prependObject: . Существует даже специальный перечислитель («итератор» в Java). Основная логика циклического буфера довольно тривиальна и отражена в трех централизованных макросах #define :
#define transformIndex(index) ((headIndex + index) % arrayCapacity)
#define incrementIndex(index) (index = (index + 1) % arrayCapacity)
#define decrementIndex(index) (index = ((index) ? index : arrayCapacity) - 1)
Как вы можете видеть в методе objectAtIndex: , все, что вы делаете для доступа N-й элемент двухсторонней очереди - это массив [transformIndex (N)] . Обратите внимание, что я делаю tailIndex всегда указывающим на один слот за последним сохраненным элементом, поэтому, если headIndex == tailIndex , массив заполнен или пуст, если размер равен 0.
Надеюсь, что это поможет. Приношу свои извинения за размещение кода, отличного от Java, но автор вопроса действительно сказал, что общие ответы приемлемы.
Ваша идея может сработать. Если это единственные операции, которые вам нужно поддерживать, тогда вам достаточно двух векторов (назовите их Head и Tail). Чтобы добавить, вы добавляете в голову, а чтобы добавить, вы добавляете в хвост. Чтобы получить доступ к элементу, если индекс меньше head.Length, тогда верните head [head.Length-1-index], иначе верните tail [index-head.Length]. Очевидно, что все эти операции являются O (1).
Вам нужна двусторонняя очередь ( deque ), как в STL, поскольку в Java ArrayDeque отсутствует get () почему-то. Здесь были хорошие предложения и ссылки на реализации: