พิเศษสำหรับ
มาเริ่มกันเลย
ที่ระดับ 18 งานแรกของการอ่านไฟล์แบบไบต์ต่อไบต์เริ่มต้นขึ้น: อ่านไฟล์ จากนั้นค้นหาไบต์ขั้นต่ำ/สูงสุด หรือส่งออกในรูปแบบที่เรียงลำดับ ฯลฯ
ผู้คนที่นี่ฉลาดมาก พวกเขารู้เกี่ยวกับคอลเลกชันและสามารถจัดเรียงและแทรกได้ คอลเลกชันเป็นกลไกอันทรงพลัง และหลายคนไม่ได้ใช้เลยก่อน JavaRush แน่นอนว่าเป็นเรื่องน่ายกย่องที่ได้ศึกษาและพยายามตีผิดที่ ดังนั้น. ลองใช้ปัญหาที่ไม่ได้อยู่ในงาน (เพื่อไม่ให้สปอยล์เมื่อแก้ไข) แต่มีปัญหาที่คล้ายกันมาก:
- ป้อนชื่อไฟล์จากคอนโซล
- อ่านไบต์ทั้งหมดจากไฟล์
- ไม่สนใจการซ้ำซ้อน ให้จัดเรียงตามไบต์โค้ดจากมากไปน้อย
- แสดง
- ปิดสตรีม I/O
ตัวอย่างไบต์ของไฟล์อินพุต
44 83 44 ตัวอย่างเอาต์พุต
83 44 เราได้แนะนำตัวแปรเพิ่มเติม
startTime
และ
finishTime
เพื่อบันทึกเวลาการทำงานของโปรแกรม สำหรับการคำนวณ ฉันใช้
i3-3GHz/8Gb RAM/HDD WD Blue-1Tb/Win7-64/jdk-8u73-windows-x64 (ตัวอย่างโปรแกรมในตัวเลือก 1-2 นำมาจากฟอรัม info.javarush เพียงเล็กน้อย แก้ไขเฉพาะการเรียงลำดับจากน้อยไปมากเท่านั้น โอเค - นั่นคือของจริง!!)
มาแก้ปัญหากันเถอะ:
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.");
}
}
ตอบโจทย์ทุกปัญหา! บททดสอบ (ถ้ามีก็คงผ่านไปแบบปังๆ) แต่ในชีวิตมีไฟล์เพียงไม่กี่ไฟล์ที่มีเพียงบรรทัดว่า "แม่ล้างกรอบ" มาป้อนไฟล์โปรแกรมของเราขนาด 46MB กันเถอะ (ตามมาตรฐานปัจจุบันดูเหมือนไม่มาก) คืออะไรครับ โปรแกรมรัน 220 วินาที ความพยายามที่จะป้อนไฟล์ 1Gb ในตอนเย็น (ขนาดของภาพยนตร์ MPEG4 ไม่ใช่คุณภาพที่ดีที่สุด) ไม่ประสบผลสำเร็จ ฉันยังอ่านรายการอยู่ในตอนเช้า - และฉันต้องไปทำงานแล้ว อะไรคือปัญหา? น่าจะใช้งานอยู่
ArrayList<Integer>
ซึ่งมีองค์ประกอบถึง 1 พันล้านชิ้นอยู่ข้างใน แต่ละองค์ประกอบของมันใช้เวลาขั้นต่ำ 16 ไบต์ (ส่วนหัว: 8 ไบต์ + Field int: 4 ไบต์ + การจัดตำแหน่งสำหรับหลายหลาก 8: 4 ไบต์) โดยรวมแล้วเราใส่ข้อมูล 16 Gb ลงในหน่วยความจำโดยสมัครใจโดยมีขนาด RAM 8 เราจะทำให้ดีกว่านี้ มาดำดิ่งลึกเข้าไปในคอลเลกชันกันดีกว่า และไชโย เราพบสิ่งที่เราต้องการแล้ว
พบกับทรีเซ็ต
มันเยอะมาก:
- ไม่อนุญาตให้จัดเก็บสององค์ประกอบที่เหมือนกัน (ซึ่งหมายความว่าเราจะจัดเก็บองค์ประกอบทั้งหมด 255 รายการไว้ในหน่วยความจำ แทนที่จะเป็นหนึ่งพันล้าน!)
- เมื่อจัดการองค์ประกอบต่างๆ มันจะจัดระเบียบโดยอัตโนมัติ (เรียงลำดับตัวเอง - นี่คือความสูงของความสมบูรณ์แบบ!)
เราได้รับ:
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.");
}
}
ผลลัพธ์คือ: ไฟล์ 46MB, 176 วินาที ไฟล์ 1Gb - 3 ชั่วโมง 5 นาที ความก้าวหน้าก็ชัดเจน เราสามารถ “รอ” ผลลัพธ์ได้ และไฟล์ 46MB ก็ได้รับการประมวลผลเร็วขึ้นอย่างเห็นได้ชัด ไปข้างหน้า. เรามาลอง
ละทิ้งการสะสมกันเถอะ (บางคนอาจจะเจ็บปวดแสนสาหัส) เราจะใช้อาร์เรย์แบบง่าย (มันดั้งเดิมมาก) เรามาสังเกต
สิ่งสำคัญอย่าง หนึ่ง จำนวนไบต์ที่พบสามารถใส่ลงในอาร์เรย์ที่มีความยาว 256 ได้ ดังนั้นเราจะเพิ่มองค์ประกอบอาร์เรย์ที่สอดคล้องกับไบต์ที่อ่านทีละไบต์
อาร์เรย์ - ไบต์ต่อไบต์
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.");
}
}
ผลลัพธ์คือ: ไฟล์ 46MB, 158 วินาที ไฟล์ 1Gb - 2 ชั่วโมง 55 นาที การปรับปรุงอีกครั้ง แต่มีขนาดเล็ก และเราทำทุกอย่างด้วยเครื่องมือง่ายๆ ไม่
ได้ใช้กล้องจุลทรรศน์ในการตอกตะปู
ตอนนี้การพูดนอกเรื่องโคลงสั้น ๆ เรามาจำโครงสร้างของคอมพิวเตอร์กันดีกว่า
หน่วยความจำ RAM (DRAM)ซึ่งโดยปกติแล้วโปรแกรมจะถูกเรียกใช้งานและจัดเก็บตัวแปรไว้ มีความเร็วในการเข้าถึงสูง แต่มีขนาดเล็ก
หน่วยความจำบนฮาร์ด/แฟลชไดรว์ (HDD หรือแฟลชไดรฟ์) ซึ่งโดยปกติแล้วไฟล์ต่างๆ จะถูกจัดเก็บ ในทางกลับกัน มีความเร็วในการเข้าถึงต่ำแต่มีขนาดใหญ่ ดังนั้นเมื่อเราอ่านไฟล์ 1Gb ไบต์ต่อไบต์ (นั่นคือเราเข้าถึง HDD หนึ่งพันล้านครั้ง) เราใช้เวลามากมายในการทำงานกับอุปกรณ์ความเร็วต่ำ (เราถ่ายโอนเม็ดทรายทีละเม็ดจากตัวถังของรถบรรทุก KamAZ ลงในกระบะทราย) ลองปรับปรุงให้ดียิ่งขึ้น
ทิ้งรถบรรทุก KAMAZ ด้วยทรายทันที!
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.");
}
}
การพูด นอกเรื่องเล็ก ๆ แต่สำคัญ อีกครั้ง
หมายเหตุ:
- ดัชนี arrBytes ถูกกำหนดไว้ภายใน 0..255
- fileImage คืออาร์เรย์ไบต์ที่มีองค์ประกอบมีค่า -128..127
ดังนั้น ในการนับไบต์ เราจะใช้โครงสร้าง
arrBytes[fileImage[i] & 0b11111111]++;
ที่จะรีเซ็ตบิตเครื่องหมายและส่งกลับค่าในช่วง 0..255 ให้เรา
ดังนั้นผลลัพธ์: ไฟล์ 46MB 0.13 วินาที (น้อยกว่าหนึ่งวินาที) ไฟล์ 1Gb - 9 วินาที เราทำได้! พวกเราเจ๋งมาก! เพิ่มความเร็วจาก 3 ชั่วโมงเป็น 9 วินาที เพียงเท่านี้คุณก็สามารถนั่งบนเก้าอี้แล้วดื่มชาได้ และตอนนี้มีการทดลองอีกครั้ง - ลองใช้ไฟล์ขนาด 32 Gb (เช่น ภาพยนตร์ HD) เป็นผลให้เราได้รับเสียงแตกจาก HDD ที่ใช้งานได้โดยที่โปรแกรมหยุดทำงานใน Windows KamAZ เททรายใส่ศพแล้วพังกระบะทราย! พวกเราทำอะไร? เรามาจำข้อเท็จจริงอีกข้อหนึ่งกัน โดยปกติไฟล์ใน OS จะถูกจัดเก็บไว้ในส่วน (คลัสเตอร์) ขนาด 2-64Kb (ขึ้นอยู่กับประเภทของระบบไฟล์ การตั้งค่า ฯลฯ) เราจะอ่านเป็นส่วนๆ เช่น 64,000 ไบต์ เรามาลองขนถ่าย KamAZ ด้วยเครื่องขุดในส่วนที่ค่อนข้างใหญ่:
การใช้บัฟเฟอร์
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.");
}
}
ผลลัพธ์ที่ได้คือ: ไฟล์ 46MB 0.08 วินาที (น้อยกว่าหนึ่งวินาที) ไฟล์ 1Gb - 0.9 วินาที (น้อยกว่าหนึ่งวินาที) ไฟล์ 32Gb - 31 วินาที โปรดทราบว่าสำหรับไฟล์ 1 Gb เราได้ปรับปรุงประสิทธิภาพจากหลาย
ชั่วโมงเป็น
เศษส่วนวินาที !!! ด้วยข้อเท็จจริงเล็กน้อยนี้ เราจะเสร็จสิ้นการทดสอบและปรับปรุงโค้ดเริ่มต้น เรามีความก้าวหน้าในหลายๆ ด้าน - เราพอใจกับตัวบ่งชี้ใหม่เกี่ยวกับการใช้หน่วยความจำและเวลาในการทำงาน นอกจากนี้ ในกรณีนี้ เราจะไม่ดึงคอลเลกชันที่ไม่มีประโยชน์จากไลบรารีมาตรฐาน ป.ล. บางคนจะบอกว่าตัวอย่างนี้ลึกซึ้งมาก ฯลฯ แต่มีงานที่คล้ายกันมากมาย - เพื่อวิเคราะห์องค์ประกอบจำนวนมากที่มีสถานะจำนวนจำกัด ตัวอย่างเช่น รูปภาพ (RGB - โดยปกติจะจัดเก็บเป็น 24 ไบต์ ในกรณีของเรา long[] arrRGB = new long[256*256*256] จะใช้พื้นที่หน่วยความจำเพียง 64MB) เพลง (แอมพลิจูดมักจะแปลงเป็นดิจิทัลเป็น 16 หรือ 24 บิต ) หรือเซ็นเซอร์ตัวบ่งชี้แบบแยก ฯลฯ
GO TO FULL VERSION