Java: каково время объявления массива размером n?
15469 просмотра
4 ответа
Каково время объявления массива размера n в Java? Я полагаю, это будет зависеть от того, обнулена ли память при сборке мусора (в этом случае это может быть O (1)) или при инициализации (в этом случае это должно быть O (n)).
Автор: Mala Источник Размещён: 13.11.2019 11:50Ответы (4)
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:078 плюса
Небольшой профессиональный тест на 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:134 плюса
Я почти уверен, что это O (n), так как память инициализируется при выделении массива. Он не должен быть выше, чем O (n), и я не вижу способа сделать его меньше, чем O (n), так что это кажется единственным вариантом.
Чтобы уточнить, Java инициализирует массивы при распределении. Невозможно обнулить область памяти, не пройдя по ней, а размер области определяет количество инструкций. Следовательно, нижняя граница равна O (n). Кроме того, не имеет смысла использовать алгоритм обнуления медленнее, чем линейный, поскольку существует линейное решение, поэтому верхняя граница должна быть O (n). Следовательно, O (n) является единственным ответом, который имеет смысл.
Просто для забавы, однако, представьте себе странное аппаратное обеспечение, в котором ОС контролирует питание отдельных областей памяти и может обнулять область, отключив и снова включив питание. Кажется, это будет O (1). Но область может быть настолько большой, пока утилита не исчезнет (не хотелось бы потерять все), поэтому при запросе обнуления региона все равно будет O (n) с большим делителем.
Автор: Jonathan Размещён: 12.04.2011 07:592 плюса
Давайте просто проверим это.
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 миллионами элементов.
Вопросы из категории :
- java В чем разница между int и Integer в Java и C #?
- java Как я могу определить IP моего маршрутизатора / шлюза в Java?
- java Каков наилучший способ проверки XML-файла по сравнению с XSD-файлом?
- java Как округлить результат целочисленного деления?
- java Преобразование списка <Integer> в список <String>
- arrays Как удалить дубликаты из массива C #?
- arrays Как определить размер моего массива в C?
- arrays Каков наилучший способ конвертировать массив в хеш в Ruby
- arrays Сравнение двухбайтовых массивов в .NET
- arrays Можно ли выполнять параллельные обходы в MATLAB так же, как в Python?
- complexity-theory Big O, как вы рассчитываете / приближаете это?
- complexity-theory Является ли list :: size () действительно O (n)?
- complexity-theory Вычислительная сложность последовательности Фибоначчи
- complexity-theory Каков наилучший способ получить минимальное или максимальное значение из массива чисел?
- complexity-theory Что такое простое английское объяснение обозначения "Big O"?
- performance Как создать новый экземпляр объекта из Типа
- performance Как работает индексация базы данных?
- performance Действительно ли опечатанные классы действительно предлагают преимущества?
- performance MyISAM против InnoDB