Dlaczego usuwanie jest zwykle o wiele trudniejsze do wdrożenia niż wstawianie do wielu struktur danych?

33

Czy potrafisz wymyślić jakiś konkretny powód, dla którego usunięcie jest zwykle znacznie trudniejsze do wdrożenia niż wstawienie dla wielu (większości?) Struktur danych?

Szybki przykład: listy połączone. Wstawianie jest trywialne, ale usuwanie ma kilka specjalnych przypadków, które znacznie utrudniają. Samowyrównujące się drzewa wyszukiwania binarnego, takie jak AVL i czerwono-czarny, to klasyczne przykłady bolesnej implementacji usuwania.

Chciałbym powiedzieć, że ma to związek ze sposobem myślenia większości ludzi: łatwiej nam jest konstruktywnie definiować rzeczy, co ładnie prowadzi do łatwych wstawek.

algorithms data-structures Leo Brito
źródło
4
Co o pop, extract-min?
coredump
5
„Trudniejsze do wdrożenia” jest bardziej kwestią psychologii (poznania oraz mocnych i słabych stron ludzkiego umysłu) niż programowania (właściwości struktur danych i algorytmów).
poza
1
Jak myślę, o czym wspominał Coredump, stosy powinny być co najmniej tak łatwe do usunięcia jak add (w przypadku stosu opartego na tablicy, popping jest tylko zmniejszeniem wskaźnika [1], podczas gdy wypychanie może wymagać kopii całej tablicy, jeśli osiągniesz maksymalny rozmiar szyk). Istnieją również przypadki użycia, w których zakłada się, że wstawianie będzie częste, a usuwanie rzadziej, ale byłaby to bardzo magiczna struktura danych, w której liczba usunięć przekracza wstawienia. [1] Prawdopodobnie powinieneś również zerować niewidoczne teraz odniesienie do pękniętego obiektu, aby uniknąć wycieków pamięci, co pamiętam, ponieważ nie zrobił tego podręcznik
Liskowa
43
„Kelner, czy mógłbyś dodać więcej majonezu do tej kanapki?” „Jasne, nie ma problemu, proszę pana”. „Czy możesz również usunąć całą musztardę?” „
Uch
3
Dlaczego odejmowanie jest bardziej skomplikowane niż dodawanie? Podział (czy rozkład na czynniki pierwsze) jest bardziej skomplikowany niż mnożenie? Korzenie bardziej skomplikowane niż potęgowanie?
mu jest za krótki

Odpowiedzi:

69

To coś więcej niż stan umysłu; istnieją fizyczne (tj. cyfrowe) powody, dla których usuwanie jest trudniejsze.

Po usunięciu pozostawiasz dziurę, w której kiedyś coś było. Technicznym terminem wynikowej entropii jest „fragmentacja”. Na połączonej liście wymaga to „załatania” usuniętego węzła i cofnięcia przydziału pamięci, której używa. W drzewach binarnych powoduje to niezrównoważenie drzewa. W systemach pamięci powoduje, że pamięć nie jest używana przez pewien czas, jeśli nowo przydzielone bloki są większe niż bloki pozostawione przez usunięcie.

Krótko mówiąc, wstawianie jest łatwiejsze, ponieważ możesz wybrać, gdzie chcesz wstawić. Usunięcie jest trudniejsze, ponieważ nie można z góry przewidzieć, który element zostanie usunięty.

Robert Harvey
źródło
3
Fragmentacja nie jest problemem, w którym mają zastosowanie wskaźniki i pośrednictwo, zarówno dla struktury w pamięci, jak i na diagramach. W pamięci nie ma znaczenia, gdzie istnieją poszczególne węzły z powodu pośrednictwa. W przypadku list usunięcie wewnętrznego węzła (w którym miałbyś dziurę w diagramie) wymaga nieco mniej operacji niż wstawienie (1 przypisanie wskaźnika i 1 wolny przydział i 1 przypisanie i 2 przypisania wskaźnika). W przypadku drzew wstawienie węzła może równoważyć drzewo tak samo jak usunięcie. Są to skrajne przypadki, które powodują trudności, o których mówi brito, w których fragmentacja nie ma znaczenia.
poza
12
Nie zgadzam się, że wstawki i skreślenia różnią się przewidywalnością. „Patchowanie wokół” węzła listy jest dokładnie tym, co dzieje się odwrotnie, jeśli zamiast tego ma zostać wstawiony ten sam węzeł. W żadnym punkcie nie ma żadnej niepewności w żadnym kierunku, a w każdym pojemniku bez wewnętrznej struktury jego elementów (np. Zrównoważone drzewo binarne, tablica o ścisłej relacji między przesunięciami elementów) w ogóle nie ma „dziury”. Dlatego obawiam się, że nie wiem o czym tu mówisz.
sqykly
2
Bardzo interesujące, ale powiedziałbym, że brakuje argumentów. Bez problemu możesz organizować struktury danych wokół prostego / szybkiego usuwania. Jest to po prostu mniej powszechne, prawdopodobnie również mniej przydatne.
luk32
@sqykly Myślę, że lista była złym wyborem, ponieważ wstawianie i relacja środkowa są równie trudne. Jeden przypadek przydziela pamięć, a drugi zostaje ponownie przydzielony. Jeden otwiera otwór, a drugi uszczelnia otwór. Więc nie wszystkie przypadki są bardziej złożone niż dodawanie.
ydobonebi
36

Dlaczego trudniej jest usunąć niż wstawić? Struktury danych są zaprojektowane bardziej z myślą o wstawianiu niż usuwaniu i słusznie.

Zastanów się - aby usunąć coś ze struktury danych, musi to być przede wszystkim. Musisz go najpierw dodać, co oznacza, że ​​co najwyżej masz tyle usunięć, ile wstawień. Jeśli zoptymalizujesz strukturę danych do wstawienia, masz gwarancję uzyskania co najmniej takiej samej korzyści, jak gdyby została zoptymalizowana do usunięcia.

Ponadto jaki jest pożytek z sekwencyjnego usuwania każdego elementu? Dlaczego nie wywołać jakiejś funkcji, która usuwa to wszystko naraz (być może po prostu tworząc nową)? Również struktury danych są najbardziej przydatne, gdy faktycznie coś zawierają. Tak więc przypadek usunięcia tylu elementów, ile wstawień, w praktyce nie będzie zbyt powszechny.

Kiedy coś optymalizujesz, chcesz zoptymalizować to, co robi najwięcej i które zajmuje najwięcej czasu. W normalnym użyciu usuwanie elementów struktury danych zdarza się rzadziej niż wstawianie.

Rob Watts
źródło
4
Jest jeden przypadek użycia, jaki mogę sobie wyobrazić. Struktura danych przygotowana do początkowego wprowadzenia, a następnie indywidualnego zużycia. Oczywiście jest to rzadki przypadek i niezbyt interesujący algorytmicznie, ponieważ, jak powiedziałeś, taka operacja nie może dominować nad wstawianiem asymptotycznie. Być może istnieje pewna nadzieja, że ​​wstawienie partii może całkiem dobrze zamortyzować koszt i być szybkie i łatwe do usunięcia, więc skomplikowane, ale praktyczne wprowadzenie partii oraz proste i szybkie indywidualne usuwanie. Z pewnością bardzo rzadka praktyczna potrzeba.
luk32
1
Ummm, myślę, że przykładem może być wektor w odwrotnej kolejności. Możesz kszybko dodać partię elementów: odwróć sortowanie danych wejściowych i scal z istniejącym wektorem - O(k log k + n). Następnie masz strukturę z dość skomplikowanym wstawianiem, ale zużywanie najlepszych uelementów jest banalne i szybkie. Po prostu weź ostatni ui przenieś koniec wektora. Chociaż, jeśli ktokolwiek kiedykolwiek potrzebuje takiej rzeczy, będę cholerny. Mam nadzieję, że to przynajmniej wzmocni twój argument.
luk32
Czy nie chcesz optymalizować pod kątem średniego wzorca użytkowania zamiast tego, co robisz najczęściej?
Shiv
Prosta kolejka robocza FIFO zazwyczaj próbuje być pusta przez większość czasu. Dobrze zaprojektowana kolejka zostanie dobrze zoptymalizowana (tj. O (1)) zarówno pod kątem wstawiania, jak i usuwania (a bardzo dobra kolejność będzie również obsługiwać szybkie operacje współbieżne, ale to inna kwestia).
Kevin
6

To nie jest trudniejsze.

W przypadku podwójnie połączonych list podczas wstawiania będziesz alokować pamięć, a następnie będziesz łączył się z nagłówkiem lub poprzednim węzłem, a także z ogonem lub następnym węzłem. Po usunięciu rozłączysz się dokładnie z tym samym, a następnie zwolnisz pamięć. Wszystkie te operacje są symetryczne.

Zakłada się, że w obu przypadkach masz węzeł do wstawienia / usunięcia. (A w przypadku wstawiania, że ​​masz również węzeł do wstawienia, więc w pewnym sensie wstawianie może być uważane za nieco bardziej skomplikowane.) Jeśli próbujesz usunąć, nie usuwając węzła, ale ładunek węzła, to oczywiście będziesz musiał najpierw przeszukać listę pod kątem ładunku, ale to nie jest wada usunięcia, prawda?

W przypadku zrównoważonych drzew to samo dotyczy: drzewo zasadniczo wymaga równoważenia natychmiast po wstawieniu, a także natychmiast po usunięciu. Dobrym pomysłem jest wypróbowanie tylko jednej procedury równoważenia i stosowanie jej po każdej operacji, niezależnie od tego, czy była to wstawianie, czy usuwanie. Jeśli próbujesz wprowadzić wstawkę, która zawsze pozostawia drzewo w równowadze, a także usunięcie, które zawsze pozostawia drzewo w równowadze, bez jednoczesnego korzystania z tej samej procedury równoważenia, niepotrzebnie komplikujesz swoje życie.

Krótko mówiąc, nie ma powodu, dla którego jedno powinno być trudniejsze od drugiego, a jeśli okaże się, że tak jest, to w rzeczywistości możliwe jest, że jesteś ofiarą (bardzo ludzkiej) tendencji, by uważać za bardziej naturalne myślenie konstruktywnie niż subtraktywnie, co oznacza, że ​​możesz implementować usuwanie w sposób, który jest bardziej skomplikowany niż to konieczne. Ale to ludzki problem. Z matematycznego punktu widzenia nie ma problemu.

Mike Nakis
źródło
1
Muszę się nie zgodzić. Algorytm usuwania AVL jest bardziej złożony niż wstawianie. W przypadku niektórych usunięć węzłów może być konieczne ponowne zrównoważenie całego drzewa, co zwykle wykonuje się rekurencyjnie, ale można to również zrobić nierekurencyjnie. Nie musisz tego robić w celu wstawienia. Nie jestem świadomy postępów algorytmu, w których we wszystkich przypadkach można uniknąć takiego równoważenia całego drzewa.
Dennis
@Dennis: może być tak, że drzewa AVL przestrzegają wyjątku, a nie reguły.
poza
@outis IIRC, wszystkie zrównoważone drzewa wyszukiwania mają bardziej skomplikowane procedury usuwania (niż wstawiania).
Raphael
Co z zamkniętymi tabelami mieszania? Wstawianie jest (względnie) proste, usuwanie jest co najmniej trudniejsze do konceptualizacji, ponieważ trzeba naprawić wszystkie „to, co miało być w indeksie X, znajduje się obecnie w indeksie Y i musimy go znaleźć i odłożyć” zagadnienia.
Kevin
3

Jeśli chodzi o czas wykonywania, patrząc na porównanie złożoności czasu operacji struktury danych na Wikipedii, zauważ, że operacje wstawiania i usuwania mają tę samą złożoność. Profilowana tam operacja usuwania polega na usunięciu według indeksu, w którym znajduje się odwołanie do elementu struktury do usunięcia; wstawianie jest według pozycji. Dłuższy czas usuwania w praktyce wynika z tego, że zwykle masz element do usunięcia, a nie jego indeks, więc potrzebujesz również operacji wyszukiwania. Większość struktur danych w tabeli nie wymaga dodatkowego wyszukiwania dla wstawki, ponieważ pozycja umieszczenia nie jest zależna od elementu lub pozycja jest ustalana domyślnie podczas wstawiania.

Jeśli chodzi o złożoność poznawczą, w pytaniu jest odpowiedź: przypadki skrajne. Usunięcie może zawierać ich więcej niż wstawienie (nie zostało to jeszcze ustalone w ogólnym przypadku). Jednak przynajmniej niektórym z tych przypadków brzegowych można uniknąć w niektórych projektach (np. Mieć węzeł wartowniczy na połączonej liście).

outis
źródło
2
„Większość struktur danych nie wymaga znalezienia wstawki”. -- Jak na przykład? W rzeczywistości miałbym przeciwne twierdzenie. („Znajdujesz” pozycję wstawiania, która jest tak samo droga jak znalezienie tego samego elementu później.)
Raphael,
@Raphael: Tę odpowiedź należy przeczytać w kontekście złożonej tabeli złożoności operacji, która nie obejmuje operacji wyszukiwania jako części operacji usuwania. W odpowiedzi na twoje pytanie skategoryzowałem strukturę według nazwy zwyczajowej. Z tablic, list, drzew, tablic mieszających, stosów, kolejek, stert i zestawów, drzewa i zestawy wymagają znalezienia wstawki; inni używają indeksu niepołączonego z przedmiotem (dla podstawowych stosów, kolejek i stosów, ujawniony jest tylko 1 indeks, a wyszukiwanie nie jest obsługiwane) lub obliczają go z przedmiotu. Wykresy mogą iść w obie strony, w zależności od sposobu ich użycia.
poza
... Próby można uznać za drzewa; jeśli jednak zostaną sklasyfikowane jako ich własna struktura, kwestia „znalezienia” podczas wstawiania jest bardziej kwestią dyskusyjną, więc nie uwzględniam tego. Uwaga: lista struktur danych nie bierze pod uwagę interfejsu vs implementacji. Również sposób liczenia zależy w dużej mierze od sposobu kategoryzacji. Zobaczę, czy mogę wymyślić bardziej obiektywne stwierdzenie.
poza
Przyznaję, że miałem na myśli interfejs słownika / zestawu (jak to często bywa w CS). W każdym razie ta tabela jest myląca, a (iirc) nawet błędna w kilku miejscach - Wikipedii, wgłębieniu błędnych informacji CS. : /
Raphael
0

Oprócz wszystkich wspomnianych problemów wiąże się to z integralnością referencyjną danych. Dla najbardziej poprawnie budowanej struktury danych, takiej jak bazy danych w SQL, integralność referencyjna Oracle jest bardzo ważna.
Aby upewnić się, że nie zniszczysz go przypadkowo, wymyślono wiele różnych rzeczy.
Na przykład kaskada usuwania, która nie tylko usuwa to, co próbujesz usunąć, ale także uruchamia czyszczenie powiązanych danych.
Ta oczyszczająca baza danych z niepotrzebnych danych, a także zachowuje nienaruszoną integralność danych.
Na przykład masz tabele z rodzicami i rodzajami jako powiązane rekordy w drugiej tabeli.
Gdzie rodzic jest głównym stołem. Jeśli nie masz wzmocnionej integralności referencyjnej, możesz usunąć dowolne rekordy w dowolnej tabeli, a później nie będziesz wiedział, jak uzyskać pełne informacje o rodzinie, ponieważ masz dane w tabeli podrzędnej i nic w tabeli nadrzędnej.
Dlatego sprawdzanie integralności referencyjnej nie pozwoli ci usunąć rekordu z tabeli nadrzędnej, dopóki rekordy z tabeli podrzędnej nie zostaną wyczyszczone.
I dlatego w większości źródeł danych trudniej jest usunąć dane.

Alex
źródło
Myślę, że pytanie dotyczyło struktur w pamięci, takich jak listy połączone, tabele skrótów itp., A nie baz danych, ale integralność referencyjna jest poważnym problemem nawet w przypadku struktur w pamięci.
supercat