Jaka struktura danych skutecznie przechowuje zakresy liczb całkowitych?

10

Muszę przechowywać kolekcję liczb całkowitych z zakresu od 0 do 65535, aby móc szybko wykonać następujące czynności:

  • Wstaw nową liczbę całkowitą
  • Wstaw zakres ciągłych liczb całkowitych
  • Usuń liczbę całkowitą
  • Usuń wszystkie liczby całkowite poniżej liczby całkowitej
  • Sprawdź, czy występuje liczba całkowita

Moje dane mają tę właściwość, że często zawierają ciągi liczb całkowitych w kolekcji. Na przykład kolekcja może w pewnym momencie być:

{ 121, 122, 123, 124, 3201, 3202, 5897, 8912, 8913, 8914, 18823, 18824, 40891 }

Najprostszym podejściem jest użycie zrównoważonego drzewa binarnego, takiego jak C ++ std :: set, jednak korzystając z tego, nie wykorzystuję faktu, że często mam serie liczb. Być może lepiej byłoby przechowywać kolekcję zakresów? Oznacza to jednak, że zasięg musi zostać podzielony, jeśli liczba całkowita w jego środku zostanie usunięta, lub połączony razem, jeśli zostanie wypełniona przestrzeń między dwoma zakresami.

Czy istnieją jakieś struktury danych, które byłyby odpowiednie dla tego problemu?

WilliamKF
źródło

Odpowiedzi:

9

Sugeruję użycie binarnego drzewa wyszukiwania, powiększonego, aby liście mogły zawierać interwał (ciąg kolejnych liczb całkowitych). Zachowaj niezmiennik, aby interwały nie nakładały się i były w porządku (zgodnie z niezmiennikiem drzewa wyszukiwania). (Można to uznać za szczególny przypadek drzewa interwałów lub drzewa segmentów, w szczególnym przypadku, gdy interwały nie nakładają się).

Ta struktura danych umożliwia obsługę wszystkich operacji w czasie , gdzie jest liczbą interwałów. Ponieważ mamy gwarancję , oczekiwałbym, że będzie to dość wydajne. (W szczególności tak, możesz podzielić interwał na dwie części lub połączyć dwa sąsiednie interwały w jeden interwał w czasie .)O(lgn)nn65535O(lgn)

DW
źródło
5

Po pierwsze, twoje pytanie jest bardzo źle sformułowane, jeśli nie z innego powodu, ponieważ „szybko” niewiele znaczy. Musisz podać dane dotyczące tego, co oznacza „szybki”.

Poza tym, próbując wymyślić projekt problemu, musisz najpierw bardzo dobrze zrozumieć problem i zadać wiele dodatkowych pytań. Odpowiednie pytania w tym przypadku wydają się być (w nieokreślonej kolejności):

  • Czy wszystkie te operacje muszą być równie szybkie, czy też niektóre są ważniejsze od innych?
  • Czy są inne względy?
  • Czy pamięć w ogóle jest problemem?
  • Czy zdolność do wstawiania, usuwania i wyszukiwania z wielu wątków stanowi problem?
  • Czy obciążenie koncentruje się głównie na wstawianiu? Usuwasz? Patrząc w górę

[0,65535]

Aby uzyskać nieco więcej pracy, możesz zaoszczędzić miejsce, jeśli jest to problem, kosztem szybkości, przechowując dane jako bity w liczbach całkowitych 8192. Chociaż koncepcyjnie pojedyncze operacje na liczbach całkowitych byłyby nadal stałym czasem, a operacje na liczbach całkowitych na dystansie byłyby nadal czasem liniowym, byłyby one wolniejsze.

Więc jeśli to naprawdę twój problem, powinieneś użyć tablicy i przejść do innych, ważniejszych rzeczy z kodem.

[0,65535]

Nik Bougalis
źródło
3

U={0,,u-1}O(loglogu)

W zależności od struktury danych może istnieć wiele sprytnych alternatyw dla przechowywania danych.

A.Schulz
źródło