Pytania otagowane jako data-structures

Pytania dotyczące sposobów przechowywania danych, aby mogły być korzystnie wykorzystywane przez algorytmy.

6
Generowanie kombinacji z zestawu par bez powtarzania elementów
Mam zestaw par. Każda para ma taką postać (x, y), że x, y należą do liczb całkowitych z zakresu [0,n). Jeśli więc n wynosi 4, to mam następujące pary: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) Mam już pary. Teraz muszę zbudować kombinację za pomocą n/2par, tak aby żadna liczba całkowita …
1
Dwie definicje zrównoważonych drzew binarnych
Widziałem dwie definicje zrównoważonych drzew binarnych, które wyglądają inaczej dla mnie. Drzewo binarne jest zrównoważone, jeśli dla każdego węzła utrzymuje, że liczba wewnętrznych węzłów w lewym poddrzewie i liczba wewnętrznych węzłów w prawym poddrzewie różnią się co najwyżej o 1. Drzewo binarne jest zrównoważone, jeśli dla dowolnych dwóch liści różnica …
2
Struktura danych z wyszukiwaniem, wstawianie i usuwanie w zamortyzowanym czasie
Czy istnieje struktura danych umożliwiająca utrzymanie uporządkowanej listy, która obsługuje następujące operacje w zamortyzowanym czasie ?O(1)O(1)O(1) GetElement (k) : zwraca ty element listy.kkk InsertAfter (x, y) : Wstaw nowy element y do listy natychmiast po x. Usuń (x) : Usuń x z listy. W przypadku dwóch ostatnich operacji można założyć, …
5
Czy jest filtr przeciw Bloomowi?
Filtr Bloom pozwala efektywnie śledzić, czy różne wartości zostały już napotkał podczas przetwarzania. Gdy jest wiele elementów danych, filtr Bloom może spowodować znaczne oszczędności pamięci w tabeli skrótów. Główną cechą filtra Bloom, który dzieli z tabelą skrótów, jest to, że zawsze mówi „nie nowy”, jeśli element nie jest nowy, ale …
2
Wydajna struktura danych mapy obsługująca przybliżone wyszukiwanie
Szukam struktury danych, która obsługuje efektywne przybliżone wyszukiwanie kluczy (np. Odległość Levenshteina dla ciągów znaków), zwracając możliwie najbliższe dopasowanie dla klucza wejściowego. Najlepszą strukturą danych, jaką do tej pory znalazłem, są drzewa Burkhard-Keller , ale zastanawiałem się, czy istnieją inne / lepsze struktury danych do tego celu. Edycja: Więcej szczegółów …
1
Dlaczego algorytm rotacji drzewa splay uwzględnia zarówno węzeł nadrzędny, jak i dziadek?
Nie do końca rozumiem, dlaczego rotacja w strukturze danych drzewa splay uwzględnia nie tylko element nadrzędny węzła oceniającego, ale także dziadka (operacja zygzak i zig-zig). Dlaczego następujące elementy nie działają: Gdy wstawiamy na przykład nowy węzeł do drzewa, sprawdzamy, czy wstawiamy do lewego lub prawego poddrzewa. Jeśli wstawimy w lewo, …
3
Pobieranie najkrótszej ścieżki dynamicznego wykresu
Obecnie badam najkrótsze ścieżki na ukierunkowanych wykresach. Istnieje wiele wydajnych algorytmów do znajdowania najkrótszej ścieżki w sieci, takich jak dijkstra lub bellman-ford. Ale co, jeśli wykres jest dynamiczny? Mówiąc dynamiczny, mam na myśli to, że możemy wstawiać lub usuwać wierzchołki podczas wykonywania programu. Próbuję znaleźć skuteczny algorytm do aktualizowania najkrótszych …
1
Czy istnieje ekwiwalent drzew van Emde Boasa dla lin?
Ktoś, kogo znam, planuje wdrożyć edytor tekstu w najbliższej przyszłości, co skłoniło mnie do zastanowienia się, jakie struktury danych są szybkie dla edytora tekstu. Najczęściej stosowanymi konstrukcjami są najwyraźniej liny lub bufory szczelinowe . Drzewa Van Emde Boas są prawie najszybszymi kolejkami priorytetowymi, jeśli nie przeszkadza ci górna granica liczby …
1
Drzewa AVL nie są zrównoważone pod względem masy?
W poprzednim pytaniu była definicja drzew zrównoważonych pod względem masy i pytanie dotyczące drzew czerwono-czarnych. To pytanie dotyczy tego samego pytania, ale dotyczy drzew AVL . Pytanie brzmi, biorąc pod uwagę definicję drzew zrównoważonych jak w drugim pytaniu,μμ\mu Czy jest jakieś takie, że wszystkie wystarczająco duże drzewa AVL są zrównoważone …
2
Jaka kombinacja struktur danych skutecznie przechowuje dyskretne sieci bayesowskie?
Rozumiem teorię leżącą u podstaw sieci bayesowskich i zastanawiam się, co trzeba zbudować w praktyce. Powiedzmy na przykład, że mam sieć bayesowską (ukierunkowaną) 100 dyskretnych zmiennych losowych; każda zmienna może przyjąć jedną z maksymalnie 10 wartości. Czy przechowuję wszystkie węzły w DAG i dla każdego węzła przechowuję tabelę prawdopodobieństwa warunkowego …
8
Czy każdy typ danych po prostu sprowadza się do węzłów ze wskaźnikami?
Tablica lub wektor to tylko sekwencja wartości. Z pewnością można je zaimplementować za pomocą połączonej listy. To tylko kilka węzłów ze wskaźnikami do następnego węzła. Stosy i kolejki to dwa abstrakcyjne typy danych powszechnie nauczane na kursach CS wprowadzających. Gdzieś w klasie uczniowie często muszą implementować stosy i kolejki, używając …
4
Struktura danych dla skrzyżowania zestawu?
Czy jest jakaś struktura danych, która utrzymuje kolekcję zbioru (zbioru skończonego) obsługującą następujące operacje? Czy doceniony zostanie jakikolwiek podliniowy czas pracy? Zainicjuj pusty zestaw. Dodaj element do zestawu. Biorąc pod uwagę dwa zestawy, zgłoś, czy się przecinają.
1
Bezblokowe, stałe struktury drzew współbieżnych w czasie aktualizacji?
Ostatnio czytałem trochę literatury i znalazłem dość interesujące struktury danych. Badałem różne metody skrócenia czasów aktualizacji do najgorszego przypadku [1-7].O(1)O(1)\mathcal{O}(1) Ostatnio zacząłem szukać struktur danych bez blokowania, aby wspierać efektywny równoczesny dostęp. Czy przy wdrażaniu struktur danych bez blokowania zastosowano jedną z tych najgorszych technik aktualizacji czasu ?O(1)O(1)\mathcal{O}(1) Pytam, ponieważ; …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.