Чем плоха вставка в массив в заданную позицию?

Question

[Porto_b]

Написал для примера программу вставки элемента key в заданную позицию в массиве. Сам код работает, но возник вопрос. Не лучше ли сначала пройтись с конца массива, переставляя элементы, и в конце только a[pos] := key прописать? Просто циклы типа for down to не очень кошерно использовать, мне кажется. Вопрос почти философский, и есть ли алгоритмы лучше чем те, которые я описал?

function  InsertPos(var ar : arInt; key, pos : integer) : boolean;
var count, temp : integer;
begin
...
                count := Length(ar);  
                inc(count);
                 SetLength(ar, count);
...    
                 for j := pos to n-1 do
                                       begin
                                            temp := ar[j];
                                            ar[j] := key;
                                            key := temp;
                                       end;
...

Comments

[vaut]

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

[beerchaser]

Основной философский вопрос: зачем это делать (вставить значение именно в заданную позицию). Далее оцениваем вычислительную сложность алгоритма и понимаем, что, без аргументированного ответа на первый вопрос, так делать не нужно.

[ddd329]

vaut,

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

Список - это абстрактный тип данных, такой же как стек и очередь, которые вы можете реализовать и сами.
Вот представьте вы это начали делать, то где вы будете хранить данные?

[ddd329]

beerchaser,

Основной философский вопрос: зачем это делать (вставить значение именно в заданную позицию).

А как быть если массив нужно держать в отсортированном виде?

[beerchaser]

Вам на это уже дал ответ vault. Отсортированный массив нужен не в абстрактный момент времени, а в момент обращения к отсортированному массиву. Что мешает добавить признак отсортированости и произвести сортировку несортированого массива любым известным методом? При этом ресурсов потратиться значительно меньше. При добавлении признак отсортированности сбрасывать. Но как уже было замечено в комментариях выше, если не стоит задача хранить данные именно в массиве, имеет смысл посмотреть на другие структуры хранения данных. Например key-value списки. Причем крайне рекомендую использовать типовые решения и стандартные библиотеки.

[ddd329]

beerchaser,

Отсортированный массив нужен не в абстрактный момент времени, а в момент обращения к отсортированному массиву.

Я так понимаю, что под "моментом обращения" имеется ввиду не только чтение, но и запись в массив? Так вот представьте, что при каждой вставке вам необходимо его каждый раз сортировать... Сортировка обычно считается медленной операцией.

А почему бы сразу не держать массив в отсортированном виде? А место для вставки искать очень простым и эффективным способом - бинарный поиск (binary search)?

Что мешает добавить признак отсортированости и произвести сортировку несортированого массива любым известным методом?

И кто этот признак отсортированости будет "носить с собой"? Будете в методы передавать массив одним параметром, а признак сортированности вторым? Плюс вешать обязанность на вызывающие методы, чтобы в случае чего они могли его отсортировать?
Идея так себе...

[beerchaser]

ddd329, Где написано, что при вставке производится сортировка? При вставке предложено производить сброс признака отсортированости. Сортировка производится при запросе отсортированного массива при сброшенном признаке отсортированности.
Далее, о неоптимальности структуры хранения в топике уже упомянуто не раз...
И снова, процедурное программирование, классов нет, все в массиве -предложите способ лучше..
Резюмируя пример, могу сказать, как первый опыт-неплохо: задача таки решена. Про все остальное уже сказано.

[ddd329]

beerchaser, хорошо. Спасибо за ваш комментарий!

Answer 1

[dollar]

Прелесть массива в том, что он позволяет искать по индексам. И делается это очень быстро, потому что это индексация в самой памяти. То есть вычисляется адрес ячейки памяти с помощью арифметических операций:
БАЗА + [РАЗМЕР ЯЧЕЙКИ] * СМЕЩЕНИЕ
И затем просто происходит обращение на чтение/запись.

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

На самом деле, это не плохо и не хорошо. Если это делать редко, а читать данные часто, то это даже отлично. Но если вставка происходит слишком часто, то лучше пересмотреть выбранную архитектуру структуры данных приложения. То есть переписать логику программы так, чтобы не приходилось вставлять в середину массива, обычно это возможно.

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

Comments

[ddd329]

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

С чего это вы взяли?

[dollar]

ddd329, с чего я взял, что в список вставка происходит быстро? Естественно, при наличии ссылки на элемент, после которого (или до) нужно вставить.

[ddd329]

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

[dollar]

ddd329, да

[ddd329]

dollar, понятно.
Спасибо!

Answer 2

[ddd329]

Приветствую!

Если отвечать прямо на поставленный вопрос, то это плохо тем, что в среднем половину элементов придется сдвигать.

Вопрос почти философский, и есть ли алгоритмы более лучше чем которые я описал?

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

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

В .Net Framework над массивом реализован абстрактный тип данных (АТД) - список, т.е. List. Так вот там при создании пустого списка, массив имеет длину 4 элемента, если необходимо будет вставить 5-ый элемент, то длина массива просто увеличивается в 2 раза, и станет равна 8-ми. Вставишь 9-ый элемент, то размер увеличиться до 16 и т.д.