std :: wektor szybciej niż std :: unordered_set?

Question

W moim niestandardowym silniku fizycznym największym wąskim gardłem jest metoda, która pobiera wszystkie obiekty z partycjonowania przestrzennego (siatka 2D) i zwraca kolekcję zawierającą tylko unikalne wskaźniki do treści.

template<typename T, typename V> bool contains(const T& mContainer, const V& mValue) 
{ 
    return std::find(std::begin(mContainer), 
        std::end(mContainer), mValue) != std::end(mContainer); 
} 

const vector<Body*>& GridInfo::getBodiesToCheck() 
{ 
    bodiesToCheck.clear(); 
    for(auto& query : queries) 
     for(auto& body : *query) 
      if(!contains(bodiesToCheck, body)) bodiesToCheck.push_back(body); 
    return bodiesToCheck; 
} 

Korzystanie z profilera pokazuje, że wąskie gardło występuje w metodzie "zawiera".

Oczywiście, rozwiązanie "idealne" byłoby tutaj: std::unordered_set. Jest to jednak znacznie wolniejsze niż obecne rozwiązanie. Próbowałem też google::dense_hash_set, który jest szybszy niż std::unordered_set, ale nadal wolniejszy niż obecne rozwiązanie.

const unordered_set<Body*>& GridInfo::getBodiesToCheck() 
{ 
    bodiesToCheck.clear(); 
    for(auto& query : queries) 
     for(auto& body : *query) 
      /*if(!contains(bodiesToCheck, body))*/ bodiesToCheck.insert(body); 
    return bodiesToCheck; 
} 

Dlaczego są "poprawne" kontenery wolniej niż std::vector?

Czy mogę w jakiś sposób przyspieszyć tę metodę?

Answer 1

Istnieją dwie możliwości mogę myśleć:

1. masz dość małą liczbę elementów danych, że przeszukiwanie liniowe jest szybsze niż odnośnika hash-plus porównania.
2. Używa się tej samej funkcji contains, aby znaleźć element w unordered_set, zamiast korzystać z funkcji elementu find.

Answer 2

Oto, co można znaleźć w dokumentacji std

„unordered_set pojemniki są szybsze niż zestaw pojemników dostęp do poszczególnych elementów przez ich klucza, choć są zazwyczaj mniej wydajne w zakresie iteracji przez podzbiór ich elementy."

Dobrze ponieważ metoda find końcu pętli znacznej liczby elementów ów prawdopodobnie powód ...

Może jeśli użyłeś funkcji Costum skrótu należy go poprawić, aby go szybciej ... Jedyne co mogę wymyślić ...

Answer 3

Jeśli liczba duplikatów nie jest tak wysoka w porównaniu do innych, jedną z opcji może być po prostu wepchnięcie wszystkich ciał do wektora i usunięcie później duplikatów. Będzie to jednak wymagać std::sort, a następnie erase(std::unique, end).

Ale może warto spróbować, biorąc pod uwagę, że Twój wektor zdaje się przeceniać std::unordered_set tak, mimo że nie ma tej samej lokacji pamięci i trywialnego dostępu, jak std::vector.

Answer 4

Nie jestem pewien, czy rozumiem problem poprawnie, ale wydaje się, że wyszukiwanie będzie wolniejsze na std::vector/std::find, ale iteracja może być szybsza niż z std::unordered_set. Jeśli tak jest i nie jesteś ograniczony przez ograniczenia pamięci, możesz mieszać oba podejścia:

Utrzymuj elementy razem z std::unordered_set i std::vector. Poszukaj wewnątrz elementu std::unordered_set, aby określić, czy element już istnieje, a jeśli nie, dodaj go do obu kontenerów. Na końcu iteruj po numerze std::vector.

Należy zauważyć, że można podać wskazówki dla obu kontenerów dotyczące "oczekiwanej" liczby elementów, które będą zawierać, a to zmniejszy liczbę przydziałów pamięci/ponownego łączenia.