Który model obliczeń jest „najlepszy”?

W 1937 r. Turing opisał maszynę Turinga. Od tego czasu opisano wiele modeli obliczeń, próbując znaleźć model, który jest jak prawdziwy komputer, ale wciąż wystarczająco prosty do projektowania i analizy algorytmów.

W rezultacie mamy kilkanaście algorytmów dla np. Problemu SORT dla różnych modeli obliczeń. Niestety nie możemy nawet mieć pewności, że implementacja algorytmu z czasem wykonania O (n) w słowie RAM z dozwolonymi operacjami wektora bitowego będzie działać szybciej niż implementacja algorytmu z czasem wykonania O (n⋅logn) w słowo RAM (mówię oczywiście tylko o „dobrych” implementacjach).

Chcę więc zrozumieć, który z istniejących modeli jest „najlepszy” do projektowania algorytmów i szukam aktualnej i szczegółowej ankiety na temat modeli obliczeniowych, która daje zalety i wady modeli oraz ich bliskość z rzeczywistością.

Zawsze uważałem standardowy model Word RAM za „najlepszy” w twoim znaczeniu. Każdy, kto nauczył się programować w języku takim jak C (lub dowolne luźne odpowiedniki, takie jak Java itp.), Ma na myśli dokładnie ten model, gdy myśli o komputerze.

Oczywiście czasami potrzebujesz uogólnień w zależności od reżimów, w których pracujesz. Należy pamiętać o modelu pamięci zewnętrznej. Dotyczy to nie tylko pracy z dyskami, ale także zrozumienia (zmuszania do dbania o) pamięci podręcznej. Oczywiście potraktowanie go zbyt poważnie może również prowadzić do bezsensownych wyników, ponieważ czysty model pamięci zewnętrznej nie liczy się z obliczeniami. Kolejnym uogólnieniem Word RAM jest paralelizm, ale w tej chwili wszyscy jesteśmy trochę zdezorientowani :)

Algorytm z czasem działania z pewnością będzie działał szybciej niż jeden z czasem działania . Jest matematycznym faktem, że ten pierwszy jest szybszy dla dużych :) Rozmiar twojego problemu może po prostu nie być wystarczająco duży, aby to miało znaczenie. Ponieważ przywołujesz sortowanie, zapewniam cię, że bardzo trudno będzie pokonać sortowanie radix za pomocą algorytmu porównawczego dla rozsądnego .O ( n lg n ) n $O(n)$$O(n \lg n)$$n$$n$

Ostatnia uwaga na temat algorytmów i „rzeczywistości”: zawsze miej na uwadze to, co próbujesz osiągnąć. Pracując w algorytmach, staramy się rozwiązać najtrudniejsze problemy (np. SAT na 50 zmiennych lub sortowanie miliarda liczb). Jeśli próbujesz posortować 200 liczb lub rozwiązać SAT na 20 zmiennych, nie potrzebujesz żadnego wymyślnego algorytmu. Dlatego większość algorytmów w rzeczywistości jest dość trywialna. Nie oznacza to nic złego w badaniach algorytmicznych - akurat jesteśmy zainteresowani tym niezwykłym 1/1000 prawdziwych problemów, które są trudne ...

Nie ma jednego całkowicie zadowalającego modelu obliczeniowego, w którym ze smutkiem analizowano by algorytmy, nawet w tym, co można by uznać za tradycyjne ustawienie. Zakłada się, że wszystkie dane są łatwo dostępne, a przestrzeń robocza jest skutecznie nieograniczona.

Maszyna Turinga z wieloma taśmami jest z pewnością dobrze teoretycznie sprecyzowana, a wiele algorytmów zaprojektowano i przeanalizowano w tym modelu na przestrzeni lat. Jednak dla niektórych nie jest wystarczająco ściśle związany z tym, jak działają prawdziwe komputery, aby naprawdę był dobrym modelem do zastosowania w XXI wieku. Z drugiej strony model słowo-RAM stał się popularny i wydaje się dokładniej uchwycić pracę współczesnych komputerów (operacje na słowach nie bitów, stały dostęp do lokalizacji pamięci w czasie). Są jednak aspekty, które nie są idealne. Na przykład nie ma jednego słowa modelu pamięci RAM. Trzeba najpierw określić, które operacje na słowach mają być dozwolone w stałym czasie. Jest na to wiele opcji bez jednej akceptowanej odpowiedzi. Druga, rozmiar słowa w jest zwykle zwiększany wraz z rozmiarem wejściowym (co najmniej tak szybkim jak log (n)), aby umożliwić adresowanie dowolnego elementu w pamięci za pomocą stałej liczby słów. Oznacza to, że trzeba sobie wyobrazić nieskończoną klasę maszyn, na których działa twój algorytm, lub nawet gorzej, że maszyna zmienia się, gdy podajesz jej więcej danych. To niepokojąca myśl dla najczystszych przynajmniej wśród moich studentów. Wreszcie, otrzymujesz nieco zaskakujące wyniki dotyczące złożoności dzięki modelowi słowo-RAM, który może nie zgadzać się z tymi, których uczy się jako uczeń. Na przykład, mnożenie dwóch liczb n-bitowych to czas O (n) w tym modelu, a po prostu odczytanie ciągu n-bitowego jest nagle podliniową operacją czasową. Oznacza to, że trzeba sobie wyobrazić nieskończoną klasę maszyn, na których działa twój algorytm, lub nawet gorzej, że maszyna zmienia się, gdy podajesz jej więcej danych. To niepokojąca myśl dla najczystszych przynajmniej wśród moich studentów. Wreszcie, otrzymujesz nieco zaskakujące wyniki dotyczące złożoności dzięki modelowi słowo-RAM, który może nie zgadzać się z tymi, których uczy się jako uczeń. Na przykład, mnożenie dwóch liczb n-bitowych to czas O (n) w tym modelu, a po prostu odczytanie ciągu n-bitowego jest nagle podliniową operacją czasową. Oznacza to, że trzeba sobie wyobrazić nieskończoną klasę maszyn, na których działa twój algorytm, lub nawet gorzej, że maszyna zmienia się, gdy podajesz jej więcej danych. To niepokojąca myśl dla najczystszych przynajmniej wśród moich studentów. Wreszcie, otrzymujesz nieco zaskakujące wyniki dotyczące złożoności dzięki modelowi słowo-RAM, który może nie zgadzać się z tymi, których uczy się jako uczeń. Na przykład, mnożenie dwóch liczb n-bitowych to czas O (n) w tym modelu, a po prostu odczytanie ciągu n-bitowego jest nagle podliniową operacją czasową.

Powiedziawszy to wszystko, jeśli chcesz tylko wiedzieć, czy Twój algorytm będzie działał szybko, najprawdopodobniej zrobi to :-)

Modele to tylko modele. Nie posunąłbym się za daleko; mówią coś o niektórych aspektach twoich algorytmów, ale nie całą prawdę.

Sugerowałbym, abyś po prostu użył standardowego modelu słowa RAM do analizy i zaimplementował algorytm i zobaczył, jak dobrze sobie radzi w praktyce.

(Właściwie samo wdrożenie algorytmu bez jego uruchamiania mówi ci już o nim wiele ... Po pierwsze, jest to możliwe do wdrożenia.)

Jeśli Twoim zadaniem obliczeniowym jest bardziej przenoszenie danych niż wykonywanie operacji (arytmetycznych) (zestawy danych są ogromne, więc nawet nie mieszczą się w głównej pamięci), to model I / O (wprowadzony przez Aggarwal i Vitter w 1988 r. ) może być bardzo dokładne. W przypadku takich zadań, jak permutacja dużej liczby elementów w pamięci głównej, pomocne może być użycie algorytmów optymalnych dla operacji wejścia / wyjścia (w ostrożnej implementacji).

W przypadku nowoczesnych komputerów wielordzeniowych równoległy wariant wprowadzony przez Arge, Goodricha, Nelsona i Sitchinavę w 2008 r. Może być dokładnym modelem.

Jeśli masz na myśli „najlepszy” model obliczeniowy, który uczyni twoje życie bardziej skomplikowanym, możesz użyć 2-stanowej, 3-symbolowej uniwersalnej maszyny Turinga Wolfram.

Wady : brak oprócz wrażenia, że ​​kroczy się cienką linią między rozumem a szaleństwem;

Wady : tony ...

:-D (tylko żart, w zasadzie zgadzam się z poprzednimi odpowiedziami ...)

Bardziej teoretyczna uwaga: artykuł Ostateczne modele teoretyczne nanokomputerów dowodzą , że odwracalny model siatki 3D jest optymalnym fizycznym modelem obliczeń, w tym sensie, że żaden inny model fizyczny nie mógłby być asymptotycznie szybszy. Omówiono kwestie fizyczne, takie jak prędkość światła, zasada Landauera i granica Bekensteina .

Cytat z streszczenia:

Stwierdzamy, że przy użyciu obecnej technologii odwracalna maszyna zawierająca zaledwie kilkaset warstw obwodów mogłaby przewyższyć każdą istniejącą maszynę, a odwracalny komputer oparty na nanotechnologii musiałby mieć zaledwie kilka mikronów średnicy, aby przewyższyć każdą możliwą nieodwracalną technologię.

Twierdzimy, że silikonowa implementacja odwracalnej siatki 3D może być dziś cenna dla przyspieszenia niektórych obliczeń naukowych i inżynieryjnych, i proponujemy, aby model ten stał się przedmiotem przyszłych badań w teorii algorytmów równoległych dla szerokiego zakresu problemów.