Por que a exclusão geralmente é muito mais difícil de implementar do que a inserção em muitas estruturas de dados?

33

Você pode pensar em algum motivo específico pelo qual a exclusão geralmente é significativamente mais difícil de implementar do que a inserção para muitas (a maioria?) Estruturas de dados?

Exemplo rápido: listas vinculadas. A inserção é trivial, mas a exclusão tem alguns casos especiais que tornam significativamente mais difícil. Árvores de pesquisa binária com auto balanceamento, como AVL e Vermelho-preto, são exemplos clássicos de implementação de exclusão dolorosa.

Eu gostaria de dizer que tem a ver com a maneira como as pessoas pensam: é mais fácil para nós definir as coisas de forma construtiva, o que leva muito a inserções fáceis.

algorithms data-structures Leo Brito
fonte
4
Que tal pop, extract-min?
coredump
5
"Mais difícil de implementar" é mais uma questão de psicologia (cognição e pontos fortes e fracos da mente humana) do que de programação (propriedades de estruturas de dados e algoritmos).
Outis
1
Como eu acho que o coredump aludiu, as pilhas devem ser pelo menos tão fáceis de excluir quanto adicionar (para uma pilha suportada por array, o popping é apenas um decréscimo de ponteiro [1] enquanto empurrar pode exigir uma cópia inteira do array se você atingir o tamanho máximo do array). Também existem alguns casos de uso em que se supõe que as inserções serão freqüentes e as exclusões menos, mas seria uma estrutura de dados muito mágica em que o número de exclusões excede as inserções. [1] Você provavelmente também deve anular a referência agora invisível ao objeto popped para evitar vazamentos de memória, o que me lembro porque o livro de Liskov não fez
Foon
43
"Garçom, você poderia adicionar mais maionese a esse sanduíche?" "Claro, sem problemas, senhor." "Você também pode remover toda a mostarda?" "Uh ......"
cobaltduck 27/10/2015
3
Por que a subtração é mais complicada do que a adição? Divisão (ou fatoração primária) mais complicada do que multiplicação? Raízes mais complicadas do que exponenciação?
mu é muito curto

Respostas:

69

É mais do que apenas um estado de espírito; existem razões físicas (ou seja, digitais) pelas quais a exclusão é mais difícil.

Quando você exclui, deixa um buraco onde costumava estar. O termo técnico para a entropia resultante é "fragmentação". Em uma lista vinculada, isso exige que você "remova" o nó removido e desaloque a memória que está usando. Em árvores binárias, causa desequilíbrio da árvore. Nos sistemas de memória, ela faz com que a memória não seja usada por algum tempo se os blocos recém-alocados forem maiores que os blocos deixados para trás pela exclusão.

Em resumo, a inserção é mais fácil porque você escolhe onde deseja inserir. A exclusão é mais difícil, porque você não pode prever com antecedência qual item será excluído.

Robert Harvey
fonte
3
A fragmentação não é um problema em que ponteiros e indiretos entram em cena, tanto para a estrutura na memória quanto para os diagramas. Na memória, não importa onde existem nós individuais devido à indireção. Para listas, a exclusão de um nó interno (que é onde você teria um furo no diagrama) envolve um pouco menos de operações do que a inserção (1 atribuição de ponteiro e 1 livre versus 1 alocação e 2 atribuições de ponteiro). Para árvores, a inserção de um nó pode desequilibrar uma árvore tanto quanto a exclusão. São os casos extremos que causam as dificuldades às quais Brito se refere, onde a fragmentação não importa.
Outis
12
Discordo que inserções e exclusões diferem em previsibilidade. "Corrigir" um nó da lista é exatamente o que acontece ao contrário, se o mesmo nó for inserido. Não há incerteza em nenhuma direção em nenhum momento, e em qualquer container sem estrutura intrínseca aos seus elementos (por exemplo, uma árvore binária balanceada, uma matriz com uma relação estrita entre compensações de elementos), não existe "buraco". Portanto, receio não saber do que você está falando aqui.
Sqykly 27/10/2015
2
Muito interessante, mas eu diria que os argumentos são perdidos. Você pode organizar estruturas de dados em torno da exclusão simples / rápida sem nenhum problema. É apenas menos comum, provavelmente menos útil também.
Luk32
@sqykly Acho que a lista foi um exemplo de má escolha porque a inserção e a relação do meio são igualmente difíceis. Um caso aloca memória onde o outro realocado. Um abre um buraco onde o outro sela um buraco. Portanto, nem todos os casos são excluídos mais complexos que os adicionados.
ydobonebi
36

Por que é mais difícil excluir do que inserir? As estruturas de dados são projetadas mais com a inserção em mente do que com a exclusão, e com razão.

Considere isso - para excluir algo de uma estrutura de dados, ele deve estar lá em primeiro lugar. Portanto, você precisa adicioná-lo primeiro, o que significa que, no máximo, você tem tantas exclusões quanto inserções. Se você otimizar uma estrutura de dados para inserção, terá a garantia de obter pelo menos o mesmo benefício que se tivesse sido otimizado para exclusão.

Além disso, de que serve a exclusão seqüencial de cada elemento? Por que não chamar uma função que a limpa de uma só vez (possivelmente apenas criando uma nova)? Além disso, as estruturas de dados são mais úteis quando na verdade contêm algo. Portanto, o caso de ter tantas exclusões quanto inserções, na prática, não será muito comum.

Quando você otimiza algo, deseja otimizar as coisas que mais fazem e que levam mais tempo. No uso normal, a exclusão de elementos de uma estrutura de dados ocorre com menos frequência do que a inserção.

Rob Watts
fonte
4
Há um caso de uso que posso imaginar. Uma estrutura de dados preparada para inserção inicial e, em seguida, consumo individual. É claro que é um caso raro, e não muito interessante por algoritmo, porque, como você disse, essa operação não pode dominar a inserção assintoticamente. Talvez exista alguma esperança de que a inserção de lotes possa ter um custo amortizado muito bom e ser rápida e simples para exclusão, portanto, haveria inserções de lotes complicadas, porém práticas, e exclusões individuais simples e rápidas. Certamente uma necessidade prática muito incomum.
Luk32
1
Ummm, acho que um exemplo pode ser um vetor de ordem inversa. Você pode adicionar um lote kde elementos rapidamente: inverter a entrada de classificação e mesclar com o vetor existente - O(k log k + n). Então você tem uma estrutura com inserção bastante complicada, mas consumir os principais uelementos é trivial e rápido. Basta pegar por último ue mover o final do vetor. No entanto, se alguém precisar de algo assim, eu serei amaldiçoado. Espero que isso ao menos reforce seu argumento.
Luk32
Você não deve otimizar o padrão de uso médio e não o que mais faz?
Shiv
Uma fila de trabalho FIFO simples normalmente tenta ficar vazia a maior parte do tempo. Uma fila bem projetada será bem otimizada (ou seja, O (1)) para inserções e exclusões (e uma muito boa também suportará operações simultâneas rápidas, mas essa é uma questão diferente).
Kevin
6

Não é mais difícil.

Com listas duplamente vinculadas, quando você insere, alocará memória e, em seguida, vinculará à cabeça ou ao nó anterior e à cauda ou ao nó seguinte. Ao excluir, você desvinculará exatamente da mesma e liberará memória. Todas essas operações são simétricas.

Isso pressupõe que, nos dois casos, você tenha o nó para inserir / excluir. (E, no caso da inserção, que você também tem o nó para inserir antes, de certa forma, a inserção pode ser considerada um pouco mais complicada.) Se você estiver tentando excluir, não tendo o nó a excluir, mas a carga útil do nó, é claro que você terá que pesquisar primeiro na lista a carga útil, mas isso não é uma falha de exclusão, é?

Com árvores balanceadas, o mesmo se aplica: uma árvore geralmente precisa ser balanceada imediatamente após uma inserção e também imediatamente após uma exclusão. É uma boa idéia tentar ter apenas uma rotina de balanceamento e aplicá-la após cada operação, independentemente de se tratar de uma inserção ou exclusão. Se você está tentando implementar uma inserção que sempre deixa a árvore equilibrada e também uma exclusão que sempre a deixa equilibrada, sem que os dois compartilhem a mesma rotina de equilíbrio, você está desnecessariamente complicando sua vida.

Em suma, não há razão para que um seja mais difícil que o outro, e se você estiver descobrindo que é, é possível que você seja vítima da tendência (muito humana) de achar mais natural pensar de forma construtiva e subtraída, o que significa que você pode estar implementando a exclusão de uma maneira mais complicada do que precisa. Mas isso é uma questão humana. Do ponto de vista matemático, não há problema.

Mike Nakis
fonte
1
Eu tenho que discordar. O algoritmo de exclusão de AVL é mais complexo que a inserção. Para determinadas exclusões de nós, talvez seja necessário reequilibrar a árvore inteira, o que geralmente é feito de forma recursiva, mas também pode ser feito de forma não recursiva. Você não precisa fazer isso para inserção. Não estou ciente dos avanços do algoritmo em que esse reequilíbrio de árvore inteira pode ser evitado em todos os casos.
Dennis
@ Dennis: pode ser que as árvores AVL sigam a exceção e não a regra.
Outis
@outis IIRC, todas as árvores de pesquisa balanceadas têm rotinas de exclusão mais complicadas (do que inserção).
Raphael
E as tabelas de hash de hash fechado ? A inserção é (relativamente) direta, a exclusão é pelo menos mais difícil de conceituar, já que você precisa consertar toda a "coisa que deveria estar no índice X está atualmente no índice Y e precisamos procurar e colocar de volta" problemas.
Kevin
3

Em termos de tempo de execução, observando a comparação da complexidade de tempo das operações da estrutura de dados na Wikipedia, observe que as operações de inserção e exclusão têm a mesma complexidade. A operação de exclusão perfilada é excluída por índice, onde você tem uma referência ao elemento de estrutura a ser excluído; inserção é por item. O tempo de execução mais longo para exclusão na prática é porque você geralmente tem um item para excluir e não seu índice, portanto, você também precisa de uma operação de localização. A maioria das estruturas de dados na tabela não exige uma localização adicional para uma inserção porque a posição da veiculação não depende do item ou a posição é determinada implicitamente durante a inserção.

Quanto à complexidade cognitiva, há uma resposta na pergunta: casos extremos. A exclusão pode ter mais do que inserção (isso ainda não foi estabelecido no caso geral). No entanto, pelo menos alguns desses casos extremos podem ser evitados em determinados projetos (por exemplo, ter um nó sentinela em uma lista vinculada).

fora
fonte
2
"A maioria das estruturas de dados não exige uma localização para uma inserção." -- tal como? Eu faria a afirmação oposta, de fato. (Você "encontra" a posição de inserção, que é tão cara quanto encontrar o mesmo elemento novamente mais tarde).
Raphael
@ Rafael: Esta resposta deve ser lida no contexto das complexidades vinculadas da tabela de operações, que não incluem a operação de busca como parte da exclusão. Em resposta à sua pergunta, categorizei estrutura por nome comum. De matrizes, listas, árvores, tabelas de hash, pilhas, filas, montões e conjuntos, árvores e conjuntos requerem uma localização para uma inserção; os outros usam um índice não conectado ao item (para pilhas básicas, filas e pilhas, apenas 1 índice é exposto e a descoberta não é suportada) ou calcula-o a partir do item. Os gráficos podem ser usados ​​de qualquer maneira, dependendo de como são usados.
Outis
... Tentativas podem ser consideradas árvores; no entanto, se classificado como sua própria estrutura, se há uma "descoberta" durante a inserção é mais uma questão de debate, então não a incluo. Observe que a lista de estrutura de dados não leva em consideração interface versus implementação. Além disso, como você conta depende muito de como você categoriza. Vou ver se consigo pensar em uma afirmação mais objetiva.
Outis
Admito que tinha em mente a interface dicionário / conjunto (como comum no CS). De qualquer forma, essa tabela é enganosa e (iirc) até errada em vários lugares - Wikipedia, o poço da desinformação do CS. : /
Raphael
0

Além de todos os problemas mencionados, há integridade referencial de dados envolvida. Para criar a estrutura de dados mais adequada, como bancos de dados em SQL, a integridade referencial da Oracle é muito importante.
Para garantir que você não o destrua acidentalmente, muitas coisas diferentes foram inventadas.
Por exemplo, cascata ao excluir, que não apenas exclui o que você tenta excluir, mas também aciona a limpeza dos dados relacionados.
Isso limpa o banco de dados a partir de dados indesejados e mantém intacta a integridade dos dados.
Por exemplo, você tem tabelas com pais e tipos como registros relacionados na segunda tabela.
Onde pai é a tabela principal. Se você não tiver integridade referencial reforçada, poderá excluir todos os registros de qualquer tabela e, posteriormente, não saberia como obter informações completas da família, pois possui dados na tabela filho e nada na tabela pai.
É por isso que a verificação de integridade referencial não permite excluir o registro da tabela pai até que os registros da tabela filho sejam limpos.
E é por isso que na maioria das fontes de dados é mais difícil excluir dados.

Alex
fonte
Eu acho que a pergunta estava perguntando sobre estruturas na memória, como listas vinculadas, tabelas de hash, etc., em vez de bancos de dados, mas a integridade referencial é um problema importante, mesmo com estruturas na memória.
Supercat