Przeszukałem i nie mogłem znaleźć specyfikacji czasu wykonania dla zestawu bitset :: count(). Czy ktokolwiek wie, co to jest (O (n) lub lepiej) i gdzie go znaleźć?Jaka jest wydajność metody STL bitset :: count()?
EDYTOWANIE Wg STL odwołuję się tylko do standardowej biblioteki szablonów.
Czytam ten plik (C: \ cygwin \ lib \ gcc \ i686-pc-cygwin \ 3.4.4 \ include \ C++ \ bitset) na moim komputerze.
Patrz te
/// Returns the number of bits which are set.
size_t
count() const { return this->_M_do_count(); }
size_t
_M_do_count() const
{
size_t __result = 0;
for (size_t __i = 0; __i < _Nw; __i++)
__result += __builtin_popcountl(_M_w[__i]);
return __result;
}
okazji, to jest, gdy _Nw jest określona:
template<size_t _Nw>
struct _Base_bitset
Zatem to O (n) w gcc realizacji. Podsumowując, specyfikacja nie wymaga tego więcej niż O (n). I nikt przy zdrowych zmysłach nie wdroży go w sposób gorszy. Możemy wtedy bezpiecznie założyć, że jest w najgorszym O (n). Być może lepiej, ale nigdy nie możesz na to liczyć.
To jednak nie jest specyfikacja! : P –
@ tomalak-geretkal W implementacji gcc jest to O (n). Podsumowując, specyfikacja nie wymaga tego więcej niż O (n). I nikt nie byłby tak głupi, by wprowadzić go w sposób gorszy. Możemy wtedy bezpiecznie założyć, że zawsze jest to co najmniej O (n). Być może lepiej, ale nigdy nie możesz na to liczyć. – Haozhun
@Gene: Chociaż w tym przypadku się z tym zgadzam, nie jest to odpowiedź na oryginalne pytanie dotyczące specyfikacji wydajności. Jest to jednak dobra dedukcja. –
„implementacja referencyjna SGI działa w czasie liniowym względem liczby bajtów potrzebnych do przechowywania bitów. Czyni to poprzez stworzenie statyczną tablicę 256 liczb całkowitych. Wartość przechowywane w indeksie ith w tablicy jest liczbą bitów ustawionych w wartości i. "
To może być dokładne, ale tylko ostrzeżenie tutaj, że cplusplus.com jest dobrze znany z błądzenia z błędami. –
Co więcej, byłby to opis pewnej implementacji. –
@DavidThornley: Rzeczywiście, cplusplus.com jest bardzo zagmatwany (śmiem powiedzieć, zdezorientowany?) Ogólnie o bibliotece. Używa terminu "STL" wyraźnie insynuując, że to naprawdę oznacza C++ Standard Library, ale wtedy ludzie na forach mówią o faktycznym STL. –
Nie jestem pewien, masz zamiar znaleźć specyfikację, że skoro STL zazwyczaj nie wymagają pewnego poziomu wydajności. Widziałem wskazówki, że jest "szybki", około 1 cykl na bit w rozmiarze zestawu. Możesz oczywiście przeczytać kod konkretnej implementacji, aby dowiedzieć się, czego się spodziewać.
STL zwykle wymaga pewnych poziomów asymptotycznej wydajności (big-O). –
Nie mogę być pewien, co naprawdę masz na myśli przez "STL" tutaj, z powodu dominującego nadużywania tego terminu w społeczności C++.
C++ Standard (2003) nie ma mandatu do wykonywania std::bitset::count() (lub w rzeczywistości, wszelkie członkowie std::bitset miarę widzę).
Nie mogę znaleźć żadnego odniesienia sugerującego mandat do wykonania STL na bitset::count() albo.
Myślę, że każde rozsądne wdrożenie zapewni to w stałym (lub w najgorszym liniowym) czasie. Jest to jednak po prostu uczucie. Sprawdź swoją, aby dowiedzieć się, co faktycznie otrzymasz.
Czy możesz podzielić się tym, co inne rzeczy robi STL w kontekście C++? – yasouser
Taki sam komentarz, jaki ci podałem [tutaj] (http://stackoverflow.com/questions/2297164/stl-deque-accessing-by-index-is-o1/4694218#4694218). Jest czas na pedanterię, to nie jest to. Skomentuj pytanie, jeśli chcesz wyjaśnić użycie "STL" przez OP, ale nie rób tego częścią twojej odpowiedzi i udawaj, że jesteś niezdolny do zrozumienia, co miał na myśli, jest arogancki i pretensjonalny. * Wyjaśnij * rzeczy OP, nie mów "Nie mogę tego dostać, nie jest to ściśle określone!" – GManNickG
@ Gman Pomyślałbym, że jego pytanie jest niejasne, a następnie udzielenie odpowiedzi na ZARÓWNO dwóch rzeczy, o które mógł zadać, wystarczy. Nie rozumiem, jak deklarowanie, że czegoś nie mogę, jest "aroganckie"; przeczytaj słownik. I nie jest tak, że moja cała odpowiedź brzmiała: "Nie wiem, co masz na myśli, spróbuj ponownie". –
To, o czym Tomalak wspomniał (ale nie * wyjaśniło *, ponieważ jest najwyraźniej niepewny i wymaga potwierdzenia swojej wiedzy o innych), jest to, że STL (Standard Template Library) jest terminem niejednoznacznym. Niektórzy z nas w społeczności C++ rozwinęli to w [info-wiki dla tagu] (http://stackoverflow.com/tags/stl/info), co powinno wyjaśnić komentarz źródłowy Tomalaka. Mówiąc krótko, powinieneś po prostu powiedzieć "standardowa biblioteka" lub "stdlib", ale będziemy wiedzieć, co masz na myśli mówiąc STL. – GManNickG
@GMan: Nie potrzeba osobistych ataków. Nie są tu mile widziane w StackOverflow. Dostosuj swój ton w przyszłości. –