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:
- Te dwa agregaty zawierają wskaźniki dla elementów.
- 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
