Сколько нужно добавлять при изменении размера массива?

Question

У меня есть конкурс с другим учеником, чтобы сделать самую быструю версию нашего домашнего задания, и я не использую ArrayList по соображениям производительности (изменение размера массива сократило контрольное время с 56 секунд до 4), но я Мне интересно, сколько я должен изменить размер массива каждый раз, когда мне нужно. В частности соответствующие части моего кода являются следующим образом:

private Node[] list; 
private int size; // The number of items in the list 
private static final int N; // How much to resize the list by every time 

public MyClass(){ 
    list = new Node[N]; 
} 

public void add(Node newNode){ 
    if(size == list.length){ 
    list = Arrays.copyOf(list, size + N); 
    } 
    list[size] = newNode; 
    size++; 
} 

TL; DR: Что я должен сделать N?

Answer 1

При изменении размера рекомендуется удвоить размер массива. Удвоение размера приводит к амортизации линейных затрат времени.

Наивная идея состоит в том, что существуют две расходы, связанные с величиной изменения размера: затраты производительности

• Копирование - затраты на копирование элементов из предыдущего массива в новый, и
• накладные расходы памяти - стоимость из выделенной памяти, которая не используется.

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

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

ОБНОВЛЕНИЕ: Кстати, очевидно, что Java ArrayList расширяется (3/2). Это делает его немного более консервативным, но стоимость немного больше с точки зрения копирования. Бенчмаркинг для вашего использования не повредит.

MINER Correction: Удвоение приведет к изменению размера линейной амортизации, но гарантирует, что у вас есть амортизированная постоянная установка времени. Проверьте CMU's lecture on Amortized Analysis.

Answer 2

Если вы знаете, сколько будет элементов, то предварительно назначьте массив или массив ArrayList для этого размера, и вам никогда не придется расширяться. Непревзойденная производительность!

В противном случае разумным способом достижения хорошей амортизированной стоимости является постоянное увеличение на некоторый процент. 100% или 50% являются общими.

Answer 3

Вы должны изменить размер своих списков как кратное предыдущему размеру, а не добавлять постоянную сумму каждый раз.

, например:

newSize = oldSize * 2; 

не

newSize = oldSize + N; 

Answer 4

Двойной размер каждый раз, когда вам необходимо изменить размер, если вы не знаете, что более или менее будет лучше.

Если память не является проблемой, просто начните с большого массива для начала.

Answer 5

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

---

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

И исключить операцию копирования в целом, вы можете использовать список массивов

Answer 6

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

Answer 7

3/2, скорее всего, выбран как «нечто, что делит чисто, но меньше phi». В ноябре 2003 года было an epic thread on comp.lang.c++.moderated, изучающее, как phi устанавливает верхнюю границу для повторного использования ранее выделенного хранилища во время перераспределения для распределителя с первым назначением.

См. post #7 from Andrew Koenig для первого упоминания о приложении Phi к этой проблеме.

Answer 8

С комментариями одного из ответов:

Проблема заключается в том, что память не вопрос, но я читал произвольно большой файл.

Попробуйте это:

new ArrayList<Node>((int)file.length()); 

Вы можете сделать это с помощью массива, а также. Тогда не должно быть никакого изменения размера в любом случае, так как массив будет размером файла (если предположить, что файл не длиннее, чем int ...).

Answer 9

Вот вам аналогия, давным-давно, когда я работал на мэйнфрейме, мы использовали систему регистрации под названием VSAM, которая потребовала бы указать начальный размер файла и объем свободного пространства.

Всякий раз, когда количество свободного пространства опускается ниже порогового значения, тогда требуемое количество свободного пространства будет выделено в фоновом режиме, пока программа продолжит обработку.

Было бы интересно узнать, можно ли это сделать в java, используя отдельный поток, чтобы выделить дополнительное пространство и «прикрепить» его к концу массива, пока основной поток продолжает обрабатывать.