Khas untuk
Mari kita mulakan
Pada tahap 18, tugas pertama membaca fail bait demi bait bermula: baca fail, kemudian cari bait minimum/maksimum atau keluarkannya dalam bentuk tersusun, dsb.
Orang-orang di sini sangat bijak. Mereka tahu tentang koleksi dan mereka boleh mengisih dan memasukkan. Koleksi adalah mekanisme yang berkuasa. Dan ramai yang tidak menggunakannya sama sekali sebelum JavaRush. Sudah tentu, adalah terpuji untuk mempelajarinya dan cuba memukulnya di tempat yang salah. Jadi. Mari kita ambil masalah yang tidak ada dalam tugas (supaya tidak ada spoiler apabila menyelesaikannya), tetapi ada yang sangat serupa:
- Masukkan nama fail daripada konsol
- Baca semua bait daripada fail.
- Mengabaikan ulangan, susun mengikut kod byte dalam susunan menurun.
- Paparan
- Tutup strim I/O
Contoh bait fail input
44 83 44 Contoh output
83 44 Kami juga memperkenalkan pembolehubah
startTime
dan
finishTime
untuk merekodkan masa pelaksanaan program. Untuk pengiraan saya menggunakan
i3-3GHz/8Gb RAM/HDD WD Blue-1Tb/Win7-64/jdk-8u73-windows-x64 (contoh program dalam pilihan 1-2 diambil dari forum info.javarush, ia sedikit diubah suai hanya untuk mengisih dalam tertib menaik okey - iaitu, ia adalah NYATA!!)
Mari kita selesaikan secara langsung:
public class Solution {
public static void main(String[] args) throws Exception {
FileInputStream inputStream = new FileInputStream(new BufferedReader(new InputStreamReader(System.in)).readLine());
long startTime = System.currentTimeMillis();
ArrayList<Integer> listData = new ArrayList<Integer>();
while (inputStream.available() > 0) listData.add(inputStream.read());
inputStream.close();
ArrayList<Integer> result = new ArrayList<Integer>(new HashSet<Integer>(listData));
Collections.sort(result);
while (!result.isEmpty()) {
System.out.print(result.get(result.size()-1) + " ");
result.remove(result.get(result.size()-1));
}
long finishTime = System.currentTimeMillis();
System.out.println("\nвремя работы=" + (finishTime-startTime) + "ms.");
}
}
Menyelesaikan segala-galanya hebat! Ujian (kalau ada, pasti lulus dengan hebat). Tetapi dalam kehidupan terdapat beberapa fail yang hanya mengandungi baris "Ibu mencuci bingkai." Mari beri program kami fail 46MB (mengikut piawaian hari ini, nampaknya tidak begitu banyak). Apa itu, program ini berjalan selama 220 saat. Percubaan untuk menyuap fail 1Gb pada waktu petang (saiz filem MPEG4 bukan kualiti terbaik) tidak berjaya. Saya masih membaca program pada waktu pagi - dan saya terpaksa pergi bekerja sudah. Apa masalahnya? Mungkin sedang digunakan
ArrayList<Integer>
yang mempunyai 1 bilion elemen di dalamnya. Setiap elemen daripadanya mengambil sekurang-kurangnya 16 bait (Kepala: 8 bait + Medan int: 4 bait + Penjajaran untuk berbilang 8: 4 bait). Secara keseluruhan, kami secara sukarela memasukkan 16 Gb data ke dalam memori dengan saiz RAM 8. Kami akan melakukan yang lebih baik. Mari selami lebih dalam koleksi. Dan hore, kami dapati apa yang kami perlukan.
Temui TreeSet
Ini banyak:
- tidak membenarkan menyimpan dua elemen yang sama (yang bermaksud kita akan menyimpan kesemua 255 elemen dalam ingatan, bukannya satu bilion!)
- apabila memanipulasi unsur-unsurnya, ia secara automatik mengatur (menyisih sendiri - inilah, ketinggian kesempurnaan!)
Kita mendapatkan:
public class Solution {
public static void main(String[] args) throws Exception {
FileInputStream inputStream = new FileInputStream(new BufferedReader(new InputStreamReader(System.in)).readLine());
byte[] arrBytes = new byte[256];
long startTime = System.currentTimeMillis();
SortedSet<Integer> list = new TreeSet<Integer>();
while(inputStream.available()>0) list.add(inputStream.read());
inputStream.close();
while (!list.isEmpty()) {
System.out.print(list.last() + " ");
list.remove(list.last());
}
long finishTime = System.currentTimeMillis();
System.out.println("\nвремя работы=" + (finishTime-startTime) + "ms.");
}
}
Outputnya ialah: fail 46MB, 176 saat. Fail 1Gb - 3 jam 5 minit. Kemajuan adalah jelas. Kami dapat "menunggu" untuk keputusan, dan fail 46MB diproses dengan ketara lebih cepat. Teruskan. Mari kita cuba
meninggalkan koleksi (ini akan menjadi sangat menyakitkan bagi sesetengah orang). Kami akan menggunakan tatasusunan mudah (ia sangat primitif). Mari kita perhatikan satu
perkara penting . Bilangan bait yang ditemui boleh dimasukkan ke dalam tatasusunan dengan panjang 256. Jadi kita hanya akan menambah elemen tatasusunan yang sepadan dengan bait dibaca dengan satu.
Tatasusunan - bait demi bait
public class Solution {
public static void main(String[] args) throws Exception {
FileInputStream inputStream = new FileInputStream(new BufferedReader(new InputStreamReader(System.in)).readLine());
long[] arrBytes = new long[256];
long startTime = System.currentTimeMillis();
while (inputStream.available() > 0) arrBytes[inputStream.read()]++;
inputStream.close();
for (long i = 255; i >= 0 ; i--)
if (arrBytes[(int) i] > 0) System.out.print(i + " ");
long finishTime = System.currentTimeMillis();
System.out.println("\nвремя работы=" + (finishTime-startTime) + "ms.");
}
}
Outputnya ialah: fail 46MB, 158 saat. Fail 1Gb - 2 jam 55 minit. Sekali lagi peningkatan, tetapi kecil. Dan kami melakukan segala-galanya dengan alat mudah.
Tidak menggunakan mikroskop untuk memandu paku .
Sekarang penyimpangan lirik. Mari kita ingat struktur komputer.
Memori RAM (DRAM) , di mana program biasanya dilaksanakan dan pembolehubah disimpan, mempunyai kelajuan akses yang tinggi, tetapi bersaiz kecil.
Memori pada pemacu keras/denyar (pemacu HDD atau Flash) di mana fail biasanya disimpan, sebaliknya, mempunyai kelajuan akses yang rendah tetapi bersaiz besar. Oleh itu, apabila kami membaca bait demi bait fail 1Gb (iaitu, kami mengakses HDD satu bilion kali), kami menghabiskan banyak masa bekerja dengan peranti berkelajuan rendah (kami memindahkan butiran pasir melalui butiran dari badan trak KamAZ ke dalam kotak pasir). Mari cuba perbaiki lagi.
Jom buang SELURUH trak KAMAZ dengan pasir sekali gus!
public class Solution {
public static void main(String[] args) throws Exception {
FileInputStream inputStream = new FileInputStream(new BufferedReader(new InputStreamReader(System.in)).readLine());
long[] arrBytes = new long[256];
long startTime = System.currentTimeMillis();
byte fileImage[]=new byte[inputStream.available()];
long fileSize=fileImage.length;
inputStream.read(fileImage);
for (int i = 0; i = 0 ; i--)
if (arrBytes[(int) i] > 0) System.out.print(i + " ");
long finishTime = System.currentTimeMillis();
System.out.println("\nвремя работы=" + (finishTime-startTime) + "ms.");
}
}
penyimpangan yang kecil, tetapi sekali lagi penting
. Nota:
- indeks arrBytes ditakrifkan dalam 0..255,
- fileImage ialah tatasusunan bait yang elemennya mempunyai nilai -128..127
Oleh itu, untuk mengira bait, kami akan menggunakan binaan
arrBytes[fileImage[i] & 0b11111111]++;
yang hanya akan menetapkan semula bit tanda dan mengembalikan kami nilai dalam julat 0..255
Dan seterusnya, keputusan: fail 46MB 0.13 saat (kurang daripada satu saat). Fail 1Gb - 9 saat. Kita berjaya! Kami sangat hebat! Dipercepatkan daripada 3 jam kepada 9 saat. Itu sahaja, anda boleh duduk di kerusi anda dan minum teh. Dan kini satu lagi percubaan - mari cuba fail 32 Gb (contohnya, filem HD). Akibatnya, kami mendapat bunyi berderak dari HDD yang berfungsi dengan program ranap dalam Windows. KamAZ membuang mayat dengan pasir dan memecahkan kotak pasir! Apa yang kita lakukan? Mari kita ingat satu fakta lagi. Fail dalam OS biasanya disimpan dalam bahagian (kluster) 2-64Kb (bergantung pada jenis sistem fail, tetapan, dll.). Kami akan membaca dalam bahagian, contohnya 64,000 bait. Mari cuba memunggah KamAZ dengan jengkaut dalam bahagian yang agak besar:
Menggunakan penimbal
public class Solution {
public static void main(String[] args) throws Exception {
FileInputStream inputStream = new FileInputStream(new BufferedReader(new InputStreamReader(System.in)).readLine());
long[] arrBytes = new long[256];
long startTime = System.currentTimeMillis();
int bufferSize = 64000;
byte buffer[] = new byte[64000];
while (inputStream.available() > 0) {
if (inputStream.available() < 64000) bufferSize = inputStream.available();
inputStream.read(buffer, 0, bufferSize );
for (int i = 0; i = 0 ; i--)
if (arrBytes[(int) i] > 0) System.out.print(i + " ");
long finishTime = System.currentTimeMillis();
System.out.println("\nвремя работы=" + (finishTime-startTime) + "ms.");
}
}
Hasilnya, kami mendapat: 46MB fail 0.08 saat (kurang daripada satu saat). Fail 1Gb - 0.9 saat (kurang daripada satu saat). Fail 32Gb - 31 saat. Ambil perhatian bahawa untuk fail 1 Gb kami telah meningkatkan prestasi daripada beberapa
jam kepada
pecahan saat !!! Dengan fakta sederhana ini, kami akan menyelesaikan percubaan dan menambah baik kod awal. Kami telah mencapai kemajuan dalam banyak cara - kami gembira dengan penunjuk baharu penggunaan memori dan masa operasi. Juga, dalam kes ini, kami tidak mengeluarkan koleksi tidak berguna daripada perpustakaan standard. PS Seseorang akan mengatakan contoh itu tidak masuk akal, dsb. Tetapi terdapat banyak tugas yang serupa - untuk menganalisis sejumlah besar elemen yang mempunyai bilangan keadaan terhingga. Sebagai contoh, imej (RGB - biasanya disimpan dalam 24 bait, dalam kes kami long[] arrRGB = new long[256*256*256] akan mengambil hanya 64MB dalam memori), muzik (amplitud biasanya didigitalkan dalam 16 atau 24 bit ) atau penderia penunjuk diskret, dsb.
GO TO FULL VERSION