Question

15469 просмотра

4 ответа

Каково время объявления массива размера n в Java? Я полагаю, это будет зависеть от того, обнулена ли память при сборке мусора (в этом случае это может быть O (1)) или при инициализации (в этом случае это должно быть O (n)).

Автор: Mala Источник Размещён: 13.11.2019 11:50

Answer 1

18 плюса

Решение

Это 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). Из ВМ Spec:

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

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

РЕДАКТИРОВАТЬ

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

Автор: Vivin Paliath Размещён: 12.04.2011 08:07

Answer 2

8 плюса

Небольшой профессиональный тест на 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). Конечно, этого недостаточно, но это намек.

Автор: amit Размещён: 12.04.2011 08:13

Answer 3

4 плюса

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

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

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

Автор: Jonathan Размещён: 12.04.2011 07:59

Answer 4

2 плюса

Давайте просто проверим это.

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 миллионами элементов.

Автор: lovasoa Размещён: 09.06.2017 11:41

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

Ответы (4)

Вопросы из категории :