Как очистить очередь кругового массива за постоянное время O (1)

Question

Я пытаюсь найти способ реализовать эффективный clear для очистки очереди циклического массива за постоянное время.

Я пробовал Array.fill() и заполнил массив значениями nullно он все равно должен пройти через массив, что означает O (n).

Answer 1

Я бы сказал, что ответ на этот вопрос немного зависит от ваших требований и того, что считается постоянной операцией.

1. Один из способов сделать это - создать новый массив с фиксированным размером (который является O (1)) и отбросить ссылку на старую, после чего указатели вернутся к их начальному значению. При таком подходе последующие операции вставки должны будут увеличить размер массива.
2. Другой способ может состоять в том, чтобы инициализировать новый массив того же размера, что и тот, который в данный момент хранит элементы, и отбросить ссылку на старый. ,Это может быть операцией с постоянным временем .
3. Третий подход будет предложен пользователем Jordan в разделе комментариев вашего вопроса,Просто перемещайте указатели head и tail. Однако имейте в виду, что это не очищает ссылки на (возможно, тяжеловесные) объекты в массиве, что может привести к утечке памяти в вашем приложении, поскольку объекты, которые все еще хранятся там, не могут быть собраны мусором.

Рассматривая реализацию операции clear ArrayDeque (которая в основном представляет собой просто кольцевую очередь массива), вы можете видеть, что она использует O (n)выполните следующие две операции: (1) обнуление элементов, (2) сброс указателей.

/**
 * Removes all of the elements from this deque.
 * The deque will be empty after this call returns.
 */
public void clear() {
    circularClear(elements, head, tail);
    head = tail = 0;
}

/**
 * Nulls out slots starting at array index i, upto index end.
 * Condition i == end means "empty" - nothing to do.
 */
private static void circularClear(Object[] es, int i, int end) {
    // assert 0 <= i && i < es.length;
    // assert 0 <= end && end < es.length;
    for (int to = (i <= end) ? end : es.length;
         ; i = 0, to = end) {
        for (; i < to; i++) es[i] = null;
        if (to == end) break;
    }
}