Pytania otagowane jako ds.data-structures

Właściwości i zastosowania struktur danych, takie jak dolne granice przestrzeni lub złożoność czasowa wstawiania i usuwania obiektów.

6
Co nowego w czysto funkcjonalnych strukturach danych od czasu Okasaki?
Od czasu książki Chrisa Okasakiego z 1998 r. „Czysto funkcjonalne struktury danych”, nie widziałem zbyt wielu nowych ekscytujących czysto funkcjonalnych struktur danych; Mogę wymienić tylko kilka: IntMap (również wynaleziony przez Okasaki w 1998 r., Ale nieobecny w tej książce) Drzewa palcowe (i ich uogólnienie na monoidy) Istnieje również kilka interesujących …

30
Algorytmy z książki.
Paul Erdos mówił o „Księdze”, w której Bóg przechowuje najbardziej elegancki dowód każdego twierdzenia matematycznego. To nawet zainspirowało książkę (która, jak sądzę, jest teraz w czwartym wydaniu): Dowody z książki . Gdyby Bóg miał podobną książkę na temat algorytmów, jaki według ciebie algorytm byłby kandydatem (kandydatami)? Jeśli to możliwe, proszę …

9
Potężne algorytmy zbyt skomplikowane do wdrożenia
Jakie są algorytmy legalnej użyteczności, które są po prostu zbyt skomplikowane, aby je zaimplementować? Wyjaśnię: nie szukam algorytmów takich jak obecny asymptotyczny algorytm optymalnego mnożenia macierzy (Coppersmith-Winograd), który jest rozsądny do wdrożenia, ale ma stałą, która czyni go bezużytecznym w praktyce. Szukam algorytmów, które mogłyby mieć praktyczną wartość, ale są …

10
Jeden stos, dwie kolejki
tło Kilka lat temu, kiedy byłem studentem, otrzymaliśmy zadanie domowe z analizy zamortyzowanej. Nie udało mi się rozwiązać jednego z problemów. Poprosiłem o to w teorii porównawczej , ale nie uzyskałem zadowalającego rezultatu. Pamiętam kurs, który TA nalegał na coś, czego nie mógł udowodnić, i powiedział, że zapomniał dowodu i …

13
Dla jakich algorytmów istnieje duża luka między analizą teoretyczną a rzeczywistością?
Istnieją dwa sposoby analizy wydajności algorytmu nałożyć asymptotyczną górną granicę czasu działania, oraz aby go uruchomić i zebrać dane eksperymentalne. Zastanawiam się, czy są znane przypadki, w których istnieje znaczna różnica między (1) a (2). Rozumiem przez to, że albo (a) dane eksperymentalne sugerują silniejszą asymptozę, albo (b) istnieją algorytmy …


4
Czy istnieje funkcja skrótu dla zbioru liczb całkowitych (tj. Wielu), która ma dobre gwarancje teoretyczne?
Ciekawe, czy istnieje sposób przechowywania skrótu zbioru liczb całkowitych, który ma następujące właściwości, najlepiej: Wykorzystuje spację O (1) Można go zaktualizować, aby odzwierciedlał wstawianie lub usuwanie w czasie O (1) Dwie identyczne kolekcje (tj. Kolekcje, które mają te same elementy o tych samych wielokrotnościach) zawsze powinny mieć skrót do tej …


6
Zestaw probabilistyczny bez fałszywych trafień?
Tak więc filtry Bloom są całkiem fajne - są zestawami, które obsługują sprawdzanie członkostwa bez fałszywych negatywów, ale z niewielką szansą na fałszywy pozytyw. Ostatnio jednak chciałem mieć „filtr Blooma”, który gwarantuje coś przeciwnego: żadnych fałszywych alarmów, ale potencjalnie fałszywych negatywów. Moja motywacja jest prosta: biorąc pod uwagę ogromny strumień …


3
Struktura danych oparta na porównaniu do znajdowania pozycji
Czy istnieje struktura danych, która pobiera nieuporządkowaną tablicę elementów, wykonuje wstępne przetwarzanie w i odpowiada na zapytania: czy na liście jest jakiś element , każde zapytanie w najgorszym czasie ?nnnO(n)O(n)O(n)xxxO(logn)O(log⁡n)O(\log n) Naprawdę uważam, że nie ma, dlatego mile widziany jest również dowód, że nie ma.

4
Dlaczego ktoś miałby używać Octree zamiast drzewa KD?
Mam pewne doświadczenie w obliczeniach naukowych i intensywnie korzystałem z drzewek kd do aplikacji BSP (partycjonowanie przestrzeni binarnej). Niedawno zapoznałem się raczej z oktatami, podobną strukturą danych do partycjonowania trójwymiarowych przestrzeni euklidesowych, ale taką, która działa w ustalonych regularnych odstępach czasu, z tego, co zbieram. Trochę badań dotyczących niezależności wydaje …

6
Czy jest stabilna kupa?
Czy istnieje struktura danych kolejki priorytetowej, która obsługuje następujące operacje? Wstaw (x, p) : dodaj nowy rekord x z priorytetem p StableExtractMin () : Zwraca i usuwa rekord z minimalnym priorytetem, zrywając powiązania według kolejności wstawiania . Zatem po Insert (a, 1), Insert (b, 2), Insert (c, 1), Insert (d, …


2
Marzyłem o strukturze danych, czy ona istnieje?
Nie udało mi się znaleźć tej struktury danych, ale nie jestem ekspertem w tej dziedzinie. Struktura implementuje zestaw i jest w zasadzie szeregiem porównywalnych elementów z niezmiennikiem. Niezmiennikiem jest to (zdefiniowane rekurencyjnie): Tablica o długości 1 jest tablicą scalającą. Tablica o długości 2 ^ n (dla n> 0) jest tablicą …

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.