Java. Как работает Random и remove в Queue?

Question

[Йцу Йцуевич]

Что, собственно говоря, стряслось...
Происходит какая-то нелепость.

Создаю очередь (PriorityQueue) и добавляю в неё значения.
1. Добавляю случайные числа (Random)
2. Добавляю константное выражение

и удаляю первый элемент в очереди (remove(0)).

В первом случае удаление происходит за 40-60 микросекунд, во втором в почти миллисекунда, что в 500 раз больше

Пожалуйста, не поленитесь глянуть на код (или хотя бы скопировать к себе).

private static final int COUNT = 1000000;

	public static void main(String[] args) {
		
		Random rand = new Random();
		
		Queue<Integer> arr = new PriorityQueue<Integer>();

		for (int i = 0; i < COUNT; i++)
			arr.add(rand.nextInt(100));               // заносим значения

		long before = System.nanoTime();			            // до
		arr.remove(0);	                              // удаляем первый элемент
		long total = System.nanoTime() - before;	    // после
		
		System.out.println("Microsecond: " + total / 1000);
	}

Клик сюда!!! (фото)

Теперь, при добавлении меняем рандом на константные числа

// ...
        arr.add(100);
// ...

И сюда

Почему так происходит???

Answer 1

[Илья Глебов]

Для работы PriorityQueue используется binary heap - это двоичное дерево, которое хранится определенном образом в линейном массиве. Корень дерева храниться в нулевом элементе, его дети - в следующих двух (1ом и 2ом), их дети - в следующих четырех.

После заполнения PriorityQueue в первом варианте, случайными числами, массив будет выглядить так

Элементы со значением "0" с вероятностью 99% будут встречаться в первых 100 элементах массива.

Если заполнить PriorityQueue одним и тем же числом - то массив двоичной кучи будет таким




Теперь посмотрим исходники метода remove

public boolean remove(Object o) {
       int i = indexOf(o);
       if (i == -1)
           return false;
        else {
            removeAt(i);
           return true;
       }
}

 private int indexOf(Object o) {
        if (o != null) {
            for (int i = 0; i < size; i++)
                if (o.equals(queue[i]))
                    return i;
        }
        return -1;
    }

Сначала ищется индекс элемента в массиве. Для этого используется проход по массиву.

В случае со случайными элементами придется просматривать в среднем 50 элементов пока не найдем элемента со значением "0", а при добавлении константы - все 1 000 000.

Comments

[Йцу Йцуевич]

ОГОГО, спасибо большое, раскрыли глаза, что-бы я делал...
- так бы наверно и мучился, думая, что Java дурацкий язык =)

А можно ли смотреть исходники в среде Eclipce, NetBeans, ... ?
Если да, то как?

[Илья Глебов]

Нужно поставить декомпилятор netbeans decompiler java

Если понравилось - отметьте как ответ :)

[Power]

Илья Глебов: Зачем декомпилятор? Исходники jdk свободно доступны, надо только их подключить.

Answer 2

[Йцу Йцуевич]

Кто-нибудь, протестите у себя, может быть у меня Java моросит...

Answer 3

[Power]

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

Comments

[Йцу Йцуевич]

воот блииин...
А как удалить по индексу, такое возможно?

[Йцу Йцуевич]

увидел removeAt, он?

[Power]

kofon: removeAt имеет модификатор private, так что его нельзя вызвать извне. Если вам нужно удалить именно первый элемент, есть метод poll. А для произвольного индекса, боюсь, метода нет.