Najszybszy kontener lub algorytm dla unikalnych identyfikatorów wielokrotnego użytku w C++

Question

Potrzebuję unikatowych identyfikatorów wielokrotnego użytku. Użytkownik może wybrać własne identyfikatory lub może poprosić o darmowy. API jest w zasadzie

class IdManager { 
public: 
    int AllocateId();   // Allocates an id 
    void FreeId(int id);  // Frees an id so it can be used again 
    bool MarkAsUsed(int id); // Let's the user register an id. 
          // returns false if the id was already used. 
    bool IsUsed(int id);  // Returns true if id is used. 
}; 

Załóżmy identyfikatory zdarzyć rozpocząć się 1 i postępu, 2, 3, itd To nie jest wymóg, żeby pomóc zilustrować.

IdManager mgr; 
mgr.MarkAsUsed(3); 
printf ("%d\n", mgr.AllocateId()); 
printf ("%d\n", mgr.AllocateId()); 
printf ("%d\n", mgr.AllocateId()); 

Czy drukować

1 
2 
4 

Bo id 3 zostało już uznane za wykorzystane.

Jaki jest najlepszy kontener/algorytm, aby pamiętać, które identyfikatory są używane I znaleźć wolny identyfikator?

Jeśli chcesz znać konkretny przypadek użycia, glGenTextures OpenGL, w glBindTexture i glDeleteTextures są równoważne AllocateId, MarkAsUsed i FreeId

Answer 1

Mój pomysł polega na użyciu std::set i Boost.interval, dzięki czemu IdManager będzie przechowywać zestaw nie nakładających się interwałów wolnych identyfikatorów. AllocateId() jest bardzo prosty i bardzo szybki i po prostu zwraca lewą granicę pierwszego wolnego przedziału. Pozostałe dwie metody są nieco trudniejsze, ponieważ może być konieczne podzielenie istniejącego odstępu lub połączenie dwóch sąsiednich przedziałów. Jednak są one również dość szybkie.

Więc to jest ilustracją idei wykorzystania odstępach:

IdManager mgr; // Now there is one interval of free IDs: [1..MAX_INT] 
mgr.MarkAsUsed(3);// Now there are two interval of free IDs: [1..2], [4..MAX_INT] 
mgr.AllocateId(); // two intervals:       [2..2], [4..MAX_INT] 
mgr.AllocateId(); // Now there is one interval:    [4..MAX_INT] 
mgr.AllocateId(); // Now there is one interval:    [5..MAX_INT] 

Jest to kod sama:

#include <boost/numeric/interval.hpp> 
#include <limits> 
#include <set> 
#include <iostream> 


class id_interval 
{ 
public: 
    id_interval(int ll, int uu) : value_(ll,uu) {} 
    bool operator < (const id_interval&) const; 
    int left() const { return value_.lower(); } 
    int right() const { return value_.upper(); } 
private: 
    boost::numeric::interval<int> value_; 
}; 

class IdManager { 
public: 
    IdManager(); 
    int AllocateId();   // Allocates an id 
    void FreeId(int id);  // Frees an id so it can be used again 
    bool MarkAsUsed(int id); // Let's the user register an id. 
private: 
    typedef std::set<id_interval> id_intervals_t; 
    id_intervals_t free_; 
}; 

IdManager::IdManager() 
{ 
    free_.insert(id_interval(1, std::numeric_limits<int>::max())); 
} 

int IdManager::AllocateId() 
{ 
    id_interval first = *(free_.begin()); 
    int free_id = first.left(); 
    free_.erase(free_.begin()); 
    if (first.left() + 1 <= first.right()) { 
     free_.insert(id_interval(first.left() + 1 , first.right())); 
    } 
    return free_id; 
} 

bool IdManager::MarkAsUsed(int id) 
{ 
    id_intervals_t::iterator it = free_.find(id_interval(id,id)); 
    if (it == free_.end()) { 
     return false; 
    } else { 
     id_interval free_interval = *(it); 
     free_.erase (it); 
     if (free_interval.left() < id) { 
      free_.insert(id_interval(free_interval.left(), id-1)); 
     } 
     if (id +1 <= free_interval.right()) { 
      free_.insert(id_interval(id+1, free_interval.right())); 
     } 
     return true; 
    } 
} 

void IdManager::FreeId(int id) 
{ 
    id_intervals_t::iterator it = free_.find(id_interval(id,id)); 
    if (it != free_.end() && it->left() <= id && it->right() > id) { 
     return ; 
    } 
    it = free_.upper_bound(id_interval(id,id)); 
    if (it == free_.end()) { 
     return ; 
    } else { 
     id_interval free_interval = *(it); 

     if (id + 1 != free_interval.left()) { 
      free_.insert(id_interval(id, id)); 
     } else { 
      if (it != free_.begin()) { 
       id_intervals_t::iterator it_2 = it; 
       --it_2; 
       if (it_2->right() + 1 == id) { 
        id_interval free_interval_2 = *(it_2); 
        free_.erase(it); 
        free_.erase(it_2); 
        free_.insert(
         id_interval(free_interval_2.left(), 
            free_interval.right())); 
       } else { 
        free_.erase(it); 
        free_.insert(id_interval(id, free_interval.right())); 
       } 
      } else { 
        free_.erase(it); 
        free_.insert(id_interval(id, free_interval.right())); 
      } 
     } 
    } 
} 

bool id_interval::operator < (const id_interval& s) const 
{ 
    return 
     (value_.lower() < s.value_.lower()) && 
     (value_.upper() < s.value_.lower()); 
} 


int main() 
{ 
    IdManager mgr; 

    mgr.MarkAsUsed(3); 
    printf ("%d\n", mgr.AllocateId()); 
    printf ("%d\n", mgr.AllocateId()); 
    printf ("%d\n", mgr.AllocateId()); 

    return 0; 
} 

Answer 2

Ale nie sądzę, trzeba zagwarantować id musi zaczynać od 1. Możesz się upewnić, że dostępny identyfikator musi być większy niż wszystkie przydzielone identyfikatory.

podobnego, jeżeli 3 jest zarejestrowany, potem następny dostępny id może być tylko 4. Nie sądzę, jest to niezbędne do korzystania z 1.

Answer 3

Byłoby dobrze, aby wiedzieć, ile jesteś identyfikatory powinien śledzić. Jeśli jest ich tylko setka, wystarczy prosty linijka set, aby uzyskać nowy identyfikator. Jeśli jest to więcej niż kilka tysięcy, to oczywiście linearne przejście stanie się zabójcą wydajności, szczególnie biorąc pod uwagę nieprzyjemność zestawu w pamięci podręcznej.

Osobiście chciałbym pójść za:

• set, co pomaga śledzenie identyfikatorów łatwo O(log N)
• proponuje nowy identyfikator jako obecnego maksimum + 1 ... O(1)

Jeśli nie przydzielisz (w okresie użytkowania aplikacji) więcej niż max<int>() id, powinno być dobrze, w przeciwnym razie ... użyj większego typu (ustaw niepodpisane, użyj long lub long long), z którego najłatwiej zacząć.

A jeśli to nie wystarczy, zostaw komentarz, a ja będę edytować i szukać bardziej skomplikowanych rozwiązań. Ale im bardziej skomplikowane jest prowadzenie ksiąg, tym dłużej trwa realizacja w praktyce i tym większe są szanse popełnienia błędu.

Answer 4

Zakładam, że chcesz mieć możliwość korzystania ze wszystkich dostępnych wartości dla typu Id i chcesz ponownie użyć uwolnionych identyfikatorów? Zakładam również, że zablokujesz kolekcję, jeśli używasz jej z więcej niż jednego wątku ...

Stworzyłem klasę z zestawem do przechowywania przydzielonych identyfikatorów, listą do przechowywania darmowe identyfikatory i maksymalna przydzielona wartość, aby uniemożliwić mi wstępne ładowanie darmowej listy identyfikatorów przy każdym dostępnym identyfikatorze.

Zaczynasz więc od pustego zestawu przydzielonych identyfikatorów i pustej listy wolnych identyfikatorów oraz maksimum przydzielonego jako 0.Przydzielasz, przejmujesz kierownika wolnej listy, jeśli jest taka, weź max, sprawdź, czy nie jest w twoim zbiorze przydzielonych identyfikatorów, ponieważ może to być, jeśli ktoś ją zarezerwował, jeśli jest, zwiększ max i spróbuj ponownie, jeśli nie, dodaj do zestawu i zwróć go.

Po zwolnieniu identyfikatora po prostu zaznaczasz go w swoim zestawie, a jeśli tak, pchnij go na wolną listę.

Aby zarezerwować identyfikator, wystarczy sprawdzić zestaw, a jeśli nie, dodać go.

To przetwarza id szybko, co może ale nie musi być dla ciebie dobre, to znaczy allocate(), free(), allocate() daje ten sam identyfikator, jeśli żadne inne wątki nie mają dostępu do kolekcji.

Answer 5

Skompresowany wektor. Ale nie sądzę, aby jakikolwiek pojemnik zrobiłby zauważalną różnicę.

Answer 6

Normalnie powiedziałbym, że trzymam się prostej implementacji, dopóki nie zorientujesz się, które metody są używane najbardziej. Przedwczesne strojenie może okazać się błędne. Użyj prostej implementacji i zapisz jej użycie, a następnie zoptymalizuj z najczęściej używanych funkcji. Nie ma sensu optymalizacja pod kątem szybkiego usuwania lub szybkiego przydzielania, jeśli potrzebujesz tylko kilkuset identyfikatorów i wystarczy prosty wektor.

Answer 7

podobne do skwllsp, będę śledzić zakresach, które nie mają zostały przydzielone, ale moje metody są nieco inne. Podstawowym kontenerem byłaby mapa, której kluczem jest górna granica zakresu, a wartość to dolna granica.

IdManager::IdManager() 
{ 
    m_map.insert(std::make_pair(std::numeric_limits<int>::max(), 1); 
} 

int IdManager::AllocateId() 
{ 
    assert(!m_map.empty()); 
    MyMap::iterator p = m_map.begin(); 
    int id = p->second; 
    ++p->second; 
    if (p->second > p->first) 
     m_map.erase(p); 
    return id; 
} 

void IdManager::FreeId(int id) 
{ 
    // I'll fill this in later 
} 

bool IdManager::MarkAsUsed(int id) 
{ 
    MyMap::iterator p = m_map.lower_bound(id); 

    // return false if the ID is already allocated 
    if (p == m_map.end() || id < p->second || id > p->first))) 
     return false; 

    // first thunderstorm of the season, I'll leave this for now before the power glitches 
} 

bool IdManager::IsUsed(int id) 
{ 
    MyMap::iterator p = m_map.lower_bound(id); 
    return (p != m_map.end() && id >= p->second && id <= p->first); 
} 

Answer 8

Przyjaciel zauważył, że w tym przypadku hash może być lepszy. Większość programów OpenGL nie wykorzystuje więcej niż kilka tysięcy identyfikatorów, więc hash z powiedzeniem 4096 slotów jest prawie gwarantowany, że ma tylko 1 lub 2 wpisy na gniazdo. Istnieje pewien zdegenerowany przypadek, w którym wiele identyfikatorów może trafić w jeden slot, ale jest to mało prawdopodobne. Użycie skrótu spowodowałoby, że AllocateID byłby znacznie wolniejszy, ale można do tego użyć zestawu. Alokacja wolniej jest mniej ważna niż InUse, która jest szybka dla mojego przypadku użycia.