LINUX.ORG.RU

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

 ,


0

1

Не подскажите общую идею, как реализуются подобные классы http://developer.android.com/reference/java/util/Vector.html , необязательно конкретно этот и конкретно из Android SDK.Меня интересует общая идея/принцип построения массивов неопределенной длинны.В классе, как по ссылке, нет жестких ограничений на количество элементов...то есть по идее можно добавлять элементы, даже когда память уже подкачку будет использовать.Мне это непонятно, ведь на самом низком уровне ты таки должен указать емкость массива как при статическом выделении памяти (int massiv[capacity]), так и при динамическом (int☆ p= new int [capacity]). Более того, эти классы еще ухитряются вставлять элементы не только в конец массива, но и внутрь, неужели при вставке элемента, там влоб сдвигаются все впереди идущие от места вставки элементы?



Последнее исправление: CYB3R (всего исправлений: 1)

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

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

anonymous
()
Ответ на: комментарий от anonymous

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

Nerevarino
() автор топика

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

ziemin ★★
()
Ответ на: комментарий от ziemin

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

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

mashina ★★★★★
()
Ответ на: комментарий от mashina

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

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

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

ziemin ★★
()
Ответ на: комментарий от ziemin

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

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

Deleted
()
Ответ на: комментарий от Deleted

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

ziemin ★★
()
Ответ на: комментарий от ziemin

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

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

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

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

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

Deleted
()
Ответ на: комментарий от ziemin

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

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

mashina ★★★★★
()
Ответ на: комментарий от mashina

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

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

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

Нет ты!!

ziemin ★★
()
Ответ на: комментарий от ziemin

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

zaz ★★★★
()
Последнее исправление: zaz (всего исправлений: 1)
Ответ на: комментарий от zaz

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

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

ziemin ★★
()
Последнее исправление: ziemin (всего исправлений: 1)
Ответ на: комментарий от ziemin

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

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. И понятно что решений в лоб как правило никто не использует, и большенство векторов используют кеши, резервирование буферов и тд.

zaz ★★★★
()
Последнее исправление: zaz (всего исправлений: 1)
Ответ на: комментарий от ziemin

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

zaz ★★★★
()

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

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

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

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

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

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

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

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

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

emulek
()

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

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

anonymous
()
Ответ на: комментарий от ziemin

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

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

anonymous
()
Ответ на: комментарий от emulek

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

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

anonymous
()
Ответ на: комментарий от anonymous

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

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

mashina ★★★★★
()
Ответ на: комментарий от ziemin

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

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

no-such-file ★★★★★
()
Ответ на: комментарий от anonymous

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

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

emulek
()
Ответ на: комментарий от no-such-file

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

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

emulek
()
Ответ на: комментарий от emulek

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

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

mashina ★★★★★
()

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

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

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

KivApple ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.