Forörite
Başlalyň
18-nji derejede, baýt-baýt faýly okamagyň ilkinji meseleleri başlandy: faýly okaň, soňra iň az / iň ýokary baýt tapyň ýa-da sargyt edilen görnüşde çykaryň we ş.m.
Bu ýerdäki adamlar gaty akylly. Kolleksiýalar hakda, tertipläp we goýup biljekdigini bilýärler. Kolleksiýalar güýçli mehanizmdir. Köpüsi JavaRush-dan öň asla ulanmady. Elbetde, olary öwrenmek we nädogry ýerlerde urmaga synanyşmak öwgä mynasyp. Şeýlelik bilen Geliň, meselelerde bolmadyk meseläni çözeliň (çözülende talaňçy bolmaz ýaly), ýöne gaty meňzeşleri bar:
- Konsoldan faýl adyny giriziň
- Faýldan ähli baýtlary okaň.
- Gaýtalamalary äsgermezlik edip, aşak tertipde tertip kodlary boýunça tertipläň.
- Ekran
- I / O akymyny ýapyň
Giriş faýlynyň baýtlary
44 83 44 Çykyşyň mysaly
83 44 Üýtgeýjileri goşmaça girizdik
startTimewe
finishTimeprogrammanyň ýerine ýetiriliş wagtyny ýazga geçirdik.
Hasaplamak üçin i3-3GHz / 8Gb RAM / HDD WD Blue-1Tb / Win7-64 / jdk-8u73-windows-x64 ulandym (1-2 wariantdaky programmalaryň mysallary info.javarush forumyndan alyndy, olar birneme diňe ýokarlanýan tertipde tertiplemek üçin üýtgedildi - ýagny REAL !!)
Geliň, muny çözeliň:
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.");
}
}
Hemme zady ajaýyp çözýär! Synag (bolan bolsa, urmak bilen geçerdi). Lifeöne durmuşda diňe “Eje çarçuwany ýuwdy” diýen setir bar. Geliň, programmamyza 46MB faýl bereliň (şu günki standartlara görä, kän bir görünmeýär). Näme, programma 220 sekunt dowam edýär. Agşam 1Gb faýly iýmitlendirmek synanyşygy şowsuz boldy (MPEG4 filminiň göwrümi iň gowy hilli däl). Men henizem irden programmany okaýardym - we eýýäm işe gitmeli boldum. Mesele näme?
ArrayList<Integer>Içinde 1 milliard elementi bolan ulanylan bolsa gerek . Onuň her elementi iň az 16 baýt alýar (Sözbaşy: 8 baýt + Meýdan int: 4 baýt + 8: 4 baýt köpeltmek üçin deňleşdirme). Umuman alanyňda, 8 RAM ululygy bilen 16 Gb maglumatlary ýada salýarys. Has gowy ederis. Kolleksiýalara has çuňňur gireliň. We gyssagly, zerur zatlary tapdyk.
TreeSet bilen tanyş
Bu köp:
- iki meňzeş elementi saklamaga rugsat bermeýär (bu bir milliard däl-de, 255 elementiň hemmesini ýatda saklarys!)
- elementlerini dolandyranda, awtomatiki tertiplenýär (özüni tertipleýär - ine, kämilligiň beýikligi!)
Biz alýarys:
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.");
}
}
Çykyş: 46MB faýl, 176 sekunt. 1Gb faýly - 3 sagat 5 minut. Ösüş görnüp dur. Netijelere “garaşyp” bildik we 46MB faýly ep-esli çalt işlenýär. Öňe git.
Kolleksiýalardan ýüz öwürmäge synanyşalyň (bu käbirleri üçin gaty agyr bolar). Simpleönekeý massiwleri ulanarys (gaty ýönekeý).
Bir möhüm zady belläliň . Duşuşykdaky baýtlaryň sanyny 256 uzynlyk massiwine goýup bolar. Şeýlelik bilen, okalýan baýtlara laýyk gelýän massiw elementini ýeke-ýekeden köpelderis.
Array - baýt
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.");
}
}
Çykyş: 46MB faýl, 158 sekunt. 1Gb faýly - 2 sagat 55 minut. Againene bir gowulaşma, ýöne kiçi. Hemmesini ýönekeý gurallar bilen etdik.
Dyrnak sürmek üçin mikroskop ulanmadyňyz .
Indi liriki many. Kompýuteriň gurluşyny ýada salalyň. Programma adatça ýerine ýetirilýän we üýtgeýänler saklanýan
RAM ýady (DRAM) , giriş tizligi ýokary, ýöne ululygy az.
Faýllar adatça saklanýan gaty / fleş diskde (HDD ýa-da Flash disklerde) ýat, tersine, giriş tizligi pes, ýöne ululygy uludyr. Şeýlelik bilen 1Gb faýl baýt baýt okanymyzda (HDD-e milliard gezek girýäris) pes tizlikli enjam bilen işlemek üçin köp wagt sarp edýäris (KamAZ ýük awtoulagynyň bedeninden çäge dänesini däne bilen geçirýäris) sandyk gutusyna). Geliň, hasam kämilleşdirmäge synanyşalyň.
ENTIRE KAMAZ awtoulagyny birbada gum bilen taşlalyň!
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.");
}
}
kiçijik, ýöne ýene-de möhüm bir çuňňur bellik
. Bellik:
- arrBytes indeksi 0..255 aralygynda kesgitlenýär,
- fileImage, elementleri -128..127 bahasy bolan baýt massiwidir
arrBytes[fileImage[i] & 0b11111111]++; Şol sebäpden, baýtlary sanamak üçin, bellik bitini täzeden düzjek we 0..255 aralygynda bahany yzyna gaýtaryp berjek gurluşyk ulanarys
we şeýlelik bilen, netijeler: 46MB faýl 0,13 sekunt (bir sekuntdanam az). 1Gb faýly - 9 sekunt. Biz etdik! Ajaýyp ajaýyp! 3 sagatdan 9 sekuntda tizlik. Ine, oturgyçda oturyp çaý içip bilersiňiz. Indi başga bir synag - 32 Gb faýly synap göreliň (mysal üçin HD filmi). Netijede, Windows-da programma ýykylmagy bilen işleýän HDD-den gaty ses eşidilýär. KamAZ jesedi gum bilen taşlady we sandyk gutusyny döwdi! Biz näme edýäris? Moreene bir hakykaty ýada salalyň. Operasiýa ulgamyndaky faýllar, adatça 2-64Kb böleklerde (toparlar) saklanýar (faýl ulgamynyň görnüşine, sazlamalara we ş.m.). Böleklerde okarys, mysal üçin 64,000 baýt. KamAZ-ny gaty uly böleklere ekskawator bilen düşürmäge synanyşalyň:
Bufer ulanmak
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.");
}
}
Netijede, 46 MB faýl 0.08 sekunt (bir sekuntdanam az) aldyk. 1Gb faýly - 0,9 sekunt (bir sekuntdanam az). 32 Gb faýl - 31 sekunt.
1 Gb faýl üçin birnäçe sagatdan
sekundyň böleklerine çenli öndürijiligimizi ýokarlandyrdyk ! Bu sada hakykat bilen, synagy tamamlarys we başlangyç kody gowulaşdyrarys. Köp ugurda öňegidişlik gazandyk - ýadyň sarp edilişiniň we iş wagtynyň täze görkezijilerinden hoşal. Şeýle hem, bu ýagdaýda adaty kitaphanadan biderek kolleksiýalary çykarmaýarys. PS Kimdir biri mysalyň gaty uzakdygyny we ş.m. Similaröne şuňa meňzeş meseleleriň köpüsi bar - köp sanly ştata eýe bolan elementleriň uly mukdaryny seljermek. Mysal üçin, şekiller (RGB - adatça 24 baýtda saklanýar, biziň ýagdaýymyzda uzyn [] arrRGB = täze uzyn [256 * 256 * 256] diňe 64 MB ýat tutar), saz (amplituda adatça 16 ýa-da 24 bitde sanlaşdyrylýar) ) ýa-da aýratyn görkezijiler datçikleri we ş.m.
GO TO FULL VERSION