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

33

Можете ли вы вспомнить какую-либо конкретную причину, по которой удаление обычно значительно сложнее реализовать, чем вставку для многих (большинства?) Структур данных?

Быстрый пример: связанные списки. Вставка тривиальна, но удаление имеет несколько особых случаев, которые значительно усложняют ее. Самобалансирующиеся бинарные деревья поиска, такие как AVL и Red-black, являются классическими примерами болезненной реализации удаления.

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

Лео Брито
источник
4
Как насчет pop, extract-min?
coredump
5
«Труднее реализовать» - это скорее вопрос психологии (познания, сильных и слабых сторон человеческого разума), чем программирования (свойства структур данных и алгоритмов).
outis 27.10.15
1
Как я полагаю в coredump, стеки должны быть, по крайней мере, такими же легкими для удаления, как и для добавления (для стека на основе массива выталкивание - это просто уменьшение указателя [1], в то время как нажатие может потребовать копию всего массива, если вы достигнете максимального размера массив). Также есть некоторые случаи использования, когда предполагается, что вставки будут частыми, а удаления - меньше, но это будет очень волшебная структура данных, где количество удалений превышает количество вставок. [1] Вероятно, вам следует также обнулить теперь невидимую ссылку на всплывающий объект, чтобы избежать утечек памяти, что я помню, потому что учебник Лискова этого не сделал
Foon
43
"Официант, не могли бы вы добавить еще майонез в этот бутерброд?" "Конечно, нет проблем, сэр." "Не могли бы вы также удалить всю горчицу?" «Эээ…»
cobaltduck
3
Почему вычитание сложнее, чем сложение? Деление (или первичная факторизация) сложнее, чем умножение? Корни сложнее, чем возведение в степень?
мю слишком коротко

Ответы:

69

Это больше, чем просто состояние души; Существуют физические (то есть цифровые) причины, по которым удаление сложнее.

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

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

Роберт Харви
источник
3
Фрагментация не является проблемой, когда указатели и косвенность вступают в игру как для структуры в памяти, так и для диаграмм. В памяти не имеет значения, где существуют отдельные узлы из-за косвенности. Для списков удаление внутреннего узла (в котором у вас будет дыра в диаграмме) включает в себя немного меньше операций, чем вставка (1 назначение указателя и 1 свободное против 1 выделения и 2 назначения указателя). Для деревьев вставка узла может разбалансировать дерево так же, как удаление. Это крайние случаи, которые вызывают трудности, на которые ссылается brito, где фрагментация не имеет значения.
вне
12
Я не согласен с тем, что вставки и удаления отличаются предсказуемостью. «Исправление» узла списка - это именно то, что происходит в обратном порядке, если вместо него будет вставлен тот же самый узел. Нет неопределенности ни в одном из направлений ни в одной точке, и в любом контейнере без внутренней структуры его элементов (например, сбалансированного двоичного дерева, массива со строгой взаимосвязью между смещениями элементов) вообще не существует «дыры». Поэтому, боюсь, я не знаю, о чем вы здесь говорите.
sqykly
2
Очень интересно, но я бы сказал, что аргументы пропущены. Вы можете организовать структуры данных вокруг простого / быстрого удаления без проблем. Это просто менее распространенное, скорее всего, менее полезное.
luk32
@sqykly Я думаю, что список был плохим примером выбора, потому что средняя вставка и среднее отношение одинаково трудны. Один случай выделяет память, где другой перераспределяется. Один открывает дыру там, где другой закрывает дыру. Так что не во всех случаях удалить сложнее, чем добавить.
ydobonebi
36

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

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

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

Когда вы оптимизируете что-то, вы хотите оптимизировать то, что оно делает больше всего и занимает больше всего времени. При обычном использовании удаление элементов структуры данных происходит реже, чем вставка.

Роб Уоттс
источник
4
Есть один вариант использования, который я могу себе представить. Структура данных, которая подготовлена ​​для первоначальной вставки, а затем для индивидуального потребления. Конечно, это редко, и алгоритмически это не очень интересно, потому что, как вы сказали, такая операция не может асимптотически доминировать над вставкой. Возможно, есть некоторая надежда на то, что пакетная вставка может иметь довольно амортизированную стоимость и быть быстрой и простой для удаления, так что это потребовало бы сложных, но практичных пакетных вставок и простых и быстрых отдельных удалений. Конечно, очень необычная практическая потребность.
luk32
1
Ммм, я думаю, что примером может быть вектор в обратном порядке. Вы можете добавить пакет kэлементов довольно быстро: выполнить обратную сортировку ввода и объединить с существующим вектором - O(k log k + n). Тогда у вас есть структура с довольно сложной вставкой, но потребление верхних uэлементов тривиально и быстро. Просто возьмите последнюю uи переместите конец вектора. Хотя, если кому-нибудь понадобится такая вещь, я буду проклят. Я надеюсь, что это по крайней мере укрепит ваш аргумент.
luk32
Разве вы не хотите оптимизировать для среднего шаблона использования, а не для того, что вы делаете больше всего?
Шив
Простая рабочая очередь FIFO обычно пытается пустовать большую часть времени. Хорошо спроектированная очередь будет хорошо оптимизирована (т. Е. O (1)) как для вставок, так и для удаления (и очень хорошая очередь также будет поддерживать быстрые параллельные операции, но это другая проблема).
Кевин
6

Это не сложнее.

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

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

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

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

Майк Накис
источник
1
Я должен не согласиться. Алгоритм удаления AVL сложнее, чем вставка. Для определенных удалений узлов может потребоваться перебалансировать все дерево, что обычно выполняется рекурсивно, но также может быть выполнено не рекурсивно. Вы не должны делать это для вставки. Я не знаю о продвижении алгоритма, где во всех случаях можно избежать такой перебалансировки всего дерева.
Деннис
@Dennis: может быть, что деревья AVL следуют за исключением, а не правилом.
outis
@outis IIRC, все сбалансированные деревья поиска имеют более сложные процедуры удаления (чем вставка).
Рафаэль
Как насчет закрытых хеш-таблиц? Вставка (относительно) прямолинейна, удаление, по крайней мере, сложнее осмыслить, так как вам нужно исправить все «то, что должно было быть в индексе X, в настоящее время находится в индексе Y, и мы должны найти его и вернуть обратно» вопросы.
Кевин
3

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

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

outis
источник
2
«Большинство структур данных не требуют поиска для вставки». -- такие как? Я бы сделал обратное утверждение, на самом деле. (Вы «находите» позицию вставки, что так же дорого, как найти тот же элемент позже.)
Рафаэль
@Raphael: Этот ответ следует читать в контексте связанной таблицы сложностей операций, которые не включают в себя операцию поиска как часть удаления. В ответ на ваш вопрос я классифицировал структуру по общему имени. Для массивов, списков, деревьев, хеш-таблиц, стеков, очередей, куч и наборов деревья и наборы требуют поиска для вставки; другие используют индекс, не связанный с элементом (для базовых стеков, очередей и куч, выставляется только 1 индекс, а поиск не поддерживается), или рассчитывают его по элементу. Графики могут идти в любом случае, в зависимости от того, как они используются.
Outis
... Попытки можно считать деревьями; однако, если они классифицируются как их собственная структура, то есть ли «находка» во время вставки, это больше вопрос дискуссии, поэтому я не включаю ее. Обратите внимание, что список структуры данных не учитывает интерфейс и реализацию. Кроме того, то, как вы считаете, во многом зависит от того, как вы классифицируете. Я посмотрю, смогу ли я придумать более объективное утверждение.
outis
Я признаю, что имел в виду интерфейс словарь / набор (как обычно в CS). Во всяком случае, эта таблица вводит в заблуждение и (iirc) даже неверна в нескольких местах - Википедия, яма дезинформации CS. : /
Рафаэль
0

Вдобавок ко всем упомянутым проблемам существует ссылочная целостность данных. Для наиболее правильно построенной структуры данных, такой как базы данных в SQL, ссылочная целостность Oracle очень важна.
Чтобы убедиться, что вы случайно не уничтожите его, придумано много разных вещей.
Например, каскад на удаление, который не только удаляет то, что вы пытаетесь удалить, но также запускает очистку связанных данных.
Это очищает базу данных от ненужных данных, а также сохраняет целостность данных.
Например, у вас есть таблицы с родителями и видами как связанные записи во второй таблице.
Где родитель является главной таблицей. Если у вас нет усиленной ссылочной целостности, вы можете удалить любые записи в любой таблице, и позже вы не будете знать, как получить полную информацию о семействе, потому что у вас есть данные в дочерней таблице и ничего в родительской таблице.
Вот почему проверка ссылочной целостности не позволит вам удалить запись из родительской таблицы, пока записи из дочерней таблицы не будут очищены.
И именно поэтому в большинстве источников данных сложнее удалить данные.

Alex
источник
Я думаю, что вопрос задавался о структурах в памяти, таких как связанные списки, хеш-таблицы и т. Д., А не о базах данных, но ссылочная целостность является серьезной проблемой даже со структурами в памяти.
суперкат