Массив неопределенной емкости

Ты же в курсе, что исходники жабы открыты?

Создаётся новый массив.

В курсе, но конкретно сейчас у меня доступа к ним не было) Спасибо.

Обычный список. Ради оптимизации делают список массивов (чтобы сэкономить на указателях и выделять память блоками. А что ещё можно придумать?

Обычный список.

Обычный список, очевидно, не даст доступа к произвольному элементу за O(1), а вектор (массив) обычно подразумевает такое св-во.

а вектор (массив) обычно подразумевает такое св-во.

А где гарантируется, что доступ к динамическому массиву не дороже обычного? Можно ссылку на такой замечательный язык или компилятор или что там у тебя.

Кстати никто не запрещает оптимизировать сам доступ к элементам. Можно не список а дерево использовать.

А где гарантируется, что доступ к динамическому массиву не дороже обычного? Можно ссылку на такой замечательный язык или компилятор или что там у тебя.

любой динамический массив с массивом внутри, при добавлении элемента выполняется аллокация нового (звисит от механизмов управления памятью) и все

Наверно я слишком сложно выразился. Виноват. Итак имеем: обычный массив и динамический массив (не realloc!). На обычном массиве есть операция индексации. На динамическом массиве имеем движение по списку и (возможно) индексацию подмассива. Я интересовался у человека как может одинаково выполняться и индексация и проход по списку.

я слишком сложно выразился

динамический массив

и что такое «динамический массив» внутри?

На динамическом массиве имеем движение по списку

какой список? связанный? так это не единственный способ реализовать контейнер с изменяемым размером

А где гарантируется, что доступ к динамическому массиву не дороже обычного?

Совсем упоротый? Это самый распространённый контейнер именно с таким свойством, это должно быть известно любому кодеру. Ява не исключение и все ссылки на документацию найдёшь как-нибудь сам.

Операция индексации есть в некоторых процессорах (аппаратная). В любом случае это простейшая математическая операция: y = index * sizeof(элемент массива).

Проход же по списку это нетривиальная задача включающая в себя цикл, вычисление условия, операцию приращения (переход к следующему элементу), получение элемента (если это не список указателей. Тогда получение указателя.

Совсем упоротый?

Нет ты!!

Дык я об этом же.

вобщето вектор подразумивает что внутри он оргонизован как непрерывный блок памяти, и как правило реализуется через malloc/free/realloc (memmove если контейнер потдерживает вставку/удаление в середине вектора). Не буду говорить за яву но в С++ так и есть, и std::vector<char> - это простейший буфер (он же строка)

А теперь посмотри производительность vector. realloc не самая дешёвая операция. Ну и в конце концов: если бы вектор эффективно решал задачу динамического массива о списках никто бы и не слышал (все бы переспрашивали чего-чего подмассивов?)

За яву я вообще ничего не говорил, это ты сам придумал.

Вот именно по этому и есть связаные списки, поскокольку операция вставки для вектора (особенно длинного вектора) - весьма ресурсозатратна.

http://www.cplusplus.com/reference/vector/vector/insert/

Because vectors use an array as their underlying storage, inserting elements in positions other than the vector end causes the container to relocate all the elements that were after position to their new positions. This is generally an inefficient operation compared to the one performed for the same operation by other kinds of sequence containers (such as list or forward_list).

PS. И понятно что решений в лоб как правило никто не использует, и большенство векторов используют кеши, резервирование буферов и тд.

Зачем спорил, если в конце согласился со мной?

Извеняюсь, я чтото вас с топик стартером перепутал - ветку прочитал не внимательно.

Просто оставлю это здесь:

http://habrahabr.ru/post/128269/

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8-b132...

обычно сбалансированное дерево с весом. Ну т.е. в каждом узле хранится его вес, т.е. число узлов в данном поддереве. Поиск элемента с номером i происходит так:

1. начинаем с корня

2. смотрим вес левого поддерева l->w и вес правого поддерева r->w

3. если i<l->w, то искомое в левом поддереве

4. если i==l->w, то искомое в этом узле

5. иначе искомое в правом поддереве.

6. повторяем рекурсивно с п2.

Если высота дерева зависит от числа узлов как логарифм, то и сложность получается логарифмическая.

Сложность вставки/удаления тоже логарифмическая.

двухсвязный список

обычно такие вопросы задают, кода мышление испорчено паскалем, но все можно исправить

А где гарантируется, что доступ к динамическому массиву не дороже обычного?

Такого понятия как «ценность» операции в программировании не существует. Есть только различные асимптотики.

Если высота дерева зависит от числа узлов как логарифм, то и сложность получается логарифмическая

Здесь еще надо добавить, что на практике логарифмическая сложность - это сложность константная, потому что тебе никогда не придется работать с данными больше, например, чем 2^100.

Здесь еще надо добавить, что на практике логарифмическая сложность - это сложность константная, потому что тебе никогда не придется работать с данными больше, например, чем 2^100.

Такую глупость можно сказать про любую сложность, не только логарифмическую.

realloc не самая дешёвая операция

И что? Даже в самом диком быдлокоде нужно будет не более десятка-другого реаллоков. Зато доступ O(1). А если тебе нужен список, то и используй список. Если бы вектор реализовывался как список, то нахрен тогда нужен отдельно список?

двухсвязный список

время поиска по номеру имеет линейную сложность, что обычно недопустимо.

Здесь еще надо добавить, что на практике логарифмическая сложность - это сложность константная, потому что тебе никогда не придется работать с данными больше, например, чем 2^100.

к сожалению это не так. Для деревьев очень большая константа пропорциональности, и потому если узлов немного, дерево даёт более худшие результаты, чем более простые методы(списки, массивы). Деревья дают профиты именно в бесконечности, но в бесконечности это обычно не нужно. Кроме того, деревья используют непредсказуемое рандомное чтение, для чего наши процессоры и память не предназначены. Проще и быстрее прочитать 100Мб последовательно, чем прочитать 100К из этих 100Мб, но по 100 байт рандомно по всему полю.

И что? Даже в самом диком быдлокоде нужно будет не более десятка-другого реаллоков.

да, можно делать realloc с удвоением, тогда количество realloc'ов будет логарифмом по основанию 2. На практике 20и удвоений хватит для увеличения в 1048576 раз.

Спасибо всем!

да, можно делать realloc с удвоением, тогда количество realloc'ов будет логарифмом по основанию 2.

Важно не это. Средняя сложность реаллоков будет O(N), т.е. не будет хуже по сравнению с наращиваем того же списка.

индекс разрешает

а как реализован индекс?

Более того, эти классы еще ухитряются вставлять элементы не только в конец массива, но и внутрь, неужели при вставке элемента, там влоб сдвигаются все впереди идущие от места вставки элементы?

Примерно так всё и есть. Зато обеспечивается мгновенный доступ по индексу. Когда важнее быстрое добавление элементов следует применять связанные списки. Для них скорее всего в жабе тоже есть специальный класс. А ещё бывают всякие деревья, для них тоже есть свои классы. В каждой задаче наиболее оптимальным является что-то из этого, универсального решения не существует.

Также для уменьшения количества realloc, обычно память выделяется не под каждый элемент, а сразу под несколько, с запасом на будущее. К тому же есть методы, которые резервируют память принудительно (в C++ во всяком случае такое есть), чтобы последующие добавления не дёргали realloc, пока список не переполнится, если автор программы по ходу дела узнал, сколько элементов будет максимум.