Jaki rodzaj algorytmu wymaga zestawu?

Na moich pierwszych kursach programowania mówiono mi, że powinienem używać zestawu, gdy muszę robić rzeczy takie jak usuwanie duplikatów czegoś. Np .: aby usunąć wszystkie duplikaty z wektora, iteruj przez ten wektor i dodaj każdy element do zestawu, a następnie pozostaną Ci niepowtarzalne zdarzenia. Mógłbym jednak to zrobić, dodając każdy elemento do innego wektora i sprawdzając, czy element już istnieje. Zakładam, że w zależności od używanego języka może występować różnica w wydajności. Ale czy istnieje powód, aby używać zestawu innego niż ten?

Zasadniczo: jakiego rodzaju algorytmy wymagają zestawu i nie należy tego robić z żadnym innym typem kontenera?

Pytasz konkretnie o zbiory, ale myślę, że twoje pytanie dotyczy szerszej koncepcji: abstrakcji. Masz całkowitą rację, że możesz to zrobić za pomocą Vector (jeśli używasz Javy, zamiast tego użyj ArrayList.) Ale po co to robić? Do czego potrzebujesz Vector? Możesz to wszystko zrobić za pomocą tablic.

Kiedykolwiek potrzebujesz dodać element do tablicy, możesz po prostu zapętlić każdy element, a jeśli go nie ma, dodajesz go na końcu. Ale tak naprawdę musisz najpierw sprawdzić, czy w tablicy jest miejsce. Jeśli nie, musisz utworzyć nową tablicę, która jest większa i skopiować wszystkie istniejące elementy ze starej tablicy do nowej, a następnie możesz dodać nowy element. Oczywiście musisz także zaktualizować każde odwołanie do starej tablicy, aby wskazywało na nową. Zrobiłeś to wszystko? Świetny! Co teraz próbowaliśmy osiągnąć ponownie?

Lub zamiast tego możesz użyć instancji Set i po prostu zadzwonić add(). Powodem istnienia zestawów jest to, że są abstrakcją przydatną w wielu typowych problemach. Załóżmy na przykład, że chcesz śledzić elementy i reagować na dodanie nowego. Wywołujesz add()zestaw, a on zwraca truelub falsezależy od tego, czy zestaw został zmodyfikowany. Możesz to wszystko napisać ręcznie, używając prymitywów, ale dlaczego?

Może istnieć przypadek, w którym masz Listę i chcesz usunąć duplikaty. Algorytm, który proponujesz, jest w zasadzie najwolniejszym sposobem, w jaki możesz to zrobić. Istnieje kilka typowych szybszych sposobów: grupowanie ich lub sortowanie. Lub możesz dodać je do zestawu, który implementuje jeden z tych algorytmów.

Na wczesnym etapie kariery zawodowej / edukacji główny nacisk kładziony jest na budowanie tych algorytmów i ich zrozumienie, dlatego ważne jest, aby to zrobić. Ale nie tak robią profesjonalni programiści w normalny sposób. Wykorzystują te podejścia do budowania o wiele bardziej interesujących rzeczy, a korzystanie z gotowych i niezawodnych implementacji pozwala zaoszczędzić mnóstwo czasu.

Zakładam, że w zależności od używanego języka może występować różnica w wydajności. Ale czy istnieje powód, aby używać zestawu innego niż ten?

O tak, (ale to nie jest wydajność).

Użyj zestawu, gdy możesz go użyć, ponieważ nieużywanie go oznacza, że ​​musisz napisać dodatkowy kod. Korzystanie z zestawu ułatwia czytanie. Całe to testowanie logiki unikatowości jest ukryte gdzie indziej, gdzie nie musisz o tym myśleć. Jest w miejscu, które zostało już przetestowane i możesz zaufać, że działa.

Napisz własny kod, aby to zrobić, i musisz się o to martwić. Bleh Kto chce to zrobić?

Zasadniczo: jakiego rodzaju algorytmy wymagają zestawu i nie należy tego robić z żadnym innym typem kontenera?

Nie ma algorytmu, który „nie powinien być wykonywany z żadnym innym typem kontenera”. Są po prostu algorytmy, które mogą korzystać z zestawów. To miłe, gdy nie musisz pisać dodatkowego kodu.

Teraz nie ma w tym względzie nic szczególnego. Zawsze powinieneś korzystać z kolekcji, która najlepiej odpowiada Twoim potrzebom. W java znalazłem to zdjęcie, które było pomocne w podjęciu tej decyzji. Zauważysz, że ma trzy różne rodzaje zestawów.

I jak słusznie wskazuje @germi, jeśli użyjesz odpowiedniej kolekcji do zadania, Twój kod stanie się łatwiejszy do odczytania dla innych.

Mógłbym jednak to zrobić, dodając każdy elemento do innego wektora i sprawdzając, czy element już istnieje.

Jeśli to zrobisz, wówczas implementujesz semantykę zestawu na szczycie wektorowej struktury danych. Piszesz dodatkowy kod (który może zawierać błędy), a wynik będzie bardzo wolny, jeśli będziesz mieć dużo wpisów.

Dlaczego chcesz to zrobić, używając istniejącej, przetestowanej i wydajnej implementacji zestawu?

Elementy oprogramowania reprezentujące elementy świata rzeczywistego często są zestawami logicznymi. Na przykład rozważ samochód. Samochody mają unikalne identyfikatory, a grupa samochodów tworzy zestaw. Pojęcie zestawu służy jako ograniczenie w gromadzeniu samochodów, o którym program może wiedzieć, a ograniczenie wartości danych jest bardzo cenne.

Również zestawy mają bardzo dobrze zdefiniowaną algebrę. Jeśli masz zestaw samochodów należących do George'a i zestaw należący do Alice, związek jest oczywiście zestawem, który należy zarówno do George'a, jak i Alice, nawet jeśli George i Alice są właścicielami tego samego samochodu. Algorytmy, które powinny używać zbiorów, to te, w których logika zaangażowanych podmiotów wykazuje cechy zestawu. To okazuje się dość powszechne.

W jaki sposób zestawy są wdrażane i jak zagwarantowane jest ograniczenie unikalności, to inna sprawa. Mamy nadzieję, że uda się znaleźć odpowiednią implementację dla logiki zestawu, która eliminuje duplikaty, biorąc pod uwagę, że zbiory są tak fundamentalne dla logiki, ale nawet jeśli wykonasz tę implementację samodzielnie, gwarancja niepowtarzalności jest nieodłączna od wstawienia elementu do zestawu i nie powinno być „sprawdzania, czy element już istnieje”.

Oprócz cech wydajności (które są bardzo znaczące i nie powinny być tak łatwo odrzucane), Zestawy są bardzo ważne jako kolekcja abstrakcyjna.

Czy możesz emulować zachowanie Set (ignorowanie wydajności) za pomocą tablicy? Tak, absolutnie! Za każdym razem, gdy wstawiasz, możesz sprawdzić, czy element jest już w tablicy, a następnie dodać element tylko, jeśli jeszcze go nie znaleziono. Ale jest to coś, o czym musisz świadomie pamiętać i pamiętać za każdym razem, gdy wkładasz swój zestaw Array-Psuedo. Och, co to jest, wstawiłeś raz bezpośrednio, bez uprzedniego sprawdzania duplikatów? Welp, twoja tablica złamała niezmiennik (że wszystkie elementy są unikalne i równoważnie, że nie ma duplikatów).

Co byś zrobił, żeby to obejść? Utworzyłbyś nowy typ danych, nazwałbyś go (powiedzmy PsuedoSet), który otacza wewnętrzną tablicę i ujawnia insertpublicznie operację, która wymusi unikalność elementów. Ponieważ zapakowana tablica jest dostępna tylko za pośrednictwem tego publicznego insertinterfejsu API, gwarantujesz, że duplikaty nigdy się nie pojawią. Teraz dodaj trochę haszowania, aby poprawić wydajność containskontroli, a wcześniej czy później zdasz sobie sprawę, że zaimplementowałeś pełną wersję Set.

Odpowiedziałbym również oświadczeniem i odpowiedziałem na pytanie:

Na moich pierwszych kursach programistycznych powiedziano mi, że powinienem używać macierzy, ilekroć muszę robić takie rzeczy, jak przechowywanie wielu zamówionych elementów czegoś. Np .: do przechowywania zbioru nazwisk współpracowników. Mógłbym jednak to zrobić, przydzielając surową pamięć i ustawiając wartość adresu pamięci podanego przez wskaźnik początkowy + pewne przesunięcie.

Czy możesz użyć surowego wskaźnika i stałych przesunięć, aby naśladować tablicę? Tak, absolutnie! Za każdym razem, gdy wstawiasz, możesz sprawdzić, czy przesunięcie nie zejdzie z końca przydzielonej pamięci, z którą pracujesz. Ale jest to coś, o czym musisz świadomie pamiętać i pamiętać za każdym razem, gdy wstawiasz do swojego Pseudo-Tablicy. Och, co to jest, wstawiłeś raz bezpośrednio, bez uprzedniego sprawdzenia przesunięcia? Welp, występuje błąd segmentacji z Twoim nazwiskiem!

Co byś zrobił, żeby to obejść? Utworzyłbyś nowy typ danych, nazwałbyś go (powiedzmy PsuedoArray), który otacza wskaźnik i rozmiar i ujawnia insertpublicznie operację, która wymusi, że przesunięcie nie przekroczy rozmiaru. Ponieważ zapakowane dane są dostępne tylko za pośrednictwem tego publicznego insertinterfejsu API, gwarantujesz, że nie nastąpi przepełnienie bufora. Teraz dodaj kilka innych funkcji wygody (zmiana rozmiaru tablicy, usuwanie elementów itp.), A wcześniej czy później zdasz sobie sprawę, że zaimplementowałeś pełny efekt Array.

Istnieją wszelkiego rodzaju algorytmy oparte na zestawach, szczególnie tam, gdzie trzeba wykonać przecięcia i połączenia zbiorów i uzyskać wynik jako zestaw.

Algorytmy oparte na zestawie są szeroko stosowane w różnych algorytmach wyszukiwania ścieżek itp.

Aby zapoznać się z podstawową teorią zbiorów, sprawdź ten link: http://people.umass.edu/partee/NZ_2006/Set%20Theory%20Basics.pdf

Jeśli potrzebujesz semantyki zestawu, użyj zestawu. Pozwoli to uniknąć błędów z powodu fałszywych duplikatów, ponieważ na pewnym etapie zapomniałeś przycinać wektor / listę, a będzie to szybsze niż możesz to zrobić przez ciągłe przycinanie wektora / listy.

Właściwie uważam, że standardowe zestawy kontenerów są w większości bezużyteczne i wolę po prostu używać tablic, ale robię to w inny sposób.

Aby obliczyć przecięcia zestawów, iteruję pierwszą tablicę i zaznaczam elementy jednym bitem. Następnie iteruję drugą tablicę i szukam zaznaczonych elementów. Voila, ustaw przecięcie w czasie liniowym z dużo mniejszą pracą i pamięcią niż tablica skrótu, np. Związki i różnice można równie łatwo zastosować przy użyciu tej metody. Pomaga to, że moja baza kodu obraca się wokół indeksowania elementów, a nie powielania ich (duplikuję indeksy do elementów, a nie danych samych elementów) i rzadko wymaga sortowania, ale od lat nie używałem ustalonej struktury danych wynik.

Mam też zły kod C, który używam, nawet gdy elementy nie oferują pola danych do takich celów. Polega ona na wykorzystaniu pamięci samych elementów poprzez ustawienie najbardziej znaczącego bitu (którego nigdy nie używam) w celu oznaczenia przemieszczonych elementów. To dość obrzydliwe, nie rób tego, chyba że naprawdę pracujesz na poziomie prawie montażowym, ale chciałem tylko wspomnieć, w jaki sposób można je zastosować nawet w przypadkach, gdy elementy nie zapewniają pola specyficznego dla przejścia, jeśli możesz to zagwarantować pewne bity nigdy nie zostaną użyte. Może obliczyć ustawione przecięcie między 200 milionami elementów (około 2,4 gigabajtów danych) w niecałą sekundę na moim dinky i7. Spróbuj wykonać ustawione skrzyżowanie dwóch std::setinstancji zawierających sto milionów elementów w tym samym czasie; nawet się nie zbliża.

To na bok ...

Mógłbym jednak to zrobić, dodając każdy elemento do innego wektora i sprawdzając, czy element już istnieje.

To sprawdzenie, czy element już istnieje w nowym wektorze, będzie na ogół liniową operacją czasową, co sprawi, że samo skrzyżowanie stanie się operacją kwadratową (gwałtowna ilość pracy tym większy rozmiar wejściowy). Polecam powyższą technikę, jeśli chcesz po prostu użyć zwykłych starych wektorów lub tablic i zrobić to w sposób, który świetnie się skaluje.

Zasadniczo: jakiego rodzaju algorytmy wymagają zestawu i nie należy tego robić z żadnym innym typem kontenera?

Brak, jeśli zapytasz moją stronniczą opinię, czy mówisz o tym na poziomie kontenera (jak w strukturze danych specjalnie zaimplementowanej w celu wydajnego zapewniania operacji na zestawach), ale jest wiele rzeczy, które wymagają logiki zestawu na poziomie koncepcyjnym. Załóżmy na przykład, że chcesz znaleźć stwory w świecie gry, które potrafią zarówno latać, jak i pływać, a latające stwory znajdują się w jednym zestawie (niezależnie od tego, czy faktycznie używasz zestawu pojemników), i te, które mogą pływać w innym . W takim przypadku chcesz ustawić skrzyżowanie. Jeśli chcesz stworów, które potrafią latać lub są magiczne, użyj zestawu unii. Oczywiście nie potrzebujesz zestawu kontenerów, aby to zaimplementować, a najbardziej optymalna implementacja na ogół nie potrzebuje lub nie chce, aby kontener specjalnie zaprojektowany był zestawem.

Going Off Tangent

W porządku, mam kilka fajnych pytań od JimmyJamesa dotyczących tego ustawionego podejścia do skrzyżowania. To trochę odwraca się od tematu, ale no cóż, interesuje mnie to, że więcej ludzi używa tego podstawowego natrętnego podejścia do ustawiania skrzyżowania, aby nie budowali całych struktur pomocniczych, takich jak zrównoważone drzewa binarne i tabele skrótów tylko do celów ustawiania operacji. Jak wspomniano, podstawowym wymaganiem jest to, aby listy miały płytkie elementy, tak aby indeksowały lub wskazywały na wspólny element, który może być „oznaczony” podczas przejścia przez pierwszą nieposortowaną listę lub tablicę lub cokolwiek, aby następnie pobrać drugą przejść przez drugą listę.

Można to jednak osiągnąć praktycznie nawet w kontekście wielowątkowości bez dotykania elementów, pod warunkiem że:

1. Te dwa agregaty zawierają wskaźniki dla elementów.
2. Zakres wskaźników nie jest zbyt duży (powiedzmy [0, 2 ^ 26), nie miliardy lub więcej) i są dość gęsto zajęte.

To pozwala nam używać tablicy równoległej (tylko jeden bit na element) do celów ustawiania operacji. Diagram:

Synchronizacja wątków musi istnieć tylko podczas pobierania równoległej tablicy bitów z puli i zwalniania jej z powrotem do puli (odbywa się to domyślnie, gdy wychodzi poza zakres). Rzeczywiste dwie pętle do wykonania operacji ustawiania nie muszą obejmować żadnych synchronizacji wątków. Nie musimy nawet używać równoległej puli bitów, jeśli wątek może po prostu lokalnie przydzielić i zwolnić bity, ale pula bitów może być przydatna do uogólnienia wzorca w bazach kodowych, które pasują do tego rodzaju reprezentacji danych, do których często odwoływane są elementy centralne według indeksu, aby każdy wątek nie musiał niepokoić się efektywnym zarządzaniem pamięcią. Najważniejszymi przykładami dla mojego obszaru są systemy elementów-bytów i indeksowane reprezentacje siatki. Oba często wymagają ustawienia skrzyżowań i zwykle odnoszą się do wszystkiego przechowywanego centralnie (komponenty i elementy w ECS i wierzchołkach, krawędziach,

Jeśli indeksy nie są gęsto zajęte i rzadko rozproszone, ma to nadal zastosowanie w przypadku rozsądnej rzadkiej implementacji równoległej tablicy bitów / boolean, takiej jak ta, która przechowuje pamięć tylko w 512-bitowych porcjach (64 bajty na rozwinięty węzeł reprezentujących 512 ciągłych wskaźników ) i pomija przydzielanie całkowicie pustych ciągłych bloków. Możliwe, że już używasz czegoś takiego, jeśli twoje centralne struktury danych są rzadko zajęte przez same elementy.

... podobny pomysł na rzadki zestaw bitów służący jako równoległa tablica bitów. Struktury te nadają się również do niezmienności, ponieważ łatwo kopiować grube bloki, które nie muszą być głęboko kopiowane, aby utworzyć nową niezmienną kopię.

Znów ustawione przecięcia między setkami milionów elementów można wykonać w ciągu sekundy za pomocą tego podejścia na bardzo przeciętnej maszynie, i to w ramach jednego wątku.

Można to również zrobić w czasie krótszym niż połowa czasu, jeśli klient nie potrzebuje listy elementów do wynikowego skrzyżowania, na przykład jeśli chce zastosować tylko logikę do elementów znajdujących się na obu listach, w którym momencie może po prostu przejść wskaźnik funkcji, funktor, delegat lub cokolwiek, co zostanie ponownie wywołane w celu przetworzenia zakresów przecinających się elementów. Coś w tym celu:

// 'func' receives a range of indices to
// process.
set_intersection(func):
{
    parallel_bits = bit_pool.acquire()

    // Mark the indices found in the first list.
    for each index in list1:
        parallel_bits[index] = 1

    // Look for the first element in the second list 
    // that intersects.
    first = -1
    for each index in list2:
    {
         if parallel_bits[index] == 1:
         {
              first = index
              break
         }
    }

    // Look for elements that don't intersect in the second
    // list to call func for each range of elements that do
    // intersect.
    for each index in list2 starting from first:
    {
        if parallel_bits[index] != 1:
        {
             func(first, index)
             first = index
        }
    }
    If first != list2.num-1:
        func(first, list2.num)
}

... lub coś w tym rodzaju. Najdroższa część pseudokodu na pierwszym schemacie znajduje się intersection.append(index)w drugiej pętli, i dotyczy to z góry std::vectorzarezerwowanej wielkości mniejszej listy.

Co się stanie, jeśli wszystko skopiuję głęboko?

Cóż, przestań! Jeśli musisz ustawić skrzyżowania, oznacza to, że kopiujesz dane, z którymi się przecinasz. Możliwe, że nawet twoje najmniejsze obiekty nie są mniejsze niż indeks 32-bitowy. Bardzo możliwe jest zmniejszenie zakresu adresowania elementów do 2 ^ 32 (2 ^ 32 elementy, a nie 2 ^ 32 bajty), chyba że faktycznie potrzebujesz więcej niż ~ 4,3 miliarda elementów, w tym momencie potrzebne jest zupełnie inne rozwiązanie ( i to zdecydowanie nie używa ustawionych kontenerów w pamięci).

Kluczowe dopasowania

Co z przypadkami, w których musimy wykonać operacje ustawiania, w których elementy nie są identyczne, ale mogą mieć pasujące klucze? W takim przypadku ten sam pomysł jak powyżej. Musimy tylko mapować każdy unikalny klucz do indeksu. Jeśli klucz jest na przykład łańcuchem, to mogą to zrobić internowane łańcuchy. W takich przypadkach potrzebna jest ładna struktura danych, taka jak tabela trie lub tablica skrótów, aby odwzorować klucze łańcuchowe na indeksy 32-bitowe, ale nie potrzebujemy takich struktur do wykonania operacji ustawiania na wynikowych indeksach 32-bitowych.

Wiele takich bardzo tanich i prostych rozwiązań algorytmicznych i struktur danych otwiera się, gdy możemy pracować z indeksami elementów w bardzo rozsądnym zakresie, a nie w pełnym zakresie adresowania maszyny, dlatego często warto w stanie uzyskać unikalny indeks dla każdego unikalnego klucza.

Kocham indeksy!

Uwielbiam indeksy tak samo jak pizza i piwo. Kiedy miałem 20 lat, zacząłem naprawdę interesować się C ++ i zacząłem projektować wszelkiego rodzaju struktury danych w pełni zgodne ze standardami (w tym sztuczki związane z ujednoznacznieniem ctor wypełnienia z ctor zakresu w czasie kompilacji). Z perspektywy czasu była to duża strata czasu.

Jeśli obracasz bazę danych wokół centralnego przechowywania elementów i indeksowania ich zamiast przechowywania ich w sposób rozdrobniony i potencjalnie w całym adresowalnym zakresie maszyny, możesz w końcu zbadać świat możliwości algorytmicznych i struktury danych, po prostu projektowanie kontenerów i algorytmów, które obracają się wokół zwykłego starego intlub int32_t. Okazało się, że efekt końcowy jest o wiele bardziej wydajny i łatwy w utrzymaniu tam, gdzie nie przenosiłem elementów z jednej struktury danych do drugiej do drugiej.

Niektóre przykładowe przypadki użycia, w których można po prostu założyć, że każda unikalna wartość Tma unikalny indeks i będzie miała instancje znajdujące się w centralnej tablicy:

Wielowątkowe sortowanie podstawowe, które działa dobrze z liczbami całkowitymi bez znaku dla indeksów . W rzeczywistości mam wielowątkowy sortowanie radix, które zajmuje około 1/10 czasu sortowania stu milionów elementów, podobnie jak sortowanie równoległe Intela, a Intel jest już 4 razy szybszy niż w std::sortprzypadku tak dużych danych wejściowych. Oczywiście Intel jest znacznie bardziej elastyczny, ponieważ jest oparty na porównaniu i może sortować leksykograficznie, więc porównuje jabłka z pomarańczami. Ale tutaj często potrzebuję tylko pomarańczy, tak jakbym mógł wykonać sortowanie radix, aby uzyskać wzorce dostępu do pamięci przyjazne dla pamięci podręcznej lub szybko odfiltrować duplikaty.

Możliwość budowania powiązanych struktur, takich jak połączone listy, drzewa, wykresy, oddzielne tabele mieszania łańcuchów itp. Bez przydziału sterty na węzeł . Możemy po prostu przydzielić węzły zbiorczo, równolegle do elementów i połączyć je razem z indeksami. Same węzły stają się po prostu 32-bitowym indeksem do następnego węzła i są przechowywane w dużej tablicy:

Przyjazny dla przetwarzania równoległego. Często połączone struktury nie są tak przyjazne dla równoległego przetwarzania, ponieważ co najmniej niewygodne jest próbowanie osiągnięcia równoległości w przechodzeniu przez drzewo lub listę połączoną, w przeciwieństwie do, powiedzmy, robienia równoległej pętli for przez tablicę. Dzięki reprezentacji indeksu / tablicy centralnej zawsze możemy przejść do tej tablicy centralnej i przetwarzać wszystko w masywnych równoległych pętlach. Zawsze mamy tę centralną tablicę wszystkich elementów, którą możemy przetwarzać w ten sposób, nawet jeśli chcemy tylko przetworzyć niektóre (w tym momencie można przetwarzać elementy indeksowane przez listę posortowaną według podstawników w celu uzyskania dostępu do pamięci podręcznej za pośrednictwem centralnej tablicy).

Może powiązać dane z każdym elementem w locie w stałym czasie . Podobnie jak w przypadku równoległego szeregu bitów powyżej, możemy łatwo i wyjątkowo tanio powiązać równoległe dane z elementami do, powiedzmy, tymczasowego przetwarzania. Ma to przypadki użycia wykraczające poza dane tymczasowe. Na przykład system siatki może pozwolić użytkownikom na dołączanie do siatki dowolnej liczby map UV. W takim przypadku nie możemy po prostu zakodować na sztywno liczby map UV w każdym wierzchołku i twarzy, stosując podejście AoS. Musimy być w stanie powiązać takie dane w locie, a równoległe tablice są tam przydatne i znacznie tańsze niż jakikolwiek wyrafinowany kontener asocjacyjny, nawet tabele skrótów.

Oczywiście marne są równoległe tablice ze względu na ich podatność na błędy polegające na utrzymywaniu synchronizacji równoległych tablic. Za każdym razem, gdy usuwamy element o indeksie 7 z tablicy „root”, musimy również zrobić to samo dla „dzieci”. Jednak w większości języków dość łatwo jest uogólnić tę koncepcję na kontener ogólnego przeznaczenia, tak więc trudna logika polegająca na synchronizacji równoległych tablic musi istnieć tylko w jednym miejscu w całej bazie kodu, a taki kontener równoległych tablic może użyj rzadkiej implementacji tablicy powyżej, aby uniknąć marnowania dużej ilości pamięci na sąsiadujące ze sobą puste miejsca w tablicy, które zostaną odzyskane po kolejnych wstawieniach.

Więcej opracowań: rzadkie drzewo bitsetów

W porządku, dostałem prośbę o rozwinięcie czegoś, co moim zdaniem było sarkastyczne, ale i tak to zrobię, bo to świetna zabawa! Jeśli ludzie chcą przenieść ten pomysł na zupełnie nowe poziomy, możliwe jest wykonanie ustawionych skrzyżowań bez nawet liniowego zapętlania elementów N + M. Oto moja ostateczna struktura danych, z której korzystam od wieków i zasadniczo modele set<int>:

Powodem, dla którego może wykonywać skrzyżowania zestawu bez sprawdzania każdego elementu na obu listach, jest to, że pojedynczy bit zestawu w katalogu głównym hierarchii może wskazywać, że, powiedzmy, milion zestawu sąsiadujących elementów jest zajęty w zestawie. Sprawdzając tylko jeden bit, możemy wiedzieć, że wskaźniki N w zakresie [first,first+N)znajdują się w zbiorze, gdzie N może być bardzo dużą liczbą.

Właściwie używam tego jako optymalizatora pętli podczas przeszukiwania zajętych indeksów, ponieważ powiedzmy, że w zestawie znajduje się 8 milionów indeksów. W takim przypadku normalnie musielibyśmy uzyskać dostęp do 8 milionów liczb całkowitych w pamięci. Dzięki temu może potencjalnie po prostu sprawdzić kilka bitów i zaproponować zakresy indeksów zajętych indeksów, które można przejrzeć. Co więcej, zakresy indeksów, które wymyśla, są posortowane, co zapewnia bardzo przyjazny dla pamięci podręcznej dostęp sekwencyjny, w przeciwieństwie do, powiedzmy, iteracji przez nieposortowaną tablicę indeksów używanych do uzyskania dostępu do pierwotnych danych elementu. Oczywiście technika ta ma się gorzej w przypadku bardzo rzadkich przypadków, przy czym najgorszym scenariuszem jest to, że każdy indeks jest liczbą parzystą (lub każdą nieparzystą), w którym to przypadku nie ma żadnych sąsiadujących regionów. Ale przynajmniej w moich przypadkach użycia

Sprawdzenie, czy zestaw zawierający n elementów zawiera inny element, zajmuje zwykle stały czas. Sprawdzenie, czy tablica zawierająca n elementów zawiera inny element, zajmuje zwykle O (n) czasu. To źle, ale jeśli chcesz usunąć duplikaty z n elementów, nagle zajmuje to O (n) w czasie zamiast O (n ^ 2); 100 000 przedmiotów rzuci Twój komputer na kolana.

A ty pytasz o więcej powodów? „Czy poza strzelaniem podobał ci się wieczór, pani Lincoln?”