Mengurutkan algoritma yang bekerja pada sejumlah besar data

Saya mencari algoritma pengurutan yang dapat bekerja pada sejumlah besar data, yaitu yang dapat bekerja bahkan ketika seluruh kumpulan data tidak dapat disimpan dalam memori utama sekaligus.

Satu-satunya kandidat yang saya temukan sampai sekarang adalah penggabungan: Anda dapat mengimplementasikan algoritma sedemikian rupa sehingga memindai kumpulan data Anda di setiap penggabungan tanpa memegang semua data di memori utama sekaligus. Variasi jenis penggabungan yang ada dalam pikiran saya dijelaskan dalam artikel ini di bagian Penggunaan dengan tape drive .

Saya pikir ini adalah solusi yang baik (dengan kompleksitas O (nx log (n)) tetapi saya ingin tahu apakah ada algoritma pengurutan lainnya (mungkin lebih cepat) yang dapat bekerja pada set data besar yang tidak sesuai dengan memori utama.

EDIT

Berikut ini beberapa perincian lebih lanjut, sebagaimana disyaratkan oleh jawaban:

• Data perlu disortir secara berkala, misalnya sebulan sekali. Saya tidak perlu memasukkan beberapa catatan dan data diurutkan secara bertahap.
• Contoh file teks saya adalah sekitar 1 GB UTF-8 teks, tetapi saya ingin menyelesaikan masalah secara umum, bahkan jika file tersebut, katakanlah, 20 GB.
• Itu tidak dalam database dan, karena kendala lain, itu tidak bisa.
• Data dibuang oleh orang lain sebagai file teks, saya punya kode sendiri untuk membaca file teks ini.
• Format data adalah file teks: karakter baris baru adalah pemisah rekaman.

Satu kemungkinan peningkatan yang saya pikirkan adalah untuk membagi file menjadi file yang cukup kecil untuk diurutkan dalam memori, dan akhirnya menggabungkan semua file ini menggunakan algoritma yang saya jelaskan di atas.

Referensi kanonik tentang penyortiran dan pencarian adalah Knuth, Vol. 3 . Mulai dari sana.

Buku ini awalnya ditulis kembali ketika komputer jauh lebih kecil dan lebih lambat dari yang ada sekarang, yang membuat teknik pemilahan memori lebih penting daripada yang dirasakan saat ini.

Penggabungan R-Way eksternal seperti pada sortperintah UNIX adalah alternatif yang baik. Dari formulasi Anda, saya tidak yakin apakah itu algoritma yang Anda maksud dengan "semacam penggabungan", dan jika Anda tidak mengetahuinya, lihatlah.

Tanpa lebih spesifik "Gabungkan Urutan" mungkin jawaban terbaik yang akan Anda dapatkan, namun Anda dapat menerapkan sesuatu yang jauh lebih pintar tergantung pada kebutuhan Anda.

Misalnya, dapatkah Anda cukup membuat indeks dalam-memori file kemudian menyalin semua nilai sekaligus, menyimpan lokasi berbagai nilai kunci? Apakah 1/2 pas di memori sekaligus, atau 1/1000000? Jika itu yang kedua maka Anda mungkin tidak dapat memasukkan indeks dalam memori, jika yang pertama maka Anda bisa mengurutkan kedua bagian dengan lebih efisien kemudian menggabungkannya bersama dalam satu langkah terakhir.

Sial, karena Anda tidak menentukan itu mungkin bahwa data Anda semuanya ada dalam database, jika demikian Anda bisa membuat tabel indeks dan menyebutnya baik (saya kira ini bukan masalahnya, tetapi hanya menunjukkan bahwa situasi Anda sangat penting untuk menyelesaikan masalah rumit seperti ini).

Jika Anda ingin melakukannya sekali saja dan sedang mencari peretasan yang sangat cepat, kedengarannya seperti penggabungan eksternal itu akan menjadi awal yang baik jika Anda menjalankan unix (karena tampaknya sudah terpasang di dalamnya)

Jika Anda harus menyimpannya secara berurutan dan selalu menambahkan catatan tunggal, maka jenis penyisipan akan diperlukan (Menambahkan catatan tunggal ke data yang diurutkan selalu merupakan jenis penyisipan).

Bisakah Anda mengontrol kode yang "Membaca" data? Jika demikian maka banyak bentuk pengindeksan (daripada menyortir dengan memindahkan data di sekitar disk) akan membantu BANYAK (sebenarnya akan menjadi persyaratan mutlak).

Begitu:

• Di tempat atau beberapa file?
• Suatu kali, berkala atau tetap disortir setiap saat?
• Berapa jauh lebih besar dari memori (Berapa banyak memori-beban untuk melewati seluruh kumpulan data)?
• Apakah itu dalam database? Bisakah?
• Apakah Anda mengontrol kode yang membaca data, atau akankah orang lain membuang file secara langsung?
• Format file? (Teks? Catatan tetap?)
• Adakah kondisi khusus lain yang tidak saya tanyakan?

Jika Anda benar-benar menginginkan solusi yang skalabel, Anda harus melihat TeraSort, implementasi pengurutan standar dengan pengurangan peta; lebih detail tentang StackOverflow .

Anda mungkin tertarik dengan jenis ember . Kinerja kasus rata-rata adalah waktu linier.

= O (n + d) n: jumlah elemen dan d = panjang angka terbesar jika Anda memiliki intuisi tentang data Anda yaitu. Jika Anda tahu berapa banyak 'digit' panjang adalah angka terbesar Anda. Jadi jika Anda memiliki 2 juta angka 6 digit => 0 (n) maka linear.

Gunakan algoritme penggabungan eksternal (jika data Anda adalah kontinu), atau jenis ember dengan penghitungan jenis sebagai implementasi penyortiran untuk kotak (jika data Anda terpisah dan terdistribusi secara merata).

Mungkin pendekatan terbaik adalah membangun file indeks / pemetaan Anda sendiri jika kenaikannya kecil.

1. Entah bagaimana memesan "database" Anda
2. Tetapkan integer untuk setiap entri (1, 2, 3, 4, ..., n) (lebih baik: gunakan beberapa indeks jarang)
3. Saat menambahkan selisih hanya temukan celah di mana angka kiri kurang atau sama dan angka kanan lebih besar atau sama (itu seharusnya tidak sulit dengan beberapa versi yang dimodifikasi dari pencarian biner)
4. Masukkan, sementara celahnya cukup besar, jika tidak: cukup masukkan kembali (jangan pernah urutkan lagi) :-)

Saya baru saja membangun beberapa struktur abstrak yang disebut antrian besar dan array besar untuk menyederhanakan tugas penyortiran dan pencarian data besar pada satu mesin dengan memori terbatas. Pada dasarnya, algoritma yang digunakan mirip dengan yang Anda sebutkan di atas - jenis gabungan eksternal.

Saya dapat mengurutkan data 128GB (setiap item 100 byte) dalam 9 jam pada satu mesin, dan kemudian biner mencari data yang diurutkan dengan hampir tidak ada waktu.

Berikut adalah posting tentang cara mencari data besar dengan menggunakan open source big queue dan struktur array besar.