2017-11-19 27 views
7

std::set to posortowane drzewo. Udostępnia metody begin i end, więc mogę uzyskać minimum i maksimum oraz lower_bound i upper_bound dla wyszukiwania binarnego. Ale co jeśli chcę, aby iterator wskazywał środkowy element (lub jeden z nich, jeśli jest tam nawet liczba elementów)?Wydajny sposób, aby uzyskać środkową (medianę) std :: set?

Czy jest to skuteczny sposób (O(log(size)), nie O(size)), aby to zrobić?

{1} => 1 
{1,2} => 1 or 2 
{1,2,3} => 2 
{1,2,3,4} => 2 or 3 (but in the same direction from middle as for {1,2}) 
{1,312,10000,14000,152333} => 10000 

PS: Same question in Russian.

+0

Sortowanie binarnym drzewo może być i zwykle jest szczegółowością implementacji std :: set, ale nie jest to wymagane. Jeśli potrzebujesz posortowanej tablicy lub drzewa binarnego, lepiej użyć tego, czego potrzebujesz. –

+0

@ ÖöTiib, potrzebuję dynamicznie wstawiać elementy i dostać środek zestawu. Posortowana tablica/wektor spowoduje wstawienie jako 'O (n)', ale chciałbym, aby zarówno wstawianie, jak i zapytanie działały 'O (lb (n))'. Wiem, że drzewo Decart z niejawnym kluczem pozwala to zrobić, ale nie chcę go implementować i miałem nadzieję, że 'std :: set' jest wystarczająco dobry, aby to osiągnąć. – Qwertiy

+0

@ Kwota w większości przypadków wstawianie do wektora będzie bardzo szybkie ze względu na lokalizację pamięci podręcznej. 'std :: set', a także listy połączone, używają wskaźników do elementów potomnych rozproszonych wszędzie, więc w wielu przypadkach może być wolniejsze. Przeczytaj [Dlaczego nigdy nie powinieneś KIEDYKOLWIEK używać kodu linków w swoim kodzie ponownie] (https://kjellkod.wordpress.com/2012/02/25/why-you-should-never-ever-ever-use- linked-list-in-your-code-again /), [Bjarne Stroustrup: Dlaczego powinieneś unikać Linked Lists] (https://youtu.be/YQs6IC-vgmo), [Are lists evil?] (https: // isocpp.org/blog/2014/06/stroustrup-lists) –

Odpowiedz

9

W zależności od tego, jak często wstawić/usunąć elementy kontra spojrzeć w górę środkowy/mediana, możliwie bardziej efektywne rozwiązanie niż oczywistym rozwiązaniem jest utrzymać trwałe iterator do środkowy element i aktualizuj go za każdym razem, gdy wstawiasz/usuniesz elementy z zestawu. Istnieje kilka skrajnych przypadków, które będą wymagały obsługi (nieparzysta, a nawet liczba elementów, usunięcie środkowego elementu, pustego zestawu itp.), Ale podstawową ideą byłoby, aby wstawić element mniejszy niż bieżący środkowy element , twój środkowy iterator może wymagać zmniejszenia, a jeśli wstawisz większy, musisz zwiększyć. W przypadku przeprowadzek jest na odwrót.

W czasie wyszukiwania jest to oczywiście O (1), ale ma również zasadniczo koszt O (1) przy każdym wstawieniu/usunięciu, tj. O (N) po N wstawieniach, które muszą zostać zamortyzowane na wystarczająca liczba wyszukiwań, aby była bardziej wydajna niż brutalne wymuszanie.

5

To będzie O (rozmiaru), aby uzyskać środek poszukiwania binarnego drzewa. Można go pobrać z std::advance() następująco:

std::set<int>::iterator it = s.begin(); 
std::advance(it, s.size()/2); 
+0

Fajnie, ale chciałbym logarytmu zamiast liniowego ... – Qwertiy

+0

Myślę, że Martin oznacza O (wysokość), gdzie wysokość * zbalansowanego * drzewa binarnego jest logarytmiczna w rozmiarze drzewa. – chepner

+1

@chepner, nope, 'std :: advance' po prostu wywołuje' ++ 'odpowiednią liczbę razy w tym przypadku. – Qwertiy

0

Jeśli dane jest statyczna, te, które mogłyby go precalcate i nie wstawić nowe elementy - to prostsze w użyciu wektora, sortować, a mediana dostęp tylko przez indeks w czasie O (1)

vector<int> data; 
// fill data 
std::sort(data.begin(), data.end()); 
auto median = data[data.size()/2]; 
Powiązane problemy