Dlaczego standard C++ wymaga std :: partition w celu spełnienia różnych złożoności dla różnych typów iteratorów?

Question

Standard C++ wymaga, aby std::partition miał różną liczbę aplikacji predykatów między ForwardIterator i BidirectionalIterator. Dla wersji ForwardIterator liczba aplikacji bazowych będzie < = N, gdzie N = std::distance(first, last), ale dla wersji BidirectionalIterator liczba aplikacji źródłowych powinny być < = N/2. Oczywiście, obie wersje mają złożoność czasową O (N).

Moje pytanie brzmi: dlaczego warto zadawać różne wymagania dla różnych typów iteratorów? Takie wymaganie zmusza wiele kompilatorów?

np. MSVC, zaimplementuj funkcję std::partition na dwa sposoby, aby spełnić takie wymagania, co nie wydaje się być bardzo eleganckie.

Kolejne pytanie: Czy istnieje jakiś algorytm, który opiera się na tego współczynnika, tak, że gdy N/2 staje N, asymptotycznej złożoności będzie inaczej? Dla mojego zrozumienia, jeśli weźmiemy pod uwagę Master's Theorem, dla formularza w T(n) = aT(n/b) + f(n), współczynnik w f(n) nie ma znaczenia.

C.f. Równoważny wdrożenie partycji msvc za:

template<class BidirIt, class UnaryPred> 
BidirIt partition(BidirIt first, BidirIt last, UnaryPred pred, std::bidirectional_iterator_tag) 
{ 
    while (true) 
    { 
     while ((first != last) && pred(*first)) 
     { 
      ++first; 
     } 
     if (first == last) 
     { 
      break; 
     } 
     --last; 
     while ((first != last) && !pred(*last)) 
     { 
      --last; 
     } 
     if (first == last) 
     { 
      break; 
     } 
     std::iter_swap(first, last); 
     ++first; 
    } 
    return first; 
} 
template<class ForwardIt, class UnaryPred> 
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPred pred, std::forward_iterator_tag) 
{ 
    first = std::find_if_not(first, last, pred); 
    if (first == last) 
    { 
     return first; 
    } 

    for (ForwardIt src = std::next(first); src != last; ++src) 
    { 
     if (pred(*src)) 
     { 
      std::iter_swap(first, src); 
      ++src; 
     } 
    } 
    return first; 
} 
template<class ForwardIt, class UnaryPred> 
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPred pred) 
{ 
    return partition(first, last, pred, typename std::iterator_traits<ForwardIt>::iterator_category()); 
} 

Answer 1

Predykat pred jest wykonywany dokładnie w obu przypadkach - w każdym przypadku każdy element musi zostać przetestowany jeden raz. Różnica między ForwardIterator i BidirectionalIterator jest w ilości swapów.

BidirectionalIterator robi co najwyżej N/2 swapy, ponieważ przeszukuje zakres od przodu i od tyłu na raz, po osiągnięciu wartości z lewej strony, który nie spełnia predykat i wartość z prawej strony, dokłada spełnij to, zamienia je. Więc w najgorszym przypadku może to zrobić w zamianie N/2.

ForwardIterator nie ma takiej przewagi, aw najgorszym przypadku może wykonać zamianę na każdy element.

Norma wymaga tych dwóch różnych ograniczeń, ponieważ oba są najlepsze, jakie można uzyskać. Programiści mogą więc polegać na tym, że każda standardowa implementacja biblioteki zachowa się w ten sposób.

Answer 2

To prawda, czas złożoność jest wciąż ten sam.

Ważne jest, aby zauważyć, że swapy są rzeczywiście dość drogie. Zwłaszcza w przypadku dużych obiektów. W większości przypadków obejmują one trzy operacje przeniesienia. W takich scenariuszach powinniśmy ograniczyć ilość swapów do minimum. Dzięki zastosowaniu dwukierunkowych iteratorów uzyskujemy znaczną poprawę wydajności, nawet jeśli złożoność czasu jest taka sama.

Należy pamiętać, że w rzeczywistym środowisku może być konieczne szybkie wykonanie prostych czynności. Ilekroć istnieje taka możliwość, należy to zrobić w ten sposób. Podczas pracy ze złożonymi algorytmami (często w przypadku problemów związanych z NP-zupełnymi problemami), które wymagają dużo czasu na obliczenie, może być konieczne wykonanie operacji w czasie o połowę krótszym. Czy wolisz mieć opóźnienie od 0,2 sekundy do 0,1 sekundy? Złożoność czasu jest zbiorem ładnej teorii, ale rzeczywisty świat nie jest tak piękny i każda ułamek sekundy jest ważny.