Считается ли эквивалентным постоянное время и амортизированное постоянное время?

Мне нужно написать RandomQueue, который позволяет добавлять и случайное удаление в постоянное время (O (1)).

Моей первой мыслью было подкрепить его каким-нибудь массивом (я выбрал ArrayList), поскольку массивы имеют постоянный доступ через индекс.

Просматривая документацию, я понял, что добавления ArrayLists считаются амортизированным постоянным временем, поскольку для добавления может потребоваться перераспределение базового массива, который равен O (n).

Являются ли амортизированные постоянное время и постоянное время практически одинаковыми, или мне нужно взглянуть на структуру, которая не требует полного перераспределения при каждом добавлении?

Я спрашиваю об этом, потому что за исключением структур на основе массива (которые, насколько я знаю, всегда будут дополнения Amortized Constant Time), я не могу придумать ничего, что будет соответствовать требованиям:

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

Вот полный вопрос; на случай, если я застеклю некоторые важные детали:

Разработка и внедрение RandomQueue. Это реализация интерфейса очереди, в котором операция remove () удаляет элемент, который выбран случайным образом равномерно среди всех элементов, находящихся в данный момент в очереди. (Подумайте о RandomQueue как о сумке, в которую мы можем добавить элементы или достучаться и слепо удалить некоторый случайный элемент.) Операции add (x) и remove () в RandomQueue должны выполняться в постоянном времени для каждой операции.

Амортизированное постоянное время почти всегда можно считать эквивалентным постоянному времени, и, не зная специфики вашего приложения и типа использования, которое вы планируете использовать в этой очереди, большинство шансов, что вы будете охвачены.

Список массивов имеет концепцию емкости , которая в основном равна наибольшему размеру / длине / количеству элементов, которые когда-либо требовались от него до сих пор. Итак, что произойдет, так это то, что в начале список массивов будет продолжать перераспределяться, увеличивая свою емкость, по мере того, как вы будете добавлять в него элементы, но в какой-то момент среднее количество элементов, добавляемых за единицу времени, неизбежно будет соответствовать среднему количеству элементов. удаляется за единицу времени (в противном случае вы в конечном итоге исчерпаете память), в этот момент массив перестанет перераспределять себя, и все добавления будут выполнены в постоянное время O (1).

Однако имейте в виду, что по умолчанию случайное удаление из списка массивов - это не O (1), а O (N), поскольку списки массивов перемещают все элементы после удаленного элемента на одну позицию вниз, чтобы занять место удаленного вещь. Для достижения O (1) вам придется переопределить поведение по умолчанию, чтобы заменить удаленный элемент копией последнего элемента списка массивов, а затем удалить последний элемент, чтобы никакие элементы не были перемещены. Но тогда, если вы это сделаете, у вас точно не будет очереди.

Вопрос, кажется, специально задает постоянное время, а не амортизированное постоянное время . Таким образом, что касается приведенного вопроса, нет, они не являются одинаковыми *. Однако они в реальных приложениях?

Типичная проблема с амортизированной константой заключается в том, что иногда вам приходится выплачивать накопленный долг. Таким образом, в то время как вставки обычно постоянны, иногда приходится переносить все заново, когда выделяется новый блок.

Где разница между постоянным временем и амортизированным постоянным временем имеет отношение к приложению, зависит от того, приемлема ли эта очень медленная скорость. Для очень большого количества доменов это обычно нормально. Особенно, если контейнер имеет эффективный максимальный размер (например, кэши, временные буферы, рабочие контейнеры), вы можете эффективно оплатить их стоимость только один раз во время выполнения.

В критических приложениях реагирования это время может быть неприемлемым. Если вам необходимо выполнить краткосрочную гарантию, вы не можете полагаться на алгоритм, который иногда будет превышать это. Я работал над такими проектами раньше, но они чрезвычайно редки.

Это также зависит от того, насколько высока эта стоимость. Векторы имеют тенденцию работать хорошо, поскольку их стоимость перераспределения относительно низкая. Однако, если вы перейдете к хэш-карте, перераспределение может быть намного выше. Хотя, опять же, для большинства приложений, вероятно, хорошо, особенно для более долгоживущих серверов с верхней границей элементов в контейнере.

* Здесь есть небольшая проблема. Чтобы сделать любой контейнер общего назначения постоянным временем для вставки, должна выполняться одна из двух вещей:

• Контейнер должен иметь фиксированный максимальный размер; или
• Вы можете предположить, что выделение памяти для отдельных элементов является постоянным временем.

Это зависит от того, оптимизируете ли вы пропускную способность или задержку:

• Чувствительные к задержке системы нуждаются в постоянной производительности. Для такого сценария мы должны подчеркнуть поведение системы в худшем случае. Примерами являются мягкие системы реального времени, такие как игры, которые хотят достичь постоянной частоты кадров, или веб-серверы, которые должны отправлять ответ в течение определенного ограниченного периода времени: тратить циклы ЦП лучше, чем опаздывать.
• Оптимизированные по пропускной способности системы не заботятся о случайных остановках, если в долгосрочной перспективе может обрабатываться максимальное количество данных. Здесь нас в первую очередь интересуют амортизированные показатели. Обычно это относится к обработке чисел или другим задачам пакетной обработки.

Обратите внимание, что одна система может иметь разные компоненты, которые должны быть по-разному классифицированы. Например, современный текстовый процессор имел бы чувствительный к задержке поток пользовательского интерфейса, но оптимизировал пропускную способность потоков для других задач, таких как проверка орфографии или экспорт PDF.

Кроме того, сложность алгоритма часто не так важна, как мы могли бы подумать: когда проблема ограничена определенным числом, фактические и измеренные характеристики производительности более важны, чем поведение «для очень больших n ».

Если вас просят ввести алгоритм «амортизированное постоянное время», ваш алгоритм может иногда занимать много времени. Например, если вы используете std :: vector в C ++, такой вектор может выделять пространство для 10 объектов, а когда вы выделяете 11-й объект, выделяется пространство для 20 объектов, 10 объектов копируются, а 11-й добавляется, что занимает значительное время Но если вы добавите миллион объектов, у вас может быть 999 980 быстрых и 20 медленных операций со средним быстрым временем.

Если вас спрашивают об алгоритме «постоянного времени», ваш алгоритм всегда должен быть быстрым для каждой отдельной операции. Это было бы важно для систем реального времени, где вам может потребоваться гарантия, что каждая отдельная операция всегда выполняется быстро. «Постоянное время» очень часто не требуется, но оно определенно не совпадает с «амортизированным постоянным временем».