Czy sprzęt / implementacja wpłynie na złożoność algorytmów czas / przestrzeń?

32

Nie jestem nawet studentem CS, więc może to być głupie pytanie, ale proszę o wyrozumiałość ...

W erze komputerów wstępnych możemy zaimplementować strukturę danych tablicowych z czymś w rodzaju tablicy szuflad. Ponieważ jeden zlokalizować szuflady z odpowiadającym indeksu przed ekstrakcji wartość z niej złożoność czas odnośnika tablicy jest , przy założeniu, że przeszukiwanie binarne.O(log(n))

Jednak wynalazek komputerów zrobił wielką różnicę. Współczesne komputery potrafią czytać z pamięci RAM tak szybko, że teraz uważamy, że złożoność czasowa wyszukiwania tablicy jest równa (nawet technicznie tak nie jest, ponieważ przeniesienie rejestru na większą odległość zajmuje więcej czasu itp.)O(1)

Innym przykładem są słowniki Python. Chociaż można uzyskać złożoność dostępu do słownika za pomocą źle napisanej, przeciążonej metody magicznej (lub śmiesznie pecha, tj. Kluczy mających wiele kolizji skrótu), zwykle przyjmuje się, że jest to O ( 1 ) . W takim przypadku złożoność czasu zależy zarówno od implementacji tablicy hashowej słowników Pythona, jak i od implementacji funkcji skrótu przez klucze.O(n)__hash__O(1)

Czy to oznacza, że ​​sprzęt / implementacja może wpływać na złożoność czasową algorytmów? (Chociaż oba przykłady dotyczą struktur danych zamiast algorytmów, te drugie są oparte na tych pierwszych i nigdy nie słyszałem o złożoności struktur danych w czasie, dlatego używam tutaj terminu „algorytmy”)

Dla mnie algorytmy są abstrakcyjne i koncepcyjne, na których właściwości, takie jak złożoność czas / przestrzeń, nie powinno mieć wpływu to, czy są one implementowane w określony sposób, ale czy tak?

nalzok
źródło
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
Gilles „SO- przestań być zły”

Odpowiedzi:

42

Pewnie. Na pewno. Oto jak pogodzić swój dyskomfort.

Analizując czas działania algorytmów, robimy to w odniesieniu do konkretnego modelu obliczeń . Model obliczeniowy określa takie rzeczy, jak czas potrzebny na wykonanie każdej podstawowej operacji (czy czas lub tablica O ( 1 ) ?). Czas działania algorytmu może zależeć od modelu obliczeń.O(logn)O(1)

Po wybraniu modelu obliczeniowego analiza algorytmu jest czysto abstrakcyjnym, koncepcyjnym, matematycznym ćwiczeniem, które nie zależy już od sprzętu.

Jednak w praktyce zazwyczaj chcemy wybrać model obliczeniowy, który odzwierciedla rzeczywistość naszego sprzętu - przynajmniej w rozsądnym stopniu. Jeśli więc nastąpi zmiana sprzętu, możemy zdecydować się przeanalizować nasze algorytmy w innym modelu obliczeń, który jest bardziej odpowiedni dla nowego sprzętu. W ten sposób sprzęt może wpływać na czas działania.

Nie jest to oczywiste, ponieważ w klasach wprowadzających często nie rozmawiamy o modelu obliczeniowym. Po prostu domyślnie przyjmujemy pewne założenia, nigdy nie ujawniając ich jasno. Jest to rozsądne, ze względów pedagogicznych, ale ma swoje koszty - ukrywa ten aspekt analizy. Teraz wiesz.

DW
źródło
Jak powiedziałeś, używamy modelu dostępu swobodnego jako modelu obliczeń, ale kiedy używamy GPU do niektórych obliczeń, złożoność czasowa dla niektórych algorytmów zmienia się, ponieważ wykorzystuje instrukcje SIMD.
Deep Joshi
6
Zauważ też, że notacja O () jest górną granicą. Nawet jeśli użyjesz analogii szuflady, znalezienie szuflady o ograniczonym rozmiarze (rzeczywista pamięć ma ograniczony rozmiar), budowanie zajmuje O (1). Nawet jeśli dotarcie do najdalszej szuflady zajmie Ci 20 minut (wszystkie pamięci podręczne nie trafią, a nawet będziesz musiał załadować dane z wymiany), to nadal jest czas O (1), ponieważ 20 minut będzie twoją ukrytą stałą dostępem do pamięci.
Goswin von Brederlow,
2
O(1)O(n)
1
@CortAmmon: Nawet w przypadku dużej tablicy wyszukiwanie liniowe może być szybsze niż użycie mapy skrótu, jeśli wszystkie oprócz kilku elementów, które szukają, znajdują się bardzo blisko początku. Na przykład, jeśli 50% elementów pasuje do pierwszego elementu, 25% pasuje do drugiego, 12,5% pasuje do trzeciego itd., Z tym wyjątkiem, że jeden element nieparzysty pasuje do czegoś, co może znajdować się w dowolnym miejscu w tablicy, oczekiwanej liczby porównań z wykonaj wyszukiwanie M na liście o rozmiarze N będzie wynosić 2 M + N.
supercat
5
@DeepJoshi Instrukcje SIMD nie zmieniają złożoności algorytmów. Zmieniają tylko stałą multiplikatywną.
Gilles „SO- przestań być zły”
5

Myślę, że w tym pytaniu jest podstawowe nieporozumienie. Porównujesz osobę znajdującą obiekt na posortowanej liście (np. Określoną stronę w książce, biorąc pod uwagę jej numer) z komputerem, który szuka elementu z tablicy.

O(logn)O(1)

Tak, tak, sprzęt (tj. Model obliczeń) wpływa na czas działania algorytmów, jak wyjaśnia DW , ale nie na tym opiera się twój przykład dostępu do tablicy.

David Richerby
źródło
2
Aby być uczciwym, pominąłeś wszystkie elementy pomiędzy „kontrolerem pamięci ustawia napięcia na przewodach adresowych do binarnej reprezentacji siedemnastu” i „dane wracają”. Jeden z tych kawałków prawie na pewno jest wyszukiwanie binarne drzewo z rodzaju opisanego przez OP; ale mimo to wykonuje się w stałym czasie, ponieważ log n wynosi około 64 dla wszystkich n .
Quuxplusone
@Quuxplusone Która część pamięci wykorzystuje wyszukiwanie binarne? Linie adresowe bezpośrednio wybierają komórki pamięci.
David Richerby
Działamy daleko poza moim obszarem specjalizacji, ale starałem się sugerować, że dekoder adresu zostanie zaimplementowany w postaci drzewa demultiplekserów . (Zakładając, że bezpośrednio uderzamy w pamięć fizyczną, ignorując wszelkie dodatkowe komplikacje związane z buforowaniem .) Ponownie, cała ta dodatkowa komplikacja dodaje tylko O(lg size-of-memory), tzn. Jest nieistotna - ale o to dokładnie pytała OP!
Quuxplusone
2

Nie, sprzęt nie wpływa na złożoność algorytmów.

Wpływa jednak na wybór algorytmu i może wpływać na użyteczność analizy złożoności do tego stopnia, że ​​analiza staje się praktycznie bez znaczenia (lub ma jedynie znaczenie akademickie).

Znalezienie właściwej szuflady (jako dostępu do elementu tablicy) wykorzystuje algorytm „otwórz N-ty element bezpośrednio przez indeks”, a nie algorytm „szukaj liniowo” lub „wykonaj wyszukiwanie binarne”. Algorytmy nie są zmieniane, ale wybór.

Z drugiej strony na samą analizę złożoności, a raczej jej znaczenie, ma duży wpływ sprzęt.

Wiele algorytmów, które są gwiezdne dzięki swojej analizie złożoności, są słabo wydajne lub nawet bezużyteczne w praktyce, ponieważ nieznaczny stały czynnik wcale nie jest nieznaczny, ale dominujący .

Lub, ponieważ założenia, które kiedyś były prawdziwe (lub w większości prawdziwe), nie są już dłużej aktualne. Na przykład każda operacja jest w większości taka sama (tylko małe stałe różnice, które nie mają znaczenia), lub nie ma znaczenia, do których lokalizacji pamięci masz dostęp w jakiej kolejności. Na podstawie analizy złożoności można stwierdzić, że niektóre algorytmy są znacznie lepsze, ponieważ wymagają tylko tak wielu operacji. W praktyce może się zdarzyć, że każda operacja powoduje gwarantowane pominięcie pamięci podręcznej (lub, co gorsza, błąd strony), co powoduje, że k jest tak duże, że nie jest już nieznaczne, ale dominuje wszystko.
Jeśli algorytm A potrzebuje 500 operacji na przetworzenie zestawu danych o danym rozmiarze, a algorytm B zajmuje tylko 5, ale B powoduje 5 błędów, które spalają każdy dwadzieścia milionów cykli, to pomimo tego, co może ci powiedzieć analityka lub zdrowy rozsądek, A jest lepsze.

Doprowadziło to do zabawnych niespodzianek, takich jak np. W Hashing z kukułką kilka lat temu. Co było znacznie lepsze, ponieważ [długa lista korzyści]. Po ochłodzeniu szumu okazało się, że był znacznie gorszy, ponieważ gwarantował dwa błędy pamięci podręcznej (błędy, w przypadku większych zestawów danych) przy każdym dostępie.

Podobnie stało się z identyfikowaniem i przetwarzaniem podzbiorów danych. Często poprawnym rozwiązaniem jest w dzisiejszych czasach: „po prostu zrób to wszystko” , tzn. Zamiast zastanawiać się, co jest potrzebne do przetworzenia i zrób to, przetwarzaj cały zestaw danych liniowo, nawet jeśli potrzebujesz tylko połowy. Ponieważ wierzcie lub nie, jest to szybsze ze względu na brak nieprzewidzianych oddziałów, brak pamięci podręcznej, brak błędów strony.
Chcesz odczytać pierwsze 8 kB i ostatnie 3 kB pliku 3 MB? Cóż, przeczytaj cały plik i wyrzuć to, czego nie chcesz, ponieważ poszukiwanie będzie dziesięć razy wolniejsze niż samo czytanie całej rzeczy.

Używać mapy, ponieważ ma ona złożoność logarytmiczną? Lub tablica skrótów, która ma stały czas dostępu? Constant brzmi niesamowicie. Cóż, w przypadku elementów zawierających mniej niż tysiąc rzeczy (w zależności od sprzętu, wielkości danych i wzorca dostępu) wyszukiwanie liniowe może być równie dobre lub lepsze. Niespodzianka.

Zatem nie dotyczy to samych algorytmów , ale ich przydatności i wyboru.

Damon
źródło