Sortir konten file teks yang sangat besar (800GB) pada Windows

Saya memiliki file teks dengan kata di setiap baris, ukuran file adalah 800GB. Saya perlu mengurutkan kata-kata berdasarkan abjad.

Saya telah mencoba menggunakan program pengurutan Windows menggunakan:

sort.exe input.txt /o output.txt

yang memberikan kesalahan: Memori utama tidak cukup untuk menyelesaikan penyortiran.

Saya memiliki 32GB RAM, jadi ketika saya mencoba menentukan memori 10GB untuk jenis menggunakan:

sort.exe input.txt /o output.txt /M 10000000

Saya mendapat:

Peringatan: ukuran memori yang ditentukan dikurangi menjadi memori halaman yang tersedia.

Catatan input melebihi panjang maksimum. Tentukan maksimum yang lebih besar.

Apa saja pilihan saya?

Apa saja pilihan saya?

Coba Freeware Command Line Sort Utility CMSort .

Ini menggunakan beberapa file sementara dan kemudian menggabungkannya di akhir.

CMsort membaca catatan file input hingga memori yang disesuaikan tercapai. Kemudian catatan diurutkan dan ditulis ke file sementara. Ini akan diulang sampai semua catatan diproses. Akhirnya, semua file sementara digabungkan ke dalam file output. Jika memori yang tersedia cukup, tidak ada file sementara yang ditulis dan tidak diperlukan penggabungan.

Satu pengguna melaporkan itu mengurutkan file 130.000.000 byte.

Jika Anda ingin mengubah beberapa kode sendiri, ada juga Menyortir File Teks Besar - CodeProject - "Algoritma pengurutan garis dalam ukuran file teks yang melebihi memori yang tersedia"

Satu opsi lain adalah memuat file ke dalam Database. EG MySQL dan MySQL Workbench.
Database adalah kandidat yang sempurna untuk bekerja dengan file besar

Jika file input Anda hanya berisi kata-kata yang dipisahkan oleh baris baru, ini tidak akan sulit.

Setelah Anda menginstal database dan MySQL Workbench, inilah yang perlu Anda lakukan.
Pertama buat skema (ini mengasumsikan kata-kata tidak akan lebih dari 255 karakter meskipun Anda dapat mengubah ini dengan meningkatkan nilai argumen). Kolom pertama "idwords" adalah kunci utama.

CREATE SCHEMA `tmp` ;

CREATE TABLE `tmp`.`words` (
  `idwords` INT NOT NULL AUTO_INCREMENT,
  `mywords` VARCHAR(255) NULL,
  PRIMARY KEY (`idwords`));

Kedua mengimpor data: EG Ini akan mengimpor semua kata ke dalam tabel (langkah ini mungkin memakan waktu beberapa saat untuk menyelesaikan. Saran saya adalah untuk menjalankan tes dengan file kata-kata kecil terlebih dahulu dan setelah Anda yakin formatnya sama dengan yang lebih besar (memotong tabel .. IE Bersihkan dan muat kumpulan data lengkap).

LOAD DATA LOCAL INFILE "C:\\words.txt" INTO TABLE tmp.words
LINES TERMINATED BY '\r\n'
(mywords);

Tautan ini dapat membantu mendapatkan format yang tepat untuk memuat. https://dev.mysql.com/doc/refman/5.7/en/load-data.html
EG Jika Anda perlu melewati baris pertama Anda akan melakukan hal berikut.

LOAD DATA LOCAL INFILE "H:\\words.txt" INTO TABLE tmp.words
-- FIELDS TERMINATED BY ','
LINES TERMINATED BY '\r\n'
IGNORE 1 LINES
(mywords);

Akhirnya Simpan file yang diurutkan. Ini mungkin memakan waktu cukup lama juga tergantung pada komputer Anda.

SELECT tmp.words.mywords
FROM tmp.words
order by tmp.words.mywords asc
INTO OUTFILE 'C:\\sorted_words.csv';

Anda juga dapat mencari data sesuka Anda. EG Ini akan memberi Anda 50 kata pertama dalam urutan menaik (mulai dari 0 atau kata pertama).

SELECT tmp.words.mywords
FROM tmp.words
order by tmp.words.mywords asc
LIMIT 0, 50 ;

Semoga beruntung
Pete

sort

Ada banyak algoritma yang digunakan untuk mengurutkan file yang dipesan dan yang tidak diurutkan ^{[ 1 ]} .
Karena semua algoritme sudah diterapkan, pilih program yang sudah diuji.

Dalam coreutils (dari Linux tetapi juga tersedia untuk windows ^{[ 2 ]} ), ada sortperintah yang mampu berjalan secara paralel di bawah prosesor multi-core: biasanya itu sudah cukup.

Jika file Anda sangat besar, Anda dapat membantu pemrosesan splitting ( split -l), file dalam beberapa chunks, mungkin menggunakan opsi paralel ( --parallel), dan mengurutkan chunks yang dipesan dengan -mopsi ( merge sort ).
Salah satu dari banyak cara untuk melakukannya dijelaskan di sini (membagi file, memesan satu potongan, menggabungkan potongan yang dipesan, menghapus file temp).

Catatan:

• Di windows 10 ada yang disebut Windows Subsystem untuk Linux di mana semua contoh Linux akan tampak lebih alami.
• Pengurutan dengan algoritma yang berbeda memiliki waktu eksekusi yang berbeda yang skala sebagai fungsi dari jumlah entri data yang akan diurutkan (O (n ^m ), O (nlogn) ...).
• Efisiensi algoritma tergantung pada urutan yang sudah ada dalam file asli.
  (Misalnya semacam gelembung adalah algoritma paling cepat untuk file yang sudah dipesan - tepatnya N -, tetapi tidak efisien dalam kasus lain).

Untuk menawarkan solusi alternatif untuk Peter H, ada program q yang memungkinkan perintah gaya SQL terhadap file teks. Perintah di bawah ini akan melakukan hal yang sama (dijalankan dari command prompt di direktori yang sama dengan file), tanpa perlu menginstal SQL Workbench atau membuat tabel.

q "select * from words.txt order by c1"

c1 adalah singkatan untuk kolom 1.

Anda dapat mengecualikan kata duplikat dengan

q "select distinct c1 from words.txt order by c1"

dan mengirim output ke file lain

q "select distinct c1 from words.txt order by c1" > sorted.txt

Jika kata-kata pada setiap baris berasal dari kosakata terbatas (seperti bahasa Inggris) maka Anda dapat mengurutkan daftar dalam waktu O (n + m log m) menggunakan TreeMap dan mencatat jumlah (di mana m adalah jumlah nilai unik).

Kalau tidak, Anda bisa menggunakan big-sorter perpustakaan java . Ini membagi input untuk mengurutkan file menengah dan menggabungkannya secara efisien (keseluruhan O (nlogn)). Untuk mengurutkan file Anda terlihat seperti ini:

Sorter.serializerTextUtf8()
      .input(inputFile)
      .output(outputFile)
      .loggerStdOut() // display some progress
      .sort();

Saya membuat file 1.7GB (100m baris) dengan 16 kata karakter yang dihasilkan secara acak dan mengurutkannya seperti di atas pada tahun 142-an dan berdasarkan pada kompleksitas komputasi O (n log n) yang saya gunakan, saya memperkirakan 800GB kata-kata 16 karakter akan butuh sekitar 24 jam untuk mengurutkan single-threaded di laptop i5 2.3GHz saya dengan SSD.