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?

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.

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 ⁿ ), 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ć.

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.

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).

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)).

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.

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)

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 ...

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?

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 ...

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.

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.