Sortowanie w informatyce a sortowanie w „prawdziwym” świecie

87

Myślałem o sortowaniu algorytmów w oprogramowaniu i możliwych sposobach pokonania O(nlogn)przeszkody. Nie sądzę, że w praktyce możliwe jest szybsze sortowanie, więc proszę, nie myśl, że tak.

Mając to na uwadze, wydaje się, że w przypadku prawie wszystkich algorytmów sortowania oprogramowanie musi znać położenie każdego elementu. Co ma sens, w przeciwnym razie skąd miałoby wiedzieć, gdzie umieścić każdy element według jakichś kryteriów sortowania?

Ale kiedy skrzyżowałem to myślenie ze światem rzeczywistym, wirówka nie ma pojęcia, w jakiej pozycji znajduje się każda cząsteczka, kiedy „sortuje” cząsteczki według gęstości. W rzeczywistości nie dba o pozycję każdej cząsteczki. Jednak może sortować biliony na tryliony elementów w stosunkowo krótkim czasie, ze względu na fakt, że każda cząsteczka podlega prawom gęstości i grawitacji - co dało mi do myślenia.

Czy byłoby możliwe, gdyby jakiś narzut na każdym węźle (pewna wartość lub metoda przypisana do każdego z węzłów) „wymusił” kolejność na liście? Coś w rodzaju wirówki, w której tylko każdy element dba o swoje względne położenie w przestrzeni (w stosunku do innych węzłów). A może to narusza jakąś zasadę obliczeniową?

Myślę, że jedną z najważniejszych kwestii, o których tu mowa, są kwantowe efekty natury i ich zastosowanie równolegle do wszystkich cząstek jednocześnie.

Być może klasyczne komputery z natury ograniczają sortowanie do domeny O(nlogn), gdzie komputery kwantowe mogą przekroczyć ten próg do O(logn)algorytmów działających równolegle.

Fakt, że wirówka jest zasadniczo równoległym sortowaniem bąbelkowym, wydaje się być poprawny, co ma złożoność czasową wynoszącą O(n).

Wydaje mi się, że następną myślą jest to, że jeśli natura może sortować O(n), dlaczego nie mogą tego robić komputery?

Kris
źródło
44
Wirówka jest po prostu masowo równoległą implementacją sortowania bąbelkowego, nic nadzwyczajnego.
el.pescado
3
Mając nprocesory (rdzenie) do sortowania szeregu tylko nelementów, można łatwo osiągnąć O(n)złożoność. Gorzka prawda jest taka, że ​​zwykle musimy sortować długie tablice (tysiące i miliony pozycji) na procesorze z tylko 2..10 rdzeniami.
Dmitry Bychenko
24
Zauważ, że n log n to liczba porównań, które należy wykonać w celu porównania par elementów . Nie ma wymogu, aby algorytm sortowania porównywał pary elementów ; jeśli możesz wymyślić rodzaj, który nie wykonuje porównań parami, możesz zrobić to szybciej niż n log n.
Eric Lippert
7
Brakuje Ci tego, że każda z tych cząsteczek w roztworze to jednostki przetwarzające. Nie ma emulatora zliczającego cząsteczki - cząsteczki liczą się same. Analogiczny komputer miałby tyle rdzeni procesora i niezależnych pamięci, ile jest elementów do sortowania. O(n)sam w sobie nic nie mówi - jest przydatny tylko do porównywania algorytmów z podobnymi ograniczeniami i działających na podobnych architekturach; w kursach wprowadzających dla algorytmicznej złożoności używamy bardzo uproszczony model „komputer”, który ma niewiele wspólnego z wirówek lub rzeczywistych komputerach :)
Luaan
4
Głosuję za zamknięciem tego pytania jako niezwiązanego z tematem, ponieważ należy ono do cs.stackexchange.com
Robert Fraser

Odpowiedzi:

71

EDYCJA: Źle zrozumiałem mechanizm wirówki i wygląda na to, że robi porównanie, do tego masowo równoległe. Istnieją jednak procesy fizyczne, które działają na właściwości sortowanej jednostki, zamiast porównywać dwie właściwości. Ta odpowiedź obejmuje algorytmy o takim charakterze.

Wirówka stosuje mechanizm sortowania, który tak naprawdę nie działa na zasadzie porównań między elementami, ale w rzeczywistości na podstawie właściwości („siła odśrodkowa”) na każdym pojedynczym elemencie. Niektóre algorytmy sortowania wpisują się w ten temat, zwłaszcza Radix Sort . Kiedy ten algorytm sortowania jest zrównoleglony, powinien zbliżyć się do przykładu wirówki.

Niektóre inne nieporównawcze algorytmy sortowania to Sortowanie zbiorcze i Sortowanie zliczania . Może się okazać, że sortowanie Bucket również pasuje do ogólnej idei wirówki (promień może odpowiadać koszowi).

Kolejnym tak zwanym „algorytmem sortowania”, w którym każdy element jest rozpatrywany oddzielnie, jest sortowanie uśpienia . Tutaj raczej czas, a nie siła odśrodkowa, jest wielkością używaną do sortowania.

user1952500
źródło
To jest właściwie prawidłowa odpowiedź - sortowanie binariów / sortowanie radix ma złożoność O (n), pod warunkiem, że bins i wejście są dostępne w czasie O (1).
pjc50
5
Chciałem zapytać „Czy ktoś inny od razu pomyśli o sortowaniu snu?”.
Wygląda na to
Wirówki działają poprzez porównywanie elementów; funkcją skrótu jest (przede wszystkim) gęstość. Na przykład, jeśli odwirujesz mieszaninę propanu i powietrza, otrzymasz propan posortowany do granic; ale jeśli odwirujesz propan i wodę, otrzymasz propan posortowany do środka (woda jest bardziej gęsta). Proces ten jest prawie dokładnie taki sam, jak proces fizyczny, od którego nazwano „sortowanie bąbelkowe”.
Nat,
Czy złożoność SleepSort nie polega w rzeczywistości na złożoności harmonogramu?
Morwenn
@Morwenn stary program planujący Linuksa był O (1), podczas gdy nowy to O (log n). Oba te czynniki przewyższają stałe czynniki podczas snu
użytkownik1952500
35

Złożoność obliczeniowa jest zawsze definiowana w odniesieniu do jakiegoś modelu obliczeniowego. Na przykład algorytm, który jest O ( n ) na typowym komputerze, może mieć wartość O (2 n ), jeśli zaimplementowano go w Brainfuck .

Model obliczeniowy wirówki ma kilka interesujących właściwości; na przykład:

  • obsługuje arbitralny paralelizm; bez względu na to, ile cząstek znajduje się w roztworze, wszystkie można sortować jednocześnie.
  • nie daje ściśle liniowego rodzaju cząstek według masy, ale raczej bardzo bliskie (niskoenergetyczne) przybliżenie.
  • nie jest możliwe zbadanie poszczególnych cząstek w wyniku.
  • nie jest możliwe sortowanie cząstek według różnych właściwości; obsługiwana jest tylko masa.

Biorąc pod uwagę, że nie mamy możliwości zaimplementowania czegoś takiego w sprzęcie komputerowym ogólnego przeznaczenia, model może nie mieć praktycznego znaczenia; ale nadal warto to zbadać, zobaczyć, czy można się czegoś z tego nauczyć. Na przykład algorytmy niedeterministyczne i algorytmy kwantowe były aktywnymi obszarami badań, mimo że obecnie żadnego z nich nie można zaimplementować.

ruakh
źródło
Natura / fizyka jest generalnie równoległa (dlatego symulacja na naszych komputerach szeregowych jest tak kosztowna obliczeniowo), więc tak, analogia OP ma poważną wadę. Jednak nadal potrzeba czasu, aby cząsteczki / cząsteczki poruszały się wzdłuż długości probówki lub czegokolwiek innego, więc dłuższa probówka jest jak więcej pracy na gwint, ale szersza probówka oznacza bardziej równoległość. (I pamiętaj, że wirówka nie sortuje po powierzchni probówki, więc jest to wiele równoległych sortowań bez łączenia, ale może po drodze pewne interakcje. W przeciwieństwie do rzeczywistego sortowania na komputerze równoległym, z ostatecznym scalaniem)
Peter Cordes
29

Rzecz w tym, że masz tylko prawdopodobieństwo posortowania listy za pomocą wirówki. Podobnie jak w przypadku innych sortowań w świecie rzeczywistym [potrzebne źródło], możesz zmienić prawdopodobieństwo, że posortowałeś listę, ale nigdy nie będziesz mieć pewności bez sprawdzenia wszystkich wartości (atomów).

Rozważ pytanie: „Jak długo powinnaś pracować wirówka?”
Jeśli uruchomiłeś go tylko przez pikosekundę, twoja próbka może być mniej posortowana niż stan początkowy ... lub jeśli uruchomiłeś ją przez kilka dni, może być całkowicie posortowana. Jednak nie wiedziałbyś bez faktycznego sprawdzenia zawartości.

ti7
źródło
To całkiem dobra uwaga. Skąd wiesz? Z drugiej strony, jeśli obowiązujące zasady są wystarczająco dobre, czy chciałbyś się o tym dowiedzieć? (tj. jeśli zmniejszysz prawdopodobieństwo, że stanie się ono pomijalne).
Kris
Zawsze możesz obliczyć, ile czasu zajmie osiągnięcie przez cząstkę końca wirówki. Znasz przyspieszenie (w ^ 2 * r, gdzie w jest prędkością kątową) i możesz obliczyć czas.
user1952500
1
To prawda, ale ponieważ jest to zagmatwane przez ruchy Browna , inne siły atomowe i fizykę kwantową (dzięki, drobne rzeczy!), Nadal nie możesz być całkowicie pewien, że posortowałeś listę, dopóki nie sprawdzisz stanu.
ti7
1
Jeśli nie masz bardzo małych cząstek, możesz zignorować efekty kwantowe. Jeśli masz bardzo małe cząstki, algorytm sortowania nie musi działać, a tak naprawdę nie możesz polegać na tym, że zadziała ze względu na efekty kwantowe. I nie można wiarygodnie sprawdzić stanu ze względu na zasadę nieoznaczoności (sprawdzenie jednej cząstki spowoduje przesunięcie innych cząstek).
user1952500
1
@Kris Cóż, wiemy, że wirówka nie sortuje idealnie. Robimy to tak długo, aż różnica przestanie mieć znaczenie dla praktycznego celu - na przykład zapobiegania krzepnięciu krwi w wirówce. Ale spójrz na wirówki uranowe - te muszą sortować przedmioty, które są znacznie „bliżej” (trudniejsze do rozdzielenia) i wymagają ogromnego obiektu, który sortuje w kółko i na nowo, ogromnym kosztem, aby wyprodukować niewielkie ilości żądanego materiału. Wirówka ma określony rozmiar, a czas separacji jest proporcjonalny do szerokości probówek i ... Nie możesz po prostu powiedzieć O (n), yay!
Luaan
5

Rzeczywistym przykładem komputerowego „porządkowania” byłyby autonomiczne drony, które współpracują ze sobą, zwane „rojami dronów”. Drony działają i komunikują się zarówno jako jednostki, jak i jako grupa, i mogą śledzić wiele celów. Drony wspólnie decydują, które drony będą podążać za jakim celem i oczywistą potrzebą unikania kolizji między dronami. Wczesne wersje to drony, które przelatywały przez punkty przelotowe, pozostając w szyku, ale formacja mogła się zmienić.

W przypadku „sortowania” drony można zaprogramować tak, aby tworzyły linię lub wzór w określonej kolejności, początkowo wypuszczane w dowolnej permutacji lub kształcie, a wspólnie i równolegle szybko tworzyłyby uporządkowaną linię lub wzór.

Wracając do sortowania komputerowego, jednym z problemów jest to, że istnieje jedna główna magistrala pamięci i nie ma możliwości, aby duża liczba obiektów poruszała się równolegle w pamięci.

znać położenie każdego elementu

W przypadku sortowania na taśmie, położenie każdego elementu (nagrania) jest „znane” tylko „taśmie”, a nie komputerowi. Sortowanie na taśmie musi działać tylko z dwoma elementami jednocześnie i sposobem na oznaczenie granic przebiegu na taśmie (znacznik pliku lub rekord o innym rozmiarze).

rcgldr
źródło
4

IMHO, ludzie za dużo myślą log (n). O (nlog (n)) JEST praktycznie O (n). I potrzebujesz O (n) tylko do odczytu danych.

Wiele algorytmów, takich jak quicksort, zapewnia bardzo szybki sposób sortowania elementów. Możesz zaimplementować różne odmiany szybkiego sortowania, które w praktyce byłyby bardzo szybkie.

Z natury wszystkie systemy fizyczne są nieskończenie równoległe. Możesz mieć ładunek atomów w ziarnku piasku, natura ma wystarczającą moc obliczeniową, aby dowiedzieć się, gdzie powinien znajdować się każdy elektron w każdym atomie. Więc jeśli masz wystarczająco dużo zasobów obliczeniowych (O (n) procesorów), możesz posortować n liczb w czasie log (n).

Z komentarzy:

  1. Biorąc pod uwagę fizyczny procesor, który ma k liczby elementów, może osiągnąć równoległość co najwyżej O (k). Jeśli przetwarzasz n liczb arbitralnie, nadal przetwarza je z szybkością związaną z k. Możesz również sformułować ten problem fizycznie. Możesz stworzyć n stalowych kulek o masach proporcjonalnych do liczby, którą chcesz zakodować, co w teorii można rozwiązać za pomocą wirówki. Ale tutaj ilość atomów, których używasz, jest proporcjonalna do n. Podczas gdy w standardowym przypadku masz ograniczoną liczbę atomów w procesorze.

  2. Innym sposobem myślenia o tym jest to, że masz mały procesor podłączony do każdego numeru i każdy procesor może komunikować się ze swoimi sąsiadami, możesz posortować wszystkie te liczby w czasie O (log (n)).

ElKamina
źródło
Ale czy to nie tylko obliczenia - wykorzystanie fizycznych właściwości natury do wykonania jakiejś pracy? Być może przechodzę tutaj do obliczeń kwantowych, ale jeśli można to zrobić fizycznie, powinno to być możliwe obliczeniowo? Być może klasyczne obliczenia są blokadą drogową między O (nlogn) i O (logn).
Kris
2
@Kris Niezupełnie. Biorąc pod uwagę fizyczny procesor, który ma k liczby elementów, może osiągnąć równoległość co najwyżej O (k). Jeśli przetwarzasz n liczb arbitralnie, nadal przetwarza je z szybkością związaną z k. Możesz również sformułować ten problem fizycznie. Możesz stworzyć n stalowych kulek o masach proporcjonalnych do liczby, którą chcesz zakodować, co można rozwiązać za pomocą wirówki w teorii. Ale tutaj ilość atomów, których używasz, jest proporcjonalna do n. Podczas gdy w standardowym przypadku masz ograniczoną liczbę atomów w procesorze.
ElKamina,
Czy to ograniczenie dotyczy również obiektów QM? Tak z ciekawości
Kris
1
@Kris Nie rozumiem QM wystarczająco szczegółowo, aby odpowiedzieć na to pytanie.
ElKamina,
Bez obaw! Jestem po prostu bardzo ciekawa i nie mogę zasnąć haha. Dziękuję za ciekawe odpowiedzi.
Kris
4

Kiedy zaczynałem studia, latem pracowałem w biurze po szkole średniej. Uczyłem się informatyki AP, między innymi sortowania i wyszukiwania .

Zastosowałem tę wiedzę w kilku systemach fizycznych, które pamiętam:

Naturalne sortowanie przez scalanie, aby rozpocząć…

System drukował wieloczęściowe formularze, w tym odrywany plik wielkości karty, który należało złożyć w banku szuflad.

Zacząłem od stosu i posortowałem stos. Pierwszym krokiem jest zebranie około 5, wystarczająco niewielu, aby łatwo było je uporządkować w dłoni. Umieść posortowaną paczkę w dół, krzyżując każdy stos, aby oddzielić je.

Następnie połącz każdą parę stosów, tworząc większy stos. Powtarzaj, aż będzie tylko jeden stos.

… Sortowanie przez wstawianie do zakończenia

Posortowane karty są łatwiejsze do ułożenia, ponieważ każda następna znajduje się nieco dalej w tej samej otwartej szufladzie.

Sortowanie radix

Ten nikt inny nie rozumiał, jak zrobiłem to tak szybko, pomimo wielokrotnych prób nauczenia.

Należy posortować duże pudełko odcinków czeków (rozmiar kart perforowanych). Wygląda to jak gra w pasjansa na dużym stole - rozdawaj, układaj, powtarzaj.

Ogólnie

30 lat temu zauważyłem, o co pytasz: pomysły przenoszą się do systemów fizycznych całkiem bezpośrednio, ponieważ istnieją względne koszty porównań i obsługi rekordów oraz poziomy buforowania.

Wykraczanie poza dobrze zrozumiałe odpowiedniki

Przypominam sobie esej na twój temat, który poruszył kwestię spaghetti . Przycinasz długość suszonego makaronu, aby wskazać wartość klucza i oznaczasz go identyfikatorem rekordu. To jest O (n), po prostu przetwarzamy każdy element raz.

Następnie chwytasz pakiet i stukasz jednym końcem w stół. Wyrównują się na dolnych krawędziach i są teraz posortowane. Możesz trywialnie zdjąć najdłuższy i powtórzyć. Odczyt jest również O (n).

W „prawdziwym świecie” dzieją się dwie rzeczy, które nie odpowiadają algorytmom. Po pierwsze, wyrównanie krawędzi jest operacją równoległą. Każdy element danych jest również procesorem (mają do niego zastosowanie prawa fizyki). Tak więc, ogólnie rzecz biorąc, skalujesz dostępne przetwarzanie z n, zasadniczo dzieląc klasyczną złożoność przez współczynnik n.

Po drugie, w jaki sposób wyrównanie krawędzi prowadzi do pewnego rodzaju? Prawdziwy sortowania jest w read-out, która pozwala znaleźć najdłuższy w jednym kroku, nawet jeśli nie porównać je wszystkie znaleźć najdłużej. Ponownie podziel przez współczynnik n, więc znalezienie największego wynosi teraz O (1).

Innym przykładem jest użycie obliczeń analogowych: model fizyczny rozwiązuje problem „natychmiast”, a praca przygotowawcza to O (n). W zasadzie obliczenia są skalowane na podstawie liczby wchodzących w interakcje komponentów, a nie liczby przygotowanych elementów. Zatem obliczenia skalują się z n². Przykładem, o którym myślę, jest ważone obliczenie wieloczynnikowe, które zostało wykonane przez wiercenie otworów w mapie, zawieszanie ciężarów na sznurkach przechodzących przez otwory i gromadzenie wszystkich sznurków na pierścieniu.

JDługosz
źródło
Spaghetti to była fajna lektura. Podobało mi się myślenie o tym, ale krytykuję akcję skanowania w poszukiwaniu najdłuższego makaronu. To nie jest tak naprawdę operacja O (1), ponieważ skanujesz makaron. Wyobraź sobie dziesięć tysięcy makaronów i kilka o podobnej długości ... to nie jest operacja O (1) „gałka oczna”. W rzeczywistości trzeba zeskanować wszystkie nieposortowane makarony, aby znaleźć najdłuższy.
ThisClark,
Możesz „zeskanować” wszystkie kluski, kładąc dłoń na całej pęczku i wyciągając jeden najwyższy makaron, który styka się z twoją ręką. Jeśli makaron ma bardzo małą długość, użyj bardziej precyzyjnej powierzchni „dłoni”, aby złapać najwyższy makaron. Kluski nie są wybierane szeregowo, jak w przypadku sortowania przez selekcję, są one wybierane wszystkie naraz, więc jest dostępnych O (n) mocy obliczeniowej.
Bradd Szonye
1
@ThisClark potrzebujesz bardziej precyzyjnego przyrządu: płaskiej płaszczyzny równoległej do ogranicznika na dnie, która wyrównuje makaron. Ostrożnie opuść go, aż jeden makaron (najwyższy) zostanie dotknięty i umieszczony pod kompresją. Porównanie wysokości samolotu z każdym makaronem jest wykonywane równolegle przez ten makaron. Sugerujesz, że potrzebny jest wyższy współczynnik, ale ten argument nie zmienia Big-O.
JDługosz
3

Sortowanie nadal trwa O (n) całkowity czas. To, że jest szybsze niż to, wynika z równoległości .

Możesz zobaczyć wirówkę jako Bucketsort z n atomów, zrównoleglonych na n rdzeniach (każdy atom działa jak procesor).

Sortowanie można przyspieszyć przez zrównoleglenie, ale tylko przez stały współczynnik, ponieważ liczba procesorów jest ograniczona, O (n / C) nadal wynosi O (n) (procesory mają zwykle <10 rdzeni, a GPU <6000)

Siphor
źródło
2

Wirówka nie sortuje węzłów, przykłada do nich siłę, po czym reagują równolegle do niej. Więc jeśli miałbyś zaimplementować sortowanie bąbelkowe, w którym każdy węzeł porusza się równolegle w górę lub w dół na podstawie swojej „gęstości”, miałbyś implementację wirówki.

Pamiętaj, że w prawdziwym świecie możesz uruchomić bardzo dużą liczbę równoległych zadań, przy czym na komputerze możesz mieć maksymalnie rzeczywistą liczbę równoległych zadań równą liczbie fizycznych jednostek przetwarzających.

W końcu byłbyś również ograniczony dostępem do listy elementów, ponieważ nie można jej modyfikować jednocześnie przez dwa węzły ...

Fokstrot
źródło
1

Czy byłoby możliwe, gdyby jakiś narzut na każdym węźle (pewna wartość lub metoda przypisana do każdego z węzłów) „wymusił” kolejność na liście?

Podczas sortowania za pomocą programów komputerowych wybieramy właściwość sortowanych wartości. Zwykle jest to wielkość liczby lub kolejność alfabetyczna.

Coś w rodzaju wirówki, w której tylko każdy element dba o swoje względne położenie w przestrzeni (w stosunku do innych węzłów)

Ta analogia trafnie przypomina mi proste sortowanie bąbelkowe. Jak mniejsze liczby pojawiają się w każdej iteracji. Jak twoja logika wirówki.

Aby odpowiedzieć na to pytanie, czy nie robimy czegoś takiego w sortowaniu opartym na oprogramowaniu?

Sudip Bhandari
źródło
1
Myślę, że masz rację. Myślę, że straciłem tutaj swoją analogię, że zapomniałem, że każda cząsteczka działa równolegle. Więc to byłoby jak równoległe sortowanie bąbelkowe ...
Kris,
1

Przede wszystkim porównujesz dwa różne konteksty, jeden to logika (komputer), a drugi to fizyka, która (jak dotąd) udowodniła, że ​​możemy modelować niektóre jej części za pomocą wzorów matematycznych, a my jako programiści możemy używać tych wzorów do symulacji (niektóre elementy) fizyki w pracy logicznej (np. silnik fizyki w silniku gry).

Po drugie, mamy pewne możliwości w świecie komputerów (logiki), które są prawie niemożliwe w fizyce, na przykład możemy uzyskać dostęp do pamięci i znaleźć dokładną lokalizację każdego bytu w każdym momencie, ale w fizyce jest to ogromny problem z zasadą nieoznaczoności Heisenberga .

Po trzecie, jeśli chcesz odwzorować wirówki i ich działanie w świecie rzeczywistym, w świecie komputerów, to tak, jakby ktoś (Bóg) dał ci super-komputer ze wszystkimi zastosowanymi regułami fizyki i robisz w nim małe sortowanie ( używając wirówki) i mówiąc, że twój problem sortowania został rozwiązany w o (n), ignorujesz ogromną symulację fizyki, która ma miejsce w tle ...

Panie Q
źródło
0

Inna perspektywa jest taka, że ​​to, co opisujesz za pomocą wirówki, jest analogiczne do tego, co nazywa się „sortowaniem spaghetti” ( https://en.wikipedia.org/wiki/Spaghetti_sort ). Powiedzmy, że masz pudełko niegotowanych prętów spaghetti o różnej długości. Trzymaj je w pięści i poluzuj rękę, aby obniżyć je pionowo, tak aby wszystkie końce spoczywały na poziomym stole. Bum! Są posortowane według wysokości. O (stały) czas. (Lub O (n), jeśli uwzględnisz wybieranie prętów według wysokości i umieszczanie ich w a.. Stojaku do spaghetti, jak sądzę?)

Można tam zauważyć, że jest to O (stała) w liczbie kawałków spaghetti, ale ze względu na skończoną prędkość dźwięku w spaghetti jest to O (n) na długości najdłuższego pasma. Nie ma więc nic za darmo.

eac2222
źródło
To jest to samo, co powiedziałem 11 godzin wcześniej. Następnie wyjaśniłem, w jaki sposób układy fizyczne pozwalają na dzielenie przez n lub przez n² i zachowują model algorytmów i obliczeń.
JDługosz
0

Zastanów się: czy „sortowanie przez wirówkę” naprawdę skaluje się lepiej? Pomyśl o tym, co się stanie, gdy zwiększysz swoją skalę.

  • Probówki muszą być coraz dłuższe.
  • Ciężki materiał musi podróżować coraz dalej, aby dostać się na dno.
  • Moment bezwładności wzrasta, wymagając większej mocy i dłuższych czasów, aby przyspieszyć do prędkości sortowania.

Warto również rozważyć inne problemy z sortowaniem wirówkowym. Na przykład możesz działać tylko na wąskiej skali rozmiarów. Komputerowy algorytm sortowania może obsłużyć liczby całkowite od 1 do 2 ^ 1024 i więcej, bez problemu. Umieść w wirówce coś, co waży 2 ^ 1024 razy więcej niż atom wodoru, a to jest czarna dziura i galaktyka została zniszczona. Algorytm zawiódł.

Oczywiście prawdziwa odpowiedź jest taka, że ​​złożoność obliczeniowa jest związana z pewnym modelem obliczeniowym, jak wspomniano w innej odpowiedzi. A „sortowanie przez wirówkę” nie ma sensu w kontekście typowych modeli obliczeniowych, takich jak model pamięci RAM, model IO lub wielotaśmowe maszyny Turinga.

Craig Gidney
źródło