К списку форумов К списку тем
Регистрация    Правила    Главная форума    Поиск   
Имя: Пароль:
Рекомендовать в новости

Ламерский вопрос: LinkedList vs ArrayList

0 - 14.04.2017 - 21:41
У меня тут возник ламерский вопрос.
Предположим, у меня есть массив из 100...00 элементов.
Мне нужно в серидину вставить еще один элемент.
В случае с ArrayList я мгновенно найду нужный элемент и за время О(n) скопирую хвост массива.
В случае с LinkedList я за время О(n) найду нужный элемент и мгновенно вставлю его.
Что будет быстрее?



1 - 14.04.2017 - 22:10
>Что будет быстрее?

надо мерять 8)

и надо учитывать что в ArrayList при вставке иногда надо еще выделить память: при аллокации память выделяется с запасом (1.3 или 1.5 от старого размера, надо смотреть) то, когда ее уже не хватает, потребуется снова выделить и потом копировать голову и хвост по отдельности

но в любом случае на одной вставке разница будет не сильно заметна, а когда вставка превалирует над чтением то и так очевидно
banned
2 - 14.04.2017 - 22:11
0-Добрых дел мастер > Не знаю, как там у вас по-модному, а раньше было простое правило - часто вставляешь в середину, редко ищешь - List. Добавляешь в конец, быстрый произвольный доступ по индексу - vector (Array по-вашему).
И всё.
3 - 14.04.2017 - 22:13
>а раньше было простое правило

а если надо читать с хвоста, вставлять в начало, но если элементов больше N то затирать самый старый ?
banned
4 - 14.04.2017 - 22:32
3-wayerr > Первые два условия - deque.
Последнее - это уже странное требование для "обычного" контейнера. Не кажется, что это нужно реализовать в ручную?
Впрочем, тот же deque легко позволяет это сделать.
И вообще, не много ли изврата у вас тут? Что за мегапроекты? :)
5 - 14.04.2017 - 23:48
>Последнее - это уже странное требование для "обычного" контейнера.

обычный цыклический буфер
banned
6 - 15.04.2017 - 09:53
5-wayerr > Извините, не помню в С++ стандартного цЫклического буфера. В boost вроде есть.
В Java конечно такая плюшка может и идет типа "из коробки". :)
Слово "обычный" конечно забавно звучит для цЫклического буфера. Как часто его применяете, по сравнению, например, с обычным Array?
7 - 15.04.2017 - 12:19
> не помню в С++ стандартного

чо если стандартного нет то все пропало? лол
8 - 15.04.2017 - 14:32
Цитата:
Сообщение от wayerr Посмотреть сообщение
но в любом случае на одной вставке разница будет не сильно заметна, а когда вставка превалирует над чтением то и так очевидно
я полагаю - вставка превалирует над поиском места для вставки.

2Нас не забанить. Вот у меня тоже раньше было простое правило. А сейчас вот задумался.
Никакого изврата. Чисто теоретический интерес.

Цитата:
Сообщение от wayerr Посмотреть сообщение
а если надо читать с хвоста, вставлять в начало, но если элементов больше N то затирать самый старый ?
Формально, это не коллекция. Коллекция должна хранить все элементы. А реализовывал бы я его (вероятно) с помощью традиционного массива и указателя на "начало".
9 - 15.04.2017 - 15:46
>Формально, это не коллекция. Коллекция должна хранить все элементы.

тогда и weakhashmap - не коллекция 8)
10 - 15.04.2017 - 15:54
Вообще, map-ы не являются коллекциями
11 - 15.04.2017 - 16:15
http://docs.oracle.com/javase/8/docs.../overview.html

>Collection Implementations

>The AbstractCollection, AbstractSet, AbstractList, AbstractSequentialList and AbstractMap classes provide basic implementations of the core collection interface

Или у нас что не реализует интерфейс Collection - то не коллекция вопреки документации?
12 - 15.04.2017 - 16:30
Ну, это вольное трактование вольно написанной фразы. Это скорее недостаток человеческого языка.

ок, а что тогда - коллекция?
13 - 15.04.2017 - 17:20
> а что тогда - коллекция?

в терминах java то что перечислено по ссылке 8)
14 - 15.04.2017 - 18:27
из того же документа:
The other collection interfaces are based on java.util.Map and are not true collections.

ладно, это спор ни о чем.
banned
15 - 16.04.2017 - 02:01
7-wayerr > Конечно ЛОЛ :)
16 - 16.04.2017 - 19:54
Цитата:
Сообщение от Добрых дел мастер Посмотреть сообщение
Что будет быстрее?
Вопрос неправильно поставлен.
Правильно: мне надо сделать...
Какими средствками лучше сделать.
в большинстве случаев это hash table


К списку вопросов
Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск




Copyright ©, Все права защищены