Как написать метод clear() в структуре данных списка?

Недавно я прочитал исходный код некоторых фреймворков и заметил, что они написали метод clear() подобной спискам структуры данных. Удалите элементы по одному.

while (_arr.length > 0 )
{

    remove(_arr[0]);

}

(возможно, вышеупомянутое выглядит немного запутанным, но это потому, что собственный тип массива на этом языке был динамическим массивом) или

 for (int i = 0; i < size; i++)
  { elementData[i] = null;}
 size = 0;

Но я вспомнил, что написал такой код. Список украсил собственный тип массива, и я написал метод clear(), подобный этому.

 _arr=new Array();
 _size=0;

создать экземпляр нового типа собственного массива.

и этот код написан на языке, который содержит сборку мусора. поэтому я думаю, что все элементы, наконец, будут собраны, так зачем нужен цикл? Будет ли новый быстрый?

Ответ 1

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

Выделение нового массива (и сбор мусора старого), вероятно, требует больше времени, чем повторение существующего массива и установка ссылок всех элементов на null.

РЕДАКТИРОВАНИЕ: Как упоминалось в комментариях, установка ссылок на null в массиве на основе List недостаточна. Вы также должны указать, что List пуст. В java.util.ArrayList это делается установкой свойства size на 0.

Ответ 2

В некоторых контекстах более эффективно очищать и повторно использовать массив поддержки. (Очевидно, что вам нужно поле size, и вам нужно установить его на ноль, когда вы очистите список!)

Очистка уменьшает количество мусора, сгенерированного при очистке списка.
Если вы постепенно увеличиваете список (т.е. без подсказки capacity), очистка также уменьшает количество мусора, создаваемого перераспределением.

Но флипсайд - это не всегда хорошая идея clear. Например:

Если вы вызываете clear на ArrayList, размер массива поддержки остается того же размера, что и при заполнении списка. Если список был очень длинным, массив может быть очень большим. И если вам никогда не понадобится список, чтобы быть таким длинным снова, большой массив может тратить много места.
GC должен проверять каждую ячейку в массиве поддержки ArrayList в любом случае независимо от текущего значения поля size. И ему нужно скопировать весь массив в пространство ".".
Это также означает, что вам нужно назначить null для "очищенных" ячеек, чтобы избежать утечек памяти.
В случае возникновения "новых" объектов в большой "старый" массив могут возникать вторичные проблемы с производительностью из-за факторов генерации и/или локальности.

Короче говоря, если список с поддержкой массива, скорее всего, выдержит несколько циклов GC, то очистка (т.е. процедура очистки и повторного использования массива поддержки) является сомнительным предложением.

Ответ 3

Вероятно, это комментарий, но он не подходит, как я предполагаю.

Существует также тот факт, что besides выделение массива может быть слишком дорогостоящим, и очистка предыдущего массива будет дешевле, есть также тот факт, что выделение массива в форме new byte[100] или что-то еще должно обнуление содержимого, что также может быть дорогостоящим.

Таким образом, в конкатенации java-9 String используется UNSAFE.allocateUninitializedArray, который специально говорит Allocates an array of a given type, but does not do zeroing. и, конечно же, добавляет:

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

И вот как выглядит фактический метод:

    @ForceInline
    private static byte[] newArray(int length, byte coder) {
        return (byte[]) UNSAFE.allocateUninitializedArray(byte.class, length << coder);
    }

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

Ответ 4

Согласитесь с ответом @Eran на создание нового массива или повторное использование существующего!

Я хочу добавить здесь еще одну информацию.

Исходный код для clear() выглядит следующим образом:

public void clear() {
    modCount++;
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

Исходный код для removeAll() (определенный в AbstractCollection):

public boolean removeAll(Collection<?> c) {
    boolean modified = false;
    Iterator<?> e = iterator();
    while (e.hasNext()) {
        if (c.contains(e.next())) {
            e.remove();
            modified = true;
        }
    }
    return modified;
}

clear(), конечно, быстрее, поскольку он не должен иметь дело со всеми этими дополнительными вызовами. Так что лучше установить элемент в null вместо его удаления.

Ответ 5

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

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

Ответ 6

Ни. Просто установите _arr в пустой массив. Вы должны, конечно, не вызывать remove() в цикле, по соображениям эффективности, и установить все элементы в null семантически неправильно.