Czy ktoś wie o strukturze danych, która skutecznie obsługuje dwie operacje?Struktura danych do wybierania elementów losowych?
- Wprowadź wartość do struktury danych.
- Usunąć i przywrócić pozycję ze struktury danych z równomiernie losowym prawdopodobieństwem.
Jest to coś w rodzaju kanonicznej "torby marmurów", która zawsze pojawia się w początkowych klasach prawdopodobieństwa. Możesz umieścić dowolne kulki w torbie, a następnie skutecznie usunąć kulki losowo.
Najlepsze rozwiązanie, które mam, jest następujące: użyj samokonującego drzewa wyszukiwania binarnego (AVL, AA, czerwony/czarny itp.) Do przechowywania elementów. Daje to czas wstawienia O (lg n). Aby usunąć losowy element, wybierz losowy indeks i, a następnie zlokalizuj i usuń element i-tego z drzewa. Jeśli odpowiednio rozbudowałeś strukturę, można to zrobić również w czasie O (lg n).
To środowisko z pewnością nie jest złe, ale jestem ciekawy, czy da się lepiej - być może O (1) do wstawiania i O (lg n) do usuwania kolczyków? A może coś, co działa w oczekiwane O (1) wstawić i usunąć za pomocą funkcji skrótu? A może silniejszy amortyzacji?
Czy ktoś ma jakieś pomysły, jak zrobić to szybciej asymptotycznie?
Po prostu z ciekawości: czy ktoś wie, czy ta struktura danych ma nazwę? Jest to oczywiście rodzaj 'Bag' i/lub' MultiSet'. "RandomBag", może? W rzeczywistości, jakie są takie struktury danych (tj. Struktury danych, w których 'pop' zwraca i usuwa element losowy) o nazwie * w ogóle *? –
Słyszałem tu terminy Bag i RandomBag, ale myślę, że RandomBag jest prawdopodobnie właściwym terminem; Torba jest zwykle synonimem multiset. – templatetypedef