Saya berpikir tentang menyortir algoritme dalam perangkat lunak, dan cara yang mungkin dilakukan seseorang untuk mengatasi O(nlogn)hambatan tersebut. Menurut saya tidak mungkin untuk mengurutkan lebih cepat dalam arti praktis, jadi tolong jangan berpikir saya melakukannya.

Dengan demikian, tampaknya dengan hampir semua algoritma pengurutan, perangkat lunak harus mengetahui posisi setiap elemen. Mana yang masuk akal, jika tidak, bagaimana cara mengetahui di mana menempatkan setiap elemen menurut beberapa kriteria penyortiran?

Tetapi ketika saya menyilangkan pemikiran ini dengan dunia nyata, sentrifus tidak tahu di mana posisi setiap molekul ketika ia 'menyortir' molekul berdasarkan kepadatan. Faktanya, ia tidak peduli dengan posisi setiap molekul. Namun ia dapat memilah triliunan demi triliunan benda dalam waktu yang relatif singkat, karena fakta bahwa setiap molekul mengikuti hukum kerapatan dan gravitasi - yang membuat saya berpikir.

Apakah mungkin dengan beberapa overhead pada setiap node (beberapa nilai atau metode ditempelkan pada setiap node) untuk 'memaksa' urutan daftar? Sesuatu seperti centrifuge, di mana hanya setiap elemen yang peduli tentang posisi relatifnya di ruang angkasa (dalam kaitannya dengan node lain). Atau, apakah ini melanggar beberapa aturan dalam perhitungan?

Saya pikir salah satu poin besar yang diangkat di sini adalah efek mekanis kuantum dari alam dan bagaimana efek tersebut berlaku secara paralel pada semua partikel secara bersamaan.

Mungkin komputer klasik secara inheren membatasi penyortiran ke domain O(nlogn), di mana komputer kuantum mungkin dapat melewati ambang itu ke dalam O(logn)algoritma yang bertindak secara paralel.

Poin bahwa centrifuge pada dasarnya adalah jenis gelembung paralel tampaknya benar, yang memiliki kompleksitas waktu O(n).

Saya kira pemikiran berikutnya adalah jika alam dapat memilah O(n), mengapa komputer tidak bisa?

EDIT: Saya telah salah memahami mekanisme centrifuge dan tampaknya itu melakukan perbandingan, yang sangat paralel pada saat itu. Namun ada proses fisik yang beroperasi pada properti entitas yang sedang diurutkan daripada membandingkan dua properti. Jawaban ini mencakup algoritme yang bersifat seperti itu.

Sentrifugal menerapkan mekanisme penyortiran yang tidak benar-benar bekerja dengan cara perbandingan antar elemen, tetapi sebenarnya dengan properti ('gaya sentrifugal') pada masing-masing elemen dalam isolasi. Beberapa algoritma pengurutan termasuk dalam tema ini, terutama Radix Sort . Saat algoritme pengurutan ini diparalelkan, algoritme tersebut harus mendekati contoh sentrifuse.

Beberapa algoritme pengurutan non-komparatif lainnya adalah Jenis Bucket dan Jenis Penghitungan . Anda mungkin menemukan bahwa jenis Bucket juga cocok dengan gagasan umum sentrifus (jari-jarinya dapat berhubungan dengan sebuah bin).

Apa yang disebut 'algoritma pengurutan' di mana setiap elemen dianggap dalam isolasi adalah Jenis Tidur . Di sini, waktu, bukan gaya sentrifugal, bertindak sebagai besaran yang digunakan untuk menyortir.

Kompleksitas komputasi selalu ditentukan sehubungan dengan beberapa model komputasi. Misalnya, algoritme yang O ( n ) pada komputer biasa mungkin menjadi O (2 ⁿ ) jika diterapkan di Brainfuck .

Model komputasi centrifuge memiliki beberapa sifat yang menarik; sebagai contoh:

• itu mendukung paralelisme sewenang-wenang; tidak peduli berapa banyak partikel di dalam larutan, semuanya dapat disortir secara bersamaan.
• ia tidak memberikan jenis partikel linier yang ketat berdasarkan massa, melainkan perkiraan yang sangat dekat (energi rendah).
• tidak mungkin untuk memeriksa partikel individu dalam hasil.
• tidak mungkin mengurutkan partikel berdasarkan properti yang berbeda; hanya massa yang didukung.

Mengingat bahwa kami tidak memiliki kemampuan untuk mengimplementasikan sesuatu seperti ini pada perangkat keras komputasi tujuan umum, model tersebut mungkin tidak memiliki relevansi praktis; tetapi masih layak untuk diteliti, untuk melihat apakah ada yang bisa dipelajari darinya. Algoritme nondeterministik dan algoritme kuantum keduanya telah menjadi area penelitian aktif, misalnya, meskipun keduanya tidak dapat diterapkan saat ini.

Triknya ada di sana, bahwa Anda hanya memiliki kemungkinan untuk mengurutkan daftar Anda menggunakan sentrifuse. Seperti jenis dunia nyata lainnya [rujukan?], Anda dapat mengubah probabilitas bahwa Anda telah menyortir daftar Anda, tetapi tidak pernah memastikan tanpa memeriksa semua nilai (atom).

Pertimbangkan pertanyaan: "Berapa lama Anda harus menjalankan centrifuge?"
Jika Anda hanya menjalankannya selama picosecond, sampel Anda mungkin kurang diurutkan dari status awal .. atau jika Anda menjalankannya selama beberapa hari, sampel Anda mungkin akan tersortir sepenuhnya. Namun, Anda tidak akan tahu tanpa benar-benar memeriksa isinya.

Contoh dunia nyata dari "pemesanan" berbasis komputer adalah drone otonom yang bekerja sama secara kooperatif, yang dikenal sebagai "kawanan drone". Drone bertindak dan berkomunikasi baik sebagai individu maupun sebagai kelompok, dan dapat melacak banyak target. Drone secara kolektif memutuskan drone mana yang akan mengikuti target mana dan kebutuhan yang jelas untuk menghindari tabrakan antar drone. Versi awalnya adalah drone yang bergerak melalui titik jalan sambil tetap dalam formasi, tetapi formasi bisa berubah.

Untuk "semacam", drone dapat diprogram untuk membentuk garis atau pola dalam urutan tertentu, awalnya dirilis dalam permutasi atau bentuk apa pun, dan secara kolektif dan paralel mereka akan dengan cepat membentuk garis atau pola yang dipesan.

Kembali ke jenis berbasis komputer, satu masalah adalah bahwa ada satu bus memori utama, dan tidak ada cara bagi sejumlah besar objek untuk bergerak dalam memori secara paralel.

ketahui posisi setiap elemen

Dalam kasus tape sort, posisi setiap elemen (record) hanya "diketahui" oleh "tape", bukan ke komputer. Pengurutan berbasis pita hanya perlu bekerja dengan dua elemen sekaligus, dan cara untuk menunjukkan batas run pada pita (tanda file, atau catatan dengan ukuran berbeda).

IMHO, orang terlalu memikirkan log (n). O (nlog (n)) praktis O (n). Dan Anda membutuhkan O (n) hanya untuk membaca data.

Banyak algoritme seperti quicksort menyediakan cara yang sangat cepat untuk mengurutkan elemen. Anda dapat menerapkan variasi quicksort yang akan sangat cepat dalam praktiknya.

Secara inheren semua sistem fisik paralel tanpa batas. Anda mungkin memiliki muatan atom dalam sebutir pasir, alam memiliki daya komputasi yang cukup untuk mencari tahu di mana seharusnya setiap elektron di setiap atom. Jadi jika Anda memiliki cukup sumber daya komputasi (O (n) prosesor), Anda dapat mengurutkan n angka dalam waktu log (n).

Dari komentar:

1. Mengingat prosesor fisik yang memiliki k jumlah elemen, itu dapat mencapai paling banyak O (k). Jika Anda memproses n angka secara sewenang-wenang, ia masih akan memprosesnya dengan kecepatan yang terkait dengan k. Juga, Anda bisa merumuskan masalah ini secara fisik. Anda dapat membuat n bola baja dengan berat yang sebanding dengan jumlah yang ingin Anda encode, yang dapat diselesaikan dengan sentrifuse dalam teori. Tetapi di sini jumlah atom yang Anda gunakan sebanding dengan n. Sedangkan dalam kasus standar Anda memiliki sejumlah atom dalam sebuah prosesor.

2. Cara lain untuk memikirkan hal ini adalah, katakanlah Anda memiliki prosesor kecil yang terpasang pada setiap nomor dan setiap prosesor dapat berkomunikasi dengan tetangganya, Anda dapat mengurutkan semua angka tersebut dalam waktu O (log (n)).

Saya bekerja di kantor musim panas setelah sekolah menengah ketika saya mulai kuliah. Saya pernah belajar di AP Computer Science antara lain sorting dan search .

Saya menerapkan pengetahuan ini dalam beberapa sistem fisik yang dapat saya ingat:

Sortir penggabungan alami untuk memulai…

Formulir multi-bagian yang dicetak sistem termasuk sobekan seukuran kartu file, yang perlu dimasukkan ke dalam laci.

Saya mulai dengan setumpuk dan memilah tumpukan untuk memulai. Langkah pertama adalah mengambil 5 atau lebih, cukup sedikit untuk ditempatkan dengan mudah di tangan Anda. Tempatkan paket yang sudah disortir ke bawah, saling silang setiap tumpukan agar tetap terpisah.

Kemudian, gabungkan setiap pasang tumpukan, menghasilkan tumpukan yang lebih besar. Ulangi sampai hanya ada satu tumpukan.

… Urutan penyisipan selesai

Lebih mudah untuk mengarsipkan kartu yang sudah diurutkan, karena setiap kartu berikutnya berada sedikit lebih jauh ke laci terbuka yang sama.

Jenis radix

Yang ini tidak ada orang lain yang mengerti bagaimana saya melakukannya dengan begitu cepat, meskipun berulang kali mencoba untuk mengajarkannya.

Sebuah kotak besar berisi tanda centang (seukuran kartu berlubang) perlu disortir. Sepertinya bermain solitaire di atas meja besar — ​​bagikan, susun, ulangi.

Secara umum

30 tahun yang lalu, saya memperhatikan apa yang Anda tanyakan: gagasan ditransfer ke sistem fisik secara langsung karena ada biaya relatif dari perbandingan dan menangani catatan , dan tingkat penyimpanan dalam cache.

Melampaui padanan yang dipahami dengan baik

Saya ingat sebuah esai tentang topik Anda, dan itu membahas jenis spageti . Anda memotong panjang mie kering untuk menunjukkan nilai kuncinya, dan memberi label dengan ID catatan. Ini adalah O (n), cukup memproses setiap item satu kali.

Kemudian Anda mengambil bungkusan itu dan mengetuk salah satu ujungnya di atas meja. Mereka sejajar di tepi bawah, dan sekarang sudah diurutkan. Anda dapat dengan mudah melepas yang terpanjang, dan mengulanginya. Pembacaannya juga O (n).

Ada dua hal yang terjadi di sini di "dunia nyata" yang tidak sesuai dengan algoritme. Pertama, menyelaraskan tepinya adalah operasi paralel. Setiap item data juga merupakan prosesor (hukum fisika berlaku untuk itu). Jadi, secara umum, Anda menskalakan pemrosesan yang tersedia dengan n, yang pada dasarnya membagi kompleksitas klasik Anda dengan faktor pada n.

Kedua, bagaimana menyelaraskan tepinya mencapai semacam? Penyortiran nyata dalam membaca-out yang memungkinkan Anda menemukan terpanjang dalam satu langkah, meskipun Anda tidak membandingkan semua dari mereka untuk menemukan terpanjang. Sekali lagi, bagi dengan faktor n, jadi mencari yang terbesar sekarang adalah O (1).

Contoh lain adalah menggunakan komputasi analog: model fisik memecahkan masalah "secara instan" dan pekerjaan persiapannya adalah O (n). Pada prinsipnya komputasi adalah penskalaan dengan jumlah komponen yang berinteraksi, bukan jumlah item yang disiapkan. Jadi skala komputasi dengan n². Contoh yang saya pikirkan adalah komputasi multi-faktor berbobot, yang dilakukan dengan mengebor lubang di peta, menggantung bobot dari string yang melewati lubang, dan mengumpulkan semua string di atas cincin.

Penyortiran masih O (n) total waktu. Itu lebih cepat dari itu karena Paralelisasi .

Anda dapat melihat sentrifugal sebagai sekumpulan atom n, diparalelkan di atas n inti (setiap atom bertindak sebagai prosesor).

Anda dapat membuat penyortiran lebih cepat dengan paralelisasi tetapi hanya dengan faktor konstan karena jumlah prosesor terbatas, O (n / C) masih O (n) (CPU biasanya memiliki <10 core dan GPU <6000)

Centrifuge tidak menyortir node, itu menerapkan gaya ke mereka kemudian mereka bereaksi secara paralel dengannya. Jadi, jika Anda menerapkan semacam gelembung di mana setiap node bergerak sendiri secara paralel ke atas atau ke bawah berdasarkan "kepadatan", Anda akan memiliki penerapan sentrifugal.

Ingatlah bahwa di dunia nyata Anda dapat menjalankan sejumlah besar tugas paralel di mana di komputer Anda dapat memiliki maksimum tugas paralel nyata yang sama dengan jumlah unit pemrosesan fisik.

Pada akhirnya, Anda juga akan dibatasi dengan akses ke daftar elemen karena tidak dapat dimodifikasi secara bersamaan oleh dua node ...

Apakah mungkin dengan beberapa overhead pada setiap node (beberapa nilai atau metode ditempelkan ke masing-masing node) untuk 'memaksa' urutan daftar?

Saat kami mengurutkan menggunakan program komputer, kami memilih properti dari nilai yang sedang diurutkan. Itu biasanya besaran angka atau urutan abjad.

Sesuatu seperti centrifuge, di mana hanya setiap elemen yang peduli tentang posisi relatifnya di ruang angkasa (dalam kaitannya dengan node lain)

Analogi ini dengan tepat mengingatkan saya pada jenis gelembung sederhana. Betapa kecilnya angka yang menggelembung di setiap iterasi. Seperti logika sentrifugasi Anda.

Jadi untuk menjawab ini, bukankah kita sebenarnya melakukan hal semacam itu dalam pengurutan berbasis perangkat lunak?

Pertama-tama, Anda membandingkan dua konteks yang berbeda, satu logika (komputer) dan yang lainnya adalah fisika yang (sejauh ini) terbukti bahwa kita dapat memodelkan beberapa bagiannya menggunakan rumus matematika dan kita sebagai programmer dapat menggunakan rumus ini untuk mensimulasikan (beberapa bagian) fisika dalam kerja logika (misalnya mesin fisika dalam mesin permainan).

Kedua Kami memiliki beberapa kemungkinan di dunia komputer (logika) yang hampir tidak mungkin dalam fisika misalnya kita dapat mengakses memori dan menemukan lokasi yang tepat dari setiap entitas setiap saat tetapi dalam fisika itu adalah masalah besar prinsip ketidakpastian Heisenberg .

Ketiga Jika Anda ingin memetakan sentrifugal dan operasinya di dunia nyata, ke dunia komputer, itu seperti seseorang (Tuhan) telah memberi Anda komputer super dengan semua aturan fisika yang diterapkan dan Anda melakukan pemilahan kecil di dalamnya ( menggunakan centrifuge) dan dengan mengatakan bahwa masalah pengurutan Anda diselesaikan dalam o (n) Anda mengabaikan simulasi fisika besar yang terjadi di latar belakang ...

Perspektif lain adalah bahwa apa yang Anda gambarkan dengan sentrifus sama dengan apa yang disebut "jenis spaghetti" ( https://en.wikipedia.org/wiki/Spaghetti_sort ). Katakanlah Anda memiliki sekotak batang spaghetti mentah dengan panjang yang bervariasi. Pegang di kepalan tangan Anda, dan kendurkan tangan Anda untuk menurunkannya secara vertikal sehingga semua ujungnya berada di atas meja horizontal. Ledakan! Mereka diurutkan berdasarkan tinggi. O (waktu konstan). (Atau O (n) jika Anda termasuk memetik batang berdasarkan ketinggian dan memasukkannya ke dalam ... rak spageti, saya rasa?)

Anda dapat mencatat di sana bahwa itu adalah O (konstan) dalam jumlah potongan spageti, tetapi, karena kecepatan suara yang terbatas dalam spageti, itu adalah O (n) untuk untai terpanjang. Jadi tidak ada yang gratis.

Pertimbangkan: apakah "jenis sentrifugal" benar-benar menskalakan lebih baik? Pikirkan tentang apa yang terjadi saat Anda meningkatkan skala.

• Tabung reaksi harus semakin panjang.
• Benda-benda berat harus menempuh perjalanan semakin jauh untuk sampai ke dasar.
• Momen inersia meningkat, membutuhkan lebih banyak tenaga dan waktu lebih lama untuk mempercepat hingga kecepatan penyortiran.

Perlu juga dipertimbangkan masalah lain dengan jenis centrifuge. Misalnya, Anda hanya dapat beroperasi pada skala ukuran yang sempit. Algoritme penyortiran komputer dapat menangani bilangan bulat dari 1 hingga 2 ^ 1024 dan seterusnya, tanpa masalah. Masukkan sesuatu yang beratnya 2 ^ 1024 kali lebih besar dari atom hidrogen ke dalam mesin pemisah dan, yah, itu adalah lubang hitam dan galaksi telah dihancurkan. Algoritme gagal.

Tentu saja jawaban sebenarnya di sini adalah bahwa kompleksitas komputasi relatif terhadap beberapa model komputasi, seperti yang disebutkan dalam jawaban lain. Dan "jenis sentrifugal" tidak masuk akal dalam konteks model komputasi umum, seperti model RAM atau model IO atau mesin Turing multitape.