Kompiuterių mokslo rūšiavimas ir rūšiavimas „realiame“ pasaulyje

Aš galvojau apie algoritmų rūšiavimą programinėje įrangoje ir galimus būdus, kaip įveikti kliūtį O(nlogn) . Nemanau, kad tai praktiškai gali būti sutrumpinta greičiau, todėl nemanau, kad tai darau.

Taip sakant, atrodo, kad beveik visi rūšiavimo algoritmai, programinė įranga turi žinoti kiekvieno elemento padėtį. Kas yra prasminga, kitaip, kaip jis žinotų, kur kiekvieną elementą įdėti pagal tam tikrus rūšiavimo kriterijus?

Bet kai aš peržengiau šį mąstymą su realiu pasauliu, centrifuga neturi idėjos, kokia padėtis yra kiekvienoje molekulėje, kai ji „rūšiuoja“ molekules pagal tankį. Tiesą sakant, jis nerūpi kiekvienos molekulės padėties. Tačiau trilijonus į trilijonus objektų galima surūšiuoti per gana trumpą laiką dėl to, kad kiekviena molekulė seka tankį ir gravitacinius įstatymus, o tai privertė mane galvoti.

Ar būtų įmanoma, kad kiekvienas mazgas (tam tikra reikšmė ar metodas, pridedamas prie kiekvieno mazgo) galėtų „priversti“ sąrašą? Kažkas panašaus į centrifugą, kurioje tik kiekvienas elementas rūpinasi santykine padėtimi erdvėje (kitų mazgų atžvilgiu). Ar tai skaičiavimo metu pažeidžia tam tikrą taisyklę?

Manau, kad vienas iš svarbiausių čia iškeltų dalykų yra gamtos kvantinis-mechaninis poveikis ir kaip jie taikomi lygiagrečiai su visomis dalelėmis vienu metu.

Galbūt klasikiniai kompiuteriai iš esmės apriboja rūšiavimą O(nlogn) domene, kur, kadangi kvantiniai kompiuteriai gali pereiti šią ribą į O(logn) algoritmus, kurie veikia lygiagrečiai.

Panašu, kad centrifuga iš esmės yra lygiagretus burbulo vaizdas, atrodo teisinga, o tai turi laiko sudėtingumą O(n) .

Manau, kad kita mintis yra ta, kad jei gamta gali būti suskirstyta į O(n) , kodėl kompiuteriai negali būti?

87
11 янв. Kris rinkosi sausio 11 d 2017-01-11 09:58 '17 at 9:58 2017-01-11 09:58
@ 12 atsakymų

EDIT: Aš nesupratau centrifugos mechanizmo, ir atrodo, kad jis lygina, kurioje yra lygiagrečiai. Tačiau yra fizinių procesų, kurie veikia su rūšiuojamo objekto nuosavybe ir nepalygina dviejų savybių. Šis atsakymas apima tokio pobūdžio algoritmus.

Centrifuga naudoja rūšiavimo mechanizmą, kuris faktiškai neveikia lyginant elementus, bet iš tikrųjų naudojant atskirą elementą („išcentrinę jėgą“) kiekvienam atskiram elementui. Kai kurios rūšiavimo algoritmai patenka į šią temą, ypač „ Radix Sort“ . Kai šis rūšiavimo algoritmas yra lygiagretus, jis turėtų kreiptis į centrifugos pavyzdį.

Kai kurie kiti lyginamieji rūšiavimo algoritmai Rūšiuoti kibirą ir skaičiavimą Rūšiuoti . Jūs galite pastebėti, kad kibiras taip pat atitinka bendrą centrifugos idėją (spindulys gali atitikti krepšį).

Kitas vadinamasis „rūšiavimo algoritmas“, kur kiekvienas elementas yra vertinamas atskirai, yra miego režimas . Čia laikas, o ne išcentrinė jėga, veikia kaip rūšiavimas.

73
11 янв. Atsakymą pateikė vartotojo1952500 11 sausis 2017-01-11 10:21 '17 at 10:21 2017-01-11 10:21

Kompiuterinis sudėtingumas visada nustatomas atsižvelgiant į kai kuriuos skaičiavimo modelius. Pavyzdžiui, algoritmas, kurį O (n) tipiniame kompiuteryje gali būti O (2 n ), jei jis yra įdiegtas „ Brainfuck“ .

Centrifugos dizaino modelis turi keletą įdomių savybių; pavyzdžiui:

  • ji remia savavališką lygiagretumą; Nesvarbu, kiek dalelių yra tirpale, jie visi gali būti surūšiuoti tuo pačiu metu.
  • ji nesuteikia griežto linijinio dalelių matmens, o labai artimos (mažos energijos) aproksimacijos.
  • Dėl to neįmanoma atsižvelgti į atskiras daleles.
  • neįmanoma surūšiuoti dalelių pagal skirtingas savybes; palaikoma tik masė.

Atsižvelgiant į tai, kad mes neturime gebėjimo įgyvendinti kažką panašaus į bendrąją įrangą, modelis gali būti nepraktiškas; bet vis tiek verta ištirti, ar yra nieko, ko galima išmokti iš jo. Neteterministiniai algoritmai ir kvantiniai algoritmai , pavyzdžiui, buvo aktyvios mokslinių tyrimų sritys, nors nė vienas iš jų šiandien neįgyvendintas.

36
11 янв. atsakymas duotas ruakh 11 jan. 2017-01-11 10:21 '17 at 10:21 2017-01-11 10:21

Piktnaudžiavimas yra tas, kad jūs galite surūšiuoti sąrašą naudojant centrifugą. Kaip ir kituose realaus pasaulio vaizduose, galite pakeisti tikimybę, kad jūsų sąrašas bus surūšiuotas, bet niekada nesate tikras, neišnagrinėdami visų reikšmių (atomų).

Apsvarstykite klausimą: „Kiek laiko turėtumėte paleisti centrifugą?“
Jei tiesiog paleisite jį PS, jūsų pavyzdys gali būti mažiau surūšiuotas nei pradinė būsena .. arba jei ją paleisite kelias dienas, jis gali būti visiškai surūšiuotas. Tačiau jūs nežinote, nekontroliuodami turinio.

30
11 янв. atsakymas pateikiamas ti7 sausio 11 d 2017-01-11 10:05 '17 at 10:05 2017-01-11 10:05

Autonominiai nepilotuojami orlaiviai, dirbantys tarpusavyje, vadinami „nepilotuojamais pulkais“, gali būti tikras kompiuterio „užsakymo“ pavyzdys. „Drones“ veikia ir praneša apie asmenis, taip pat grupę ir gali stebėti kelis tikslus. „Drones“ kartu nusprendžia, kurie dronai laikysis tikslų, ir akivaizdus poreikis išvengti susidūrimų tarp nepilotuojamų orlaivių. Ankstyvosios šios versijos buvo nepilotuojamos orlaiviai, judėję per kelio taškus, likę formavimosi metu, tačiau susidarymas gali pasikeisti.

„Rūšiuoti“, dronai gali būti užprogramuoti taip, kad sudarytų liniją ar modelį tam tikroje eilėje, iš pradžių išleistą bet kokioje permutacijoje ar formoje, ir kartu ir lygiagrečiai, jie greitai sudaro užsakytą eilutę arba modelį.

Grįžus į rūšiavimą kompiuteryje, viena problema yra ta, kad yra vienas pagrindinis atminties magistralė, ir nėra galimybės daugeliui objektų perkelti atmintyje lygiagrečiai.

žinoti kiekvieno elemento padėtį

Rūšiuojant juostą, kiekvieno elemento (įrašo) padėtis yra „žinoma“ „juostoje“, o ne kompiuteryje. Rūšiavimas pagal juostą turėtų veikti tik su dviem elementais vienu metu, taip pat nurodyti juostos paleidimo ribas (failo ženklas arba kitokio dydžio įrašymas).

6
11 янв. atsakymą pateikė rcgldr 11 sausis 2017-01-11 10:21 '17 at 10:21 2017-01-11 10:21

Dirbau biure vasarą po baigimo, kai pradėjau mokytis. Be kitų dalykų, studijavau AP kompiuterių moksluose, rūšiuoti ir ieškoti .

Šias žinias pritaikiau kelioms fizinėms sistemoms, kurias galiu prisiminti:

Rūšiuoti natūralią sintezę paleisti ...

Spausdintų kelių dalių formų sistema, įskaitant kortelės dydžio įspaudą, kuris turėjo būti pateiktas dėžių bankui.

Aš pradėjau su krūva jų ir pirmiausia paėmiau krūvą. Pirmas žingsnis - surinkti 5 ar daugiau, tiesiog pakankamai, kad juos būtų galima lengvai įdėti į rankas. Įdėkite suskirstytą paketą žemyn, kirsdami kiekvieną steką, kad juos atskirtumėte.

Tada sujunkite kiekvieną stekų porą ir sukurkite didesnį kaminą. Pakartokite, kol yra tik vienas stekas.

... įterpti rūšiuoti

Lengviau įkelti surūšiuotus žemėlapius, nes kiekvienas kitas yra šiek tiek toliau palei tą patį atvirą >

Radix veislė

Tai dar nesuprato, kaip tai padariau taip greitai, nepaisant pakartotinių bandymų jį išmokyti.

Būtina surūšiuoti didelį dėžutės >

Paprastai

Prieš 30 metų pastebėjau tai, ko klausiate: idėjų perkėlimas į fizines sistemas visiškai tiesiogiai, nes yra santykinės palyginimų ir įrašų apdorojimo sąnaudos ir talpyklos lygiai.

Perėjimas prie gerai suprantamų ekvivalentų

Prisimenu esė apie jūsų temą, ir tai lėmė spagetų rūšiavimą. Pjaukite džiovintų makaronų ilgį, kad pamatytumėte pagrindinę vertę, ir pavadinkite jį įrašo identifikatoriumi. Tai yra O (n), tiesiog apdorojant kiekvieną elementą vieną kartą.

Tada patraukite paketą ir bakstelėkite vieną galą ant stalo. Jie yra suderinti apatiniuose kraštuose, o dabar jie yra rūšiuojami. Jūs galite trivialiai nuimti ilgiausią ir kartoti. Taip pat perskaitykite O (n).

„Realiame pasaulyje“ yra du dalykai, kurie neatitinka algoritmų. Pirma, kraštų derinimas yra lygiagrečios operacijos. Kiekvienas duomenų elementas taip pat yra procesorius (jam taikomi fizikos įstatymai). Taigi, apskritai, jūs nubrėžiate turimą apdorojimą n, iš esmės padalijus savo klasikinį sudėtingumą n.

Antra, kaip kraštų lygiavimas atlieka rūšiavimą? Tikrasis rūšiavimas - tai skaitymas, kuris leidžia jums rasti ilgiausią viename žingsnyje, net jei lygintumėte visus juos, kad rastumėte ilgiausią. Vėlgi, padalinkite iš faktoriaus n, todėl rasti didžiausią dabar yra O (1).

Kitas pavyzdys yra analoginio skaičiavimo naudojimas: fizinis modelis išsprendžia problemą „iš karto“ ir preparatą O (n). Iš esmės skaičiavimas yra susietas su sąveikaujančių komponentų skaičiumi, o ne paruoštų elementų skaičiumi. Taigi skaičiavimas yra suskirstytas su n². Pavyzdys, kurį aš turiu omenyje, yra svertinis, daugiafunkcinis skaičiavimas, kuris buvo atliktas gręžiant skyles žemėlapyje, kabant skales iš linijų, einančių per skyles, ir surinkti visas žiedo linijas.

5
11 янв. Atsakymas duotas JDługosz 11 sausio. 2017-01-11 12:29 '17 at 12:29 2017-01-11 12:29

IMHO, žmonės apverčia žurnalą (n). O (nlog (n)) IS yra praktiškai O (n). Ir jums reikia O (n) tik skaitymo duomenų.

Daugelis algoritmų, tokių kaip quicksort, suteikia labai greitą elementų rūšiavimo būdą. Galite įdiegti greitas rūšiavimo parinktis, kurios praktiškai būtų labai greitos.

Iš tiesų visos fizinės sistemos yra begalinės lygiagrečios. Jūs galite turėti atomų srautą smėlio grūduose, gamta turi pakankamai kompiuterinės galios, kad išsiaiškintų, kur kiekvienas elektronas turi būti kiekviename atome. Todėl, jei turite pakankamai kompiuterinių išteklių (O (n) procesorių), galite suskirstyti n numerius į log (n) laiką.

Iš komentarų:

  • Fiziniam procesoriui su k elementų skaičiumi jis gali užtikrinti ne daugiau kaip O (k) lygiagretumą. Jei savavališkai apdorosite „n“ skaičius, jis vis tiek apdoros jį su k. Be to, galite šią problemą suformuluoti fiziškai. Galite sukurti n plieninius rutulius, kurių svoris yra proporcingas skaičiui, kurį norite koduoti, o tai teoriškai būtų galima išspręsti naudojant centrifugą. Tačiau čia naudojamų atomų skaičius yra proporcingas n. Jei standartiniu atveju procesoriuje yra ribotas atomų skaičius.

  • Kitas būdas galvoti apie tai, tarkim, yra mažas procesorius, prijungtas prie kiekvieno numerio, ir kiekvienas procesorius gali bendrauti su kaimynais, visus šiuos numerius galite rūšiuoti į O (log (n)) laiką.

5
11 янв. Atsakymą pateikė ElKamina sausio 11 d. 2017-01-11 10:30 '17 at 10:30 2017-01-11 10:30

Rūšiavimas vis dar yra O (n) bendras laikas. Tai greičiau nei dėl lygiagretinimo .

Centrifugą galite peržiūrėti kaip n atomų, lygiagrečių per n šerdį, spragas (kiekvienas atomas veikia kaip procesorius).

Jūs galite padaryti rūšiavimą greičiau lygiagrečiai, bet tik esant pastoviam faktoriui, nes procesorių skaičius yra ribotas, O (n / C) vis dar yra O (n) (procesoriai paprastai turi <10 branduolių ir grafikos procesorių <6000)

4
11 янв. Atsakymą Siphor pateikė sausio 11 d. 2017-01-11 11:33 '17 at 11:33 2017-01-11 11:33

Centrifuga nesirūšia mazgų, joms taiko jėgą ir tada reaguoja lygiagrečiai su juo. Todėl, jei ketinate įgyvendinti burbulų rūšiavimą, kur kiekvienas mazgas bus lygiagrečiai arba žemyn, remiantis „tankiu“, turėsite įgyvendinti centrifugą.

Turėkite omenyje, kad realiame pasaulyje galite paleisti labai daug lygiagrečių užduočių, kur kompiuteryje gali būti daugiausiai realios lygiagrečios užduotys, lygios fizinių procesorių skaičiui.

Galų gale, jūs taip pat apsiribosite prieigą prie elementų sąrašo, nes jį vienu metu negali pakeisti du mazgai ...

2
11 янв. Atsakymą pateikė Foxtrot Romeo sausio 11 d. 2017-01-11 10:38 '17 at 10:38 2017-01-11 10:38

Visų pirma, jūs lyginate du skirtingus kontekstus: vienas yra logiškas (kompiuterinis), kitas - fizika, kuri (iki šiol) buvo įrodyta, kad galime modeliuoti kai kurias jo dalis matematinėmis formulėmis, o mes, kaip programuotojai, galime ją naudoti fizikos modeliavimo formulės (kai kurios dalys) loginiame darbe (pavyzdžiui, žaidimo variklio fizikos variklis).

Antra, mes turime tam tikras galimybes kompiuteriniame (loginiame) pasaulyje, kuris fizikoje yra beveik neįmanomas, pavyzdžiui, mes galime pasiekti atmintį ir rasti tikslią kiekvieno objekto vietą bet kuriuo metu, bet fizikoje tai didžiulė Heisenbergo neapibrėžties principo problema .

Trečia Jei norite palyginti centrifugas ir jų darbą realiame pasaulyje, kompiuterių pasaulyje atrodo, kad kažkas (Dievas) davė jums superkompiuterį su visomis taikomomis fizikos taisyklėmis, ir jūs darote savo nedidelį rūšiavimą (naudojant centrifugą) ir sakydamas, kad jūsų rūšiavimo problema buvo išspręsta o (n), ignoruojate didžiulį fizinį modeliavimą, vykstantį fone ...

1
12 янв. Atsakymas pateiktas sausio 12 d 2017-01-12 09:16 '17 at 9:16 2017-01-12 09:16

Ar būtų įmanoma, kad kiekvienas mazgas (tam tikra reikšmė ar metodas, pridedamas prie kiekvieno mazgo) būtų „priverstas“ sąrašo tvarka?

Rūšiuojant naudojant kompiuterines programas, mes pasirenkame rūšiuojamų vertybių savybę. Tai paprastai yra skaičiaus arba abėcėlės tvarka.

Kažkas panašaus į centrifugą, kur tik kiekvienas elementas rūpinasi savo santykine padėtimi erdvėje (palyginti su kitais mazgais)

Ši analogija man primena paprastą burbuliukų rūšiavimą. Kuo mažesnis kiekvienos iteracijos burbuliukų skaičius. Kaip ir jūsų centrifugavimo sistema.

Taigi, kad atsakytume į šį klausimą, ar mes darome kažką panašaus programinės įrangos rūšiavime?

1
11 янв. atsakymą pateikė Sudip Bhandari . 2017-01-11 10:14 '17 at 10:14 2017-01-11 10:14

Kita perspektyva yra ta, kad tai, ką apibūdinate naudojant centrifugą, yra panaši į tai, kas vadinama „spageti rūšiavimu“ ( https://en.wikipedia.org/wiki/Spaghetti_sort ). Pasakykite, kad turite skirtingų ilgių žaliavinio spageti >

Jūs galite pastebėti, kad O (pastovus) spageti vienetų skaičiumi, tačiau dėl riboto spageti greičio greičio ilgiausio eilutės ilgyje yra O (n). Taigi nieko nereiškia nemokamai.

0
11 янв. atsakymas pateikiamas eac2222 11 jan. 2017-01-11 23:14 '17 at 11:14 2017-01-11 23:14

Apsvarstykite: „centrifugų rūšiavimas“ iš tikrųjų skalės geriau? Pagalvokite apie tai, kas vyksta skaleojant.

  • Vamzdžiai turi būti ilgesni ir ilgesni.
  • Sunkios medžiagos turi keliauti toliau ir toliau, kad patektų į apačią.
  • Inercijos momentas didėja, todėl reikia didesnės galios ir ilgesnio laiko paspartinti iki rūšiavimo greičio.

Taip pat verta apsvarstyti ir kitus centrifugų rūšiavimo klausimus. Pavyzdžiui, galite dirbti tik siauro dydžio skalėje. Kompiuterių rūšiavimo algoritmas gali apdoroti sveikuosius skaičius nuo 1 iki 2 ^ 1024 ir didesniais, be prakaito. Įdėkite tai, kas sveria 2 ^ 1024 kartus daugiau nei vandenilio atomas centrifugoje, ir, gerai, kad juodoji skylė ir galaktika buvo sunaikintos. Algoritmo klaida.

Žinoma, realus atsakymas čia yra tas, kad skaičiavimo sudėtingumas susijęs su tam tikru skaičiavimo modeliu, kaip minėta kitame atsakyme. Ir „išcentrinis rūšiavimas“ nėra prasmingas bendrų skaičiavimo modelių, pvz., RAM modelio, IO modelio ar daugiakanalių Turingo mašinų kontekste.

0
07 февр. atsakymas, kurį pateikė Craig Gidney 2017-02-07 00:33 '17 - 0:33 2017-02-07 00:33

Kiti klausimai apie žymių arba Užduoti klausimą