Dlaczego std :: list :: reverse ma złożoność O (n)?

192

Dlaczego funkcja odwrotna dla std::listklasy w standardowej bibliotece C ++ ma liniowe środowisko wykonawcze? Sądzę, że dla podwójnie powiązanych list funkcją odwrotną powinna być O (1).

Odwrócenie podwójnie połączonej listy powinno po prostu obejmować zmianę wskaźników głowy i ogona.

Ciekawy
źródło
18
Nie rozumiem, dlaczego ludzie odrzucają to pytanie. Pytanie jest całkowicie rozsądne. Odwrócenie podwójnie połączonej listy powinno zająć czas O (1).
Ciekawy
46
niestety niektórzy mylą pojęcia „pytanie jest dobre” z „pytanie ma dobry pomysł”. Uwielbiam takie pytania, w których zasadniczo „moje rozumienie wydaje się inne niż powszechnie akceptowana praktyka, proszę pomóż rozwiązać ten konflikt”, ponieważ poszerzenie twojego sposobu myślenia pomaga rozwiązać znacznie więcej problemów na późniejszym etapie! Wydaje się, że inni przyjmują podejście „to marnotrawstwo przetwarzania w 99,9999% przypadków, nawet o tym nie myśl”. Jeśli to jakaś pociecha, zostałem przegłosowany o wiele, wiele mniej!
corsiKa
4
Tak, to pytanie uzyskało nadmierną liczbę głosów negatywnych za jego jakość. Prawdopodobnie jest to ten sam, kto głosował za odpowiedzią Blindy. Mówiąc uczciwie, „odwrócenie podwójnie połączonej listy powinno po prostu obejmować zmianę wskaźników głowy i ogona” na ogół nie jest prawdą w przypadku standardowej listy połączonej, co oznacza, że ​​wszyscy uczą się w liceum lub w wielu implementacjach, z których korzystają ludzie. Wiele razy w reakcji SO na jelita na pytanie lub odpowiedź kieruje decyzją pozytywną / negatywną. Gdybyście byli bardziej klarowni w tym zdaniu lub go pominęli, myślę, że mielibyście mniej głosów negatywnych.
Chris Beck
3
Albo pozwólcie, że przedstawię wam ciężar dowodu: @Curious : Podniosłem tutaj podwójnie linkowaną implementację listy: ideone.com/c1HebO . Czy możesz wskazać, jak można oczekiwać, że Reversefunkcja zostanie zaimplementowana w O (1)?
CompuChip
2
@CompuChip: W rzeczywistości, w zależności od implementacji, może nie. Nie potrzebujesz dodatkowej wartości logicznej, aby wiedzieć, którego wskaźnika użyć: po prostu użyj tego, który nie wskazuje na ciebie ... który może być automatyczny z listą połączoną z XOR'em. Tak więc, to zależy od tego, jak lista jest wdrażana, a instrukcja PO może zostać wyjaśniona.
Matthieu M.,

Odpowiedzi:

187

Hipotetycznie reversemógł to być O (1) . Tam (ponownie hipotetycznie) mógł istnieć element listy boolowskiej wskazujący, czy kierunek połączonej listy jest obecnie taki sam, czy przeciwny, niż pierwotny kierunek, w którym lista została utworzona.

Niestety zmniejszyłoby to wydajność praktycznie każdej innej operacji (choć bez zmiany asymptotycznego środowiska wykonawczego). W każdej operacji należy skonsultować się z wartością logiczną, aby zastanowić się, czy zastosować wskaźnik „następny”, czy „poprzedni” linku.

Ponieważ przypuszczalnie uznano to za stosunkowo rzadką operację, standard (który nie dyktuje implementacji, tylko złożoność) określa, że ​​złożoność może być liniowa. Pozwala to „następnym” wskaźnikom zawsze jednoznacznie oznaczać ten sam kierunek, przyspieszając operacje w typowych przypadkach.

Ami Tavory
źródło
29
@MooseBoys: Nie zgadzam się z twoją analogią. Różnica polega na tym, że w przypadku listy, realizacja może dostarczyć reverseze O(1)złożoności bez wpływu na big-O jakiejkolwiek innej operacji , za pomocą tego logiczną flagi podstęp. Ale w praktyce dodatkowy oddział w każdej operacji jest kosztowny, nawet jeśli technicznie jest to O (1). Natomiast nie można utworzyć struktury listy, w której sortjest O (1), a wszystkie pozostałe operacje są takie same. Chodzi o to, że najwyraźniej możesz uzyskać zwrot O(1)za darmo, jeśli zależy ci tylko na dużym O, więc dlaczego tego nie zrobili.
Chris Beck
9
Jeśli użyjesz listy połączonej z XOR, cofanie stałoby się stałym czasem. Iterator byłby jednak większy, a zwiększanie / zmniejszanie byłoby nieco droższe obliczeniowo. Może to zostać przyćmione przez nieunikniony dostęp do pamięci dla każdego rodzaju listy połączonej.
Deduplicator
3
@IlyaPopov: Czy każdy węzeł naprawdę tego potrzebuje? Użytkownik nigdy nie zadaje żadnych pytań do samego węzła listy, tylko do głównej treści listy. Dostęp do wartości logicznej jest więc łatwy dla każdej metody wywoływanej przez użytkownika. Można wprowadzić regułę, że iteratory są unieważniane, jeśli lista jest odwrócona, i / lub przechowywać na przykład kopię wartości logicznej w iteratorze. Myślę więc, że niekoniecznie wpłynie to na duże O. Przyznaję, że nie przeglądałem specyfikacji wiersz po wierszu. :)
Chris Beck
4
@Kevin: Hm, co? Tak czy inaczej nie możesz bezpośrednio xor lub dwóch wskaźników, musisz najpierw przekonwertować je na liczby całkowite (oczywiście typu std::uintptr_t. Potem możesz je xor.
Deduplicator
3
@Kevin, na pewno możesz stworzyć listę połączoną z XOR w C ++, jest to praktycznie język potomny dla tego typu rzeczy. Nic nie mówi, że musisz użyć std::uintptr_t, możesz rzutować na chartablicę, a następnie XOR komponentów. Byłby wolniejszy, ale w 100% przenośny. Prawdopodobnie możesz dokonać wyboru między tymi dwiema implementacjami i użyć drugiej jako rezerwowej, jeśli jej uintptr_tbrakuje. Niektóre, jeśli jest to opisane w tej odpowiedzi: stackoverflow.com/questions/14243971/…
Chris Beck
61

Może to być O (1), jeśli lista przechowuje flagę, która umożliwia zamianę znaczenia wskaźników „ prev” i „ next” każdego węzła. Jeśli odwrócenie listy byłoby częstą operacją, takie dodanie może być w rzeczywistości przydatne i nie znam żadnego powodu, dla którego wdrożenie byłoby zabronione przez obecny standard. Posiadanie takiej flagi spowodowałoby jednak, że zwykłe przejście na listę byłoby droższe (choćby o stały czynnik), ponieważ zamiast

current = current->next;

w operator++iteratorze listy, dostaniesz

if (reversed)
  current = current->prev;
else
  current = current->next;

co nie jest łatwe do dodania. Biorąc pod uwagę, że listy są zwykle przeszukiwane znacznie częściej niż są odwrócone, normalne byłoby wymuszanie tej techniki. Dlatego operacja odwrotna może mieć złożoność liniową. Należy jednak pamiętać, że tO (1) ⇒ tO ( n ), więc, jak wspomniano wcześniej, technicznie możliwe byłoby wdrożenie „optymalizacji”.

Jeśli pochodzisz z języka Java lub podobnego, możesz zastanawiać się, dlaczego iterator musi za każdym razem sprawdzać flagę. Czy nie moglibyśmy zamiast tego mieć dwa różne typy iteratorów, oba wywodzące się ze wspólnego typu podstawowego, i mieć std::list::begini std::list::rbeginzwracać polimorficznie odpowiedni iterator? Chociaż jest to możliwe, pogorszyłoby to wszystko, ponieważ przyspieszenie iteratora byłoby teraz wywołaniem funkcji pośredniej (trudnej do wstawienia). W Javie i tak płacisz tę cenę rutynowo, ale z drugiej strony jest to jeden z powodów, dla których wiele osób korzysta z C ++, gdy wydajność jest krytyczna.

Jak zauważył Benjamin Lindley w komentarzach, ponieważ reversenie wolno unieważniać iteratorów, jedynym podejściem dozwolonym przez standard wydaje się być przechowywanie wskaźnika z powrotem do listy wewnątrz iteratora, co powoduje podwójnie pośredni dostęp do pamięci.

5gon12eder
źródło
7
@ galinette: std::list::reversenie unieważnia iteratorów.
Benjamin Lindley,
1
@ galinette Przepraszam, źle odczytałem twój wcześniejszy komentarz jako „flag na iterator ”, a nie „flag na węzeł ”, jak go napisałeś. Oczywiście flaga na każdy węzeł przyniosłaby efekt przeciwny do zamierzonego, ponieważ musielibyście ponownie wykonać liniowe przejście, aby je wszystkie przerzucić.
5gon12eder
2
@ 5gon12eder: Możesz wyeliminować rozgałęzienie przy bardzo utraconych kosztach: przechowuj wskaźniki nexti prevwskaźniki w tablicy i przechowuj kierunek jako 0lub 1. Aby wykonać iterację do przodu, należy wykonać czynności pointers[direction]iteracyjne w odwrotnej kolejności pointers[1-direction](lub odwrotnie). To wciąż dodaje odrobinę narzutu, ale prawdopodobnie mniej niż gałąź.
Jerry Coffin,
4
Prawdopodobnie nie można zapisać wskaźnika do listy w iteratorach. swap()jest określony jako stały czas i nie unieważnia żadnych iteratorów.
Tavian Barnes,
1
@TavianBarnes Cholera! No cóż, potrójne pośrednie… (to znaczy właściwie nie potrójne. Musiałbyś przechowywać flagę w dynamicznie przydzielanym obiekcie, ale wskaźnik w iteratorze może oczywiście wskazywać bezpośrednio na ten obiekt zamiast pośrednio nad listą.)
5gon12eder
37

Z pewnością, ponieważ wszystkie kontenery obsługujące dwukierunkowe iteratory mają pojęcie rbegin () i rend (), to pytanie jest dyskusyjne?

Budowanie serwera proxy odwracającego iteratory i uzyskiwanie do niego dostępu do kontenera jest banalne.

Ten brak działania jest rzeczywiście O (1).

Jak na przykład:

#include <iostream>
#include <list>
#include <string>
#include <iterator>

template<class Container>
struct reverse_proxy
{
    reverse_proxy(Container& c)
    : _c(c)
    {}

    auto begin() { return std::make_reverse_iterator(std::end(_c)); }
    auto end() { return std::make_reverse_iterator(std::begin(_c)); }

    auto begin() const { return std::make_reverse_iterator(std::end(_c)); }
    auto end() const { return std::make_reverse_iterator(std::begin(_c)); }

    Container& _c;
};

template<class Container>
auto reversed(Container& c)
{
    return reverse_proxy<Container>(c);
}

int main()
{
    using namespace std;
    list<string> l { "the", "cat", "sat", "on", "the", "mat" };

    auto r = reversed(l);
    copy(begin(r), end(r), ostream_iterator<string>(cout, "\n"));

    return 0;
}

oczekiwany wynik:

mat
the
on
sat
cat
the

Biorąc to pod uwagę, wydaje mi się, że komitet normalizacyjny nie poświęcił czasu na zlecenie O (1) odwrotnego zamawiania kontenera, ponieważ nie jest to konieczne, a biblioteka standardowa jest w dużej mierze zbudowana na zasadzie mandowania tylko tego, co jest ściśle konieczne, podczas gdy unikanie powielania.

Tylko mój 2c.

Richard Hodges
źródło
18

Ponieważ musi przejść przez każdy węzeł ( nłącznie) i zaktualizować ich dane (krok aktualizacji jest rzeczywiście O(1)). To sprawia, że ​​cała operacja O(n*1) = O(n).

Blindy
źródło
27
Ponieważ musisz również zaktualizować linki między każdym przedmiotem. Wyjmij kawałek papieru i wyciągnij go zamiast głosowania w dół.
Blindy,
11
Dlaczego więc pytasz, czy jesteś taki pewien? Marnujesz nasz czas.
Blindy,
28
@Curious Węzły podwójnie połączonej listy mają wyczucie kierunku. Powód stamtąd.
But
11
@Blindy Dobra odpowiedź powinna być kompletna. „Wyjmij kawałek papieru i wyciągnij go”, dlatego nie powinno być wymaganym elementem dobrej odpowiedzi. Odpowiedzi, które nie są dobre, podlegają głosowaniu negatywnemu.
RM
7
@ But: Czy muszą? Sprawdź listę połączoną z XOR i tym podobne.
Deduplicator
2

Zamienia również poprzedni i następny wskaźnik dla każdego węzła. Właśnie dlatego bierze Linear. Chociaż można to zrobić w O (1), jeśli funkcja korzystająca z tego LL pobiera również informacje o LL jako dane wejściowe, takie jak to, czy uzyskuje dostęp normalnie, czy odwrotnie.

techcomp
źródło
1

Tylko wyjaśnienie algorytmu. Wyobraź sobie, że masz tablicę z elementami, a następnie musisz ją odwrócić. Podstawową ideą jest iteracja każdego elementu zmieniającego element z pierwszej pozycji do ostatniej pozycji, element z drugiej pozycji do pozycji przedostatniej i tak dalej. Kiedy osiągniesz środek tablicy, zmienisz wszystkie elementy, a więc w (n / 2) iteracjach, co jest uważane za O (n).

danilobraga
źródło
1

Jest to O (n) po prostu dlatego, że musi skopiować listę w odwrotnej kolejności. Każda pojedyncza operacja na elemencie to O (1), ale n jest ich na całej liście.

Oczywiście istnieją pewne operacje wykonywane w czasie stałym związane z ustawieniem miejsca dla nowej listy, późniejszą zmianą wskaźników itp. Notacja O nie uwzględnia indywidualnych stałych, jeśli uwzględni się czynnik n rzędu pierwszego.

SDsolar
źródło