Besonderes für
Lass uns anfangen
Auf Stufe 18 begannen die ersten Aufgaben des Byte-für-Byte-Lesens von Dateien: Lesen Sie die Datei, ermitteln Sie dann die minimalen/maximalen Bytes oder geben Sie sie in geordneter Form aus usw.
Die Leute hier sind sehr schlau. Sie kennen sich mit Sammlungen aus und wissen, dass sie sortieren und einfügen können. Sammlungen sind ein leistungsstarker Mechanismus. Und viele haben sie vor JavaRush überhaupt nicht verwendet. Es ist natürlich lobenswert, sie zu studieren und zu versuchen, sie an den falschen Stellen zu treffen. Also. Nehmen wir ein Problem, das nicht in den Aufgaben enthalten ist (damit es bei der Lösung keine Spoiler gibt), es aber sehr ähnliche gibt:
- Geben Sie den Dateinamen über die Konsole ein
- Alle Bytes aus einer Datei lesen.
- Ignorieren Sie Wiederholungen und sortieren Sie sie in absteigender Reihenfolge nach Bytecode.
- Anzeige
- I/O-Stream schließen
Beispielbytes einer Eingabedatei
44 83 44 Beispiel einer Ausgabe
83 44 Wir haben zusätzlich Variablen eingeführt
startTimeund
finishTimedie Ausführungszeit des Programms aufgezeichnet. Für die Berechnung habe ich
i3-3GHz/8Gb RAM/HDD WD Blue-1Tb/Win7-64/jdk-8u73-windows-x64 verwendet (Beispiele für Programme in den Optionen 1-2 stammen aus dem info.javarush-Forum, sie sind leicht nur für die Sortierung in aufsteigender Reihenfolge modifiziert, okay – das heißt, sie sind ECHT!!)
Lassen Sie es uns direkt lösen:
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.");
}
}
Löst alles super! Der Test (wenn es ihn gegeben hätte, wäre er mit einem Knall bestanden worden). Aber im Leben gibt es nur wenige Dateien, die nur die Zeile „Mama hat den Rahmen gewaschen“ enthalten. Geben wir unserem Programm eine 46-MB-Datei (nach heutigen Maßstäben scheint das nicht viel zu sein). Was ist es, das Programm läuft 220 Sekunden. Ein Versuch, abends eine 1-GB-Datei einzuspeisen (die Größe des MPEG4-Films ist nicht von bester Qualität), war erfolglos. Ich las morgens noch das Programm – und musste schon zur Arbeit. Was ist das Problem? Wahrscheinlich im Einsatz
ArrayList<Integer>, das 1 Milliarde Elemente enthält. Jedes Element davon nimmt mindestens 16 Bytes ein (Header: 8 Bytes + Feldint: 4 Bytes + Ausrichtung für Multiplizität 8: 4 Bytes). Insgesamt haben wir bei einer RAM-Größe von 8 freiwillig 16 GB Daten in den Speicher gelegt. Wir werden es besser machen. Tauchen wir tiefer in die Sammlungen ein. Und Hurra, wir haben gefunden, was wir brauchten.
Lernen Sie TreeSet kennen
Das ist eine Menge:
- erlaubt nicht das Speichern von zwei identischen Elementen (was bedeutet, dass wir alle 255 Elemente im Speicher speichern, statt einer Milliarde!)
- Wenn es seine Elemente manipuliert, organisiert es sich automatisch (sortiert sich selbst – hier ist es, der Gipfel der Perfektion!)
Wir bekommen:
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.");
}
}
Die Ausgabe ist: 46 MB Datei, 176 Sekunden. 1-GB-Datei – 3 Stunden 5 Minuten. Der Fortschritt ist offensichtlich. Wir konnten auf die Ergebnisse „warten“ und die 46 MB große Datei wird spürbar schneller verarbeitet. Fortfahren. Versuchen wir, auf Sammlungen
zu verzichten (das wird für einige unerträglich schmerzhaft sein). Wir werden einfache Arrays verwenden (es ist so primitiv). Beachten wir eine
wichtige Sache . Die Anzahl der gefundenen Bytes kann in ein Array der Länge 256 eingefügt werden. Wir erhöhen also einfach das Array-Element, das dem gelesenen Byte entspricht, um eins.
Array - Byte für Byte
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.");
}
}
Die Ausgabe ist: 46 MB Datei, 158 Sekunden. 1-GB-Datei – 2 Stunden 55 Minuten. Wieder eine Verbesserung, aber klein. Und wir haben alles mit einfachen Werkzeugen gemacht.
Ich habe kein Mikroskop zum Einschlagen von Nägeln verwendet .
Nun ein lyrischer Exkurs. Erinnern wir uns an den Aufbau eines Computers.
Der RAM-Speicher (DRAM) , in dem normalerweise das Programm ausgeführt und Variablen gespeichert werden, hat eine hohe Zugriffsgeschwindigkeit, ist aber klein.
Der Speicher auf einem Festplatten-/Flash-Laufwerk (HDD oder Flash-Laufwerke), auf dem normalerweise Dateien gespeichert werden, weist dagegen eine niedrige Zugriffsgeschwindigkeit, aber eine große Größe auf. Wenn wir also eine 1-GB-Datei Byte für Byte lesen (das heißt, wir greifen eine Milliarde Mal auf die Festplatte zu), verbringen wir viel Zeit damit, mit einem Gerät mit niedriger Geschwindigkeit zu arbeiten (wir übertragen Sandkorn für Korn von der Karosserie eines KamAZ-Lastwagens). in den Sandkasten). Versuchen wir es weiter zu verbessern.
Lasst uns den GESAMTEN KAMAZ-Truck auf einmal mit Sand ausschütten!
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.");
}
}
ein kleiner, aber wieder wichtiger Exkurs
. Hinweis:
- Der arrBytes-Index ist innerhalb von 0..255 definiert.
- fileImage ist ein Byte-Array, dessen Elemente den Wert -128..127 haben
Um die Bytes zu zählen, verwenden wir daher eine Konstruktion
arrBytes[fileImage[i] & 0b11111111]++; , die einfach das Vorzeichenbit zurücksetzt und uns einen Wert im Bereich von 0 bis 255 zurückgibt
. Das Ergebnis lautet also: 46 MB Datei 0,13 Sekunden (weniger als eine Sekunde). 1-GB-Datei – 9 Sekunden. Wir haben es geschafft! Wir sind unglaublich cool! Beschleunigung von 3 Stunden auf 9 Sekunden. Das war's, Sie können sich in Ihrem Stuhl zurücklehnen und etwas Tee trinken. Und jetzt ein weiteres Experiment: Versuchen wir es mit einer 32-GB-Datei (z. B. einem HD-Film). Als Ergebnis hören wir ein knisterndes Geräusch von der funktionierenden Festplatte und das Programm stürzt unter Windows ab. KamAZ hat die Leiche mit Sand abgeladen und den Sandkasten zerbrochen! Was machen wir? Erinnern wir uns noch an eine Tatsache. Dateien im Betriebssystem werden normalerweise in Teilen (Clustern) von 2 bis 64 KB gespeichert (abhängig von der Art des Dateisystems, den Einstellungen usw.). Wir werden in Portionen lesen, zum Beispiel 64.000 Bytes. Versuchen wir, KamAZ in relativ großen Portionen mit einem Bagger zu entladen:
Verwendung eines Puffers
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.");
}
}
Als Ergebnis erhielten wir: 46 MB Datei 0,08 Sekunden (weniger als eine Sekunde). 1-GB-Datei – 0,9 Sekunden (weniger als eine Sekunde). 32-GB-Datei – 31 Sekunden. Beachten Sie, dass wir für eine 1-GB-Datei die Leistung von mehreren
Stunden auf
Bruchteile von Sekunden verbessert haben !!! Mit dieser bescheidenen Tatsache werden wir das Experiment beenden und den ursprünglichen Code verbessern. Wir haben in vielerlei Hinsicht Fortschritte gemacht – wir freuen uns über die neuen Indikatoren für Speicherverbrauch und Betriebszeit. Außerdem rufen wir in diesem Fall keine nutzlosen Sammlungen aus der Standardbibliothek ab. PS: Jemand wird sagen, das Beispiel sei weit hergeholt usw. Aber es gibt viele ähnliche Aufgaben – die Analyse einer riesigen Menge von Elementen, die eine endliche Anzahl von Zuständen haben. Zum Beispiel Bilder (RGB – normalerweise in 24 Bytes gespeichert, in unserem Fall würde long[] arrRGB = new long[256*256*256] nur 64 MB im Speicher beanspruchen), Musik (Amplitude wird normalerweise in 16 oder 24 Bit digitalisiert ) oder diskrete Anzeigesensoren usw.
GO TO FULL VERSION