Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Java [игнор отключен] [закрыт для гостей] / Скорость перебора элементов LinkedList методом get() / 6 сообщений из 6, страница 1 из 1
26.03.2013, 17:45:21
    #38199146
ozzmosis
ozzmosis
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Скорость перебора элементов LinkedList методом get()
Из лит-ры известно, что "перебор грибов" в LinkedList лучше не делать, если число элементов с списке достаточно велико.
Есть вот такой код:
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
import java.util.*;
public class LinkedListExplore5 {
    final static int m = 80000;
    public static void main(String[] args) {
        List<String> s = new LinkedList<String>();
        for (int i = 0; i < m; i++) {
            s.add(UUID.randomUUID().toString());
        }
        System.out.println("t0="+System.currentTimeMillis());
        // s.get(12000);
        for (int i = 0; i < m; i++) {
            s.get(i);
        }
        System.out.println("t1="+System.currentTimeMillis());
    }
}

В нём я менял значения `m` от 10'000 до 80'000 с шагом 10'000 и получил следующую таблицу времени выполнения:mtime, ms1000034420000123430000289140000128915000027079600004307870000671258000090797
Видно, что после числа = 40 тыс действительно начинаются проблемы.
В книге Хорстманна (ISBN 5-8459-1033-1 rus) объясняется, что метод get(n) будет делать перебор, начиная с 1-го элемента и до n, если n<=list.size() / 2, в противном случае начиная с list.size() вниз до n. Но по-любому будет перебор, начиная с границы.

Почему тогда вот это:
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
import java.util.*;
public class LinkedListExplore5 {
    final static int m = 80000;
    public static void main(String[] args) {
        List<String> s = new LinkedList<String>();
        ListIterator<String> k = s.listIterator();
        for (int i = 0; i < m; i++) {
            s.add(UUID.randomUUID().toString());
        }
        System.out.println("t0="+System.currentTimeMillis());
        s.get(34567);
//        for (int i = 0; i < m; i++) {
//            s.get(i);
//        }
        System.out.println("t1="+System.currentTimeMillis());
    }
}

- отрабатывает мгновенно, какой бы числовой индекс я не задал ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.03.2013, 17:53:21
    #38199163
Blazkowicz
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Скорость перебора элементов LinkedList методом get()
Перебор в LinkedList чудесно делает через итератор. Проблемы только в доступе по случайному индексу.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.03.2013, 17:53:24
    #38199164
ivanra
ivanra
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Скорость перебора элементов LinkedList методом get()
Ну как мгновенно. Пользуясь вашей табличкой, доступ осуществляется примерно за 90797/80000 = 1,13мс, такое время человеку действительно трудно заметить. А сделайте это 40000 раз в цикле и сравните с таким же циклом для ArrayList - и все станет понятно
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.03.2013, 18:01:42
    #38199175
Лагман
Лагман
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Скорость перебора элементов LinkedList методом get()
ozzmosis,

потому что цикл закомментирован
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.03.2013, 18:17:44
    #38199202
ozzmosis
ozzmosis
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Скорость перебора элементов LinkedList методом get()
BlazkowiczПеребор в LinkedList чудесно делает через итератор. Проблемы только в доступе по случайному индексу.А еще вопрос. Если я создам объект LinkedList, затем сразу же - итератор к нему, то дальше я не могу добавлять к объекту LinkedList новые элементы:
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
import java.util.*;
public class LinkedListExplore4 {
    public static void main(String[] args) {
        List<String> s = new LinkedList<String>();
        Iterator<String> si = s.iterator();
        s.add("Adam");
        s.add("Bob");
        s.add("Carl");

        //si = s.iterator();
        while (si.hasNext()) {
            si.next();
        }
        
        System.out.println(s);
    }
}

- вываливает:
Код: plaintext
1.
2.
3.
4.
Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.LinkedList$ListItr.checkForComodification(LinkedList.java:761)
	at java.util.LinkedList$ListItr.next(LinkedList.java:696)
	at LinkedListExplore4.main(LinkedListExplore4.java:12)
Java Result: 1
Если же раскомментировать строку "//si = s.iterator();" перед while-циклом, то ошибки уже не будет.

В книге Хорстманна на стр. 135 сказано:
авторпри изменениях списка<...> к набору следует подключать только один итератор, который помимо операций чтения может выполнять операции записи.
...
Перед выполнением каждого метода итератора выполняется проверка равенства количества изменений данного итератора и общего количества изменений всего набора данных. Если равенство не соблюдается, то генерируется исключение ConcurrentModificationExceptionя правильно понимаю, что переменной итератора надо присваивать значение list.iterator() только после "окончательной утряски" списка, даже без всякой параллельной работы ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.03.2013, 18:24:23
    #38199219
Blazkowicz
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Скорость перебора элементов LinkedList методом get()
для "параллельной работы" существуют отдельные коллекции с разной реализацией этой самое "параллельности".
например CopyOnWriteArrayList
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Java [игнор отключен] [закрыт для гостей] / Скорость перебора элементов LinkedList методом get() / 6 сообщений из 6, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 597ms
Закрыть
start [/forum/topic.php?fid=59&tablet=1&tid=2129688]:
 0ms
get settings:
 21ms
get forum list:
 28ms
check forum access:
 8ms
check topic access:
 8ms
track hit:
 89ms
get topic data:
 22ms
get forum data:
 5ms
get page messages:
 79ms
get tp. blocked users:
 3ms
others: 334ms
total:  597ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]