Java: какое большое время для объявления массива размера n?

Ответ 1

Это O(n). Рассмотрим эту простую программу:

public class ArrayTest {

  public static void main(String[] args) {
     int[] var = new int[5];
  }

}

Созданный байткод:

Compiled from "ArrayTest.java"
public class ArrayTest extends java.lang.Object{
public ArrayTest();
  Code:
   0:   aload_0
   1:   invokespecial   #1; //Method java/lang/Object."<init>":()V
   4:   return

public static void main(java.lang.String[]);
  Code:
   0:   iconst_5
   1:   newarray int
   3:   astore_1
   4:   return

}

Инструкция, чтобы взглянуть на инструкцию newarray (просто найдите newarray). Из спецификации VM:

Новый массив, компоненты которого имеют тип atype и счетчик длины, выделяется из собранной мусором кучи. Ссылка arrayref на этот новый объект массива помещается в стек операнда. Каждый из элементов нового массива инициализируется начальным значением по умолчанию для типа массива (§2.5.1).

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

ИЗМЕНИТЬ

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

Ответ 2

Небольшой профессиональный тест на JRE1.6:

public static void main(String[] args) {
    long start = System.nanoTime();
    int[] x = new int[50];
    long smallArray = System.nanoTime();
    int[] m = new int[1000000];
    long bigArray = System.nanoTime();
    System.out.println("big:" +  new Long( bigArray - smallArray));
    System.out.println("small:" +  new Long( smallArray - start));


}

дал следующий результат:

big:6133612
small:6159

поэтому я предполагаю, что O (n). конечно, этого недостаточно, но это намек.

Ответ 3

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

Для дальнейшего развития Java инициализирует массивы при распределении. Нет никакого способа обнулить область памяти, не прогуливаясь по ней, и размер региона диктует количество инструкций. Поэтому нижняя граница O (n). Кроме того, нет смысла использовать алгоритм обнуления медленнее, чем линейный, поскольку существует линейное решение, поэтому верхняя граница должна быть O (n). Поэтому O (n) - единственный ответ, который имеет смысл.

Просто для удовольствия, однако, представьте себе странное аппаратное обеспечение, в котором ОС имеет контроль над мощностью в отдельных областях памяти и может обнулить регион, отключив питание и затем включить. Кажется, это будет O (1). Но область может быть настолько большой, пока утилита не исчезнет (не хочет потерять все), поэтому при запросе нулевой области все равно будет O (n) с большим делителем.

Ответ 4

Позвольте просто протестировать его.

class ArrayAlloc {
  static long alloc(int n) {
    long start = System.nanoTime();
    long[] var = new long[n];
    long total = System.nanoTime() - start;
    var[n/2] = 8;
    return total;
  }
  public static void main(String[] args) {
    for(int i=1; i<100000000; i+=1000000) {
      System.out.println(i + "," + alloc(i));
    }
  }
}

И результаты на моем ноутбуке linux (i7-4600M @2,90 ГГц):

Значит, это выглядит как O(n), но похоже, что он переключается на более эффективный метод примерно на 5 миллионов элементов.