במיוחד בשביל
בואו נתחיל
ברמה 18 החלו המשימות הראשונות של קריאת קובץ בתים-בייט: קראו את הקובץ, ואז מצאו את המינימום/מקסימום בתים או פלט אותו בצורה מסודרת וכו'.
האנשים פה מאוד חכמים. הם יודעים על אוספים ושהם יכולים למיין ולהכניס. אוספים הם מנגנון רב עוצמה. ורבים לא השתמשו בהם כלל לפני JavaRush. ראוי כמובן לשבח ללמוד אותם ולנסות לפגוע בהם במקומות הלא נכונים. כך. בואו ניקח בעיה שלא נמצאת במשימות (כדי שלא יהיו ספוילרים כשפותרים אותה), אבל יש כאלה מאוד דומות:
- הזן את שם הקובץ מהמסוף
- קרא את כל הבתים מקובץ.
- התעלמות מחזרות, מיין אותן לפי bytecode בסדר יורד.
- לְהַצִיג
- סגור את זרם הקלט/פלט
בתים לדוגמה של קובץ קלט
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>
שיש בו מיליארד אלמנטים בפנים. כל רכיב שלו תופס 16 בתים מינימום (כותרת: 8 בתים + שדה int: 4 בתים + יישור עבור ריבוי 8: 4 בתים). בסך הכל, הכנסנו מרצון 16 ג'יגה-בייט של נתונים לזיכרון עם גודל RAM של 8. נעשה יותר טוב. בואו נצלול עמוק יותר לתוך האוספים. ומהיר, מצאנו את מה שהיינו צריכים.
הכירו את TreeSet
זה הרבה:
- אינו מאפשר אחסון שני אלמנטים זהים (מה שאומר שנשמור את כל 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 - שעתיים 55 דקות. שוב שיפור, אבל קטן. ועשינו הכל עם כלים פשוטים.
לא השתמש במיקרוסקופ לנעילת ציפורניים .
עכשיו סטייה לירית. בואו נזכור את המבנה של מחשב.
זיכרון RAM (DRAM) , שבו התוכנית מבוצעת בדרך כלל ומשתנים מאוחסנים, הוא בעל מהירות גישה גבוהה, אך הוא קטן בגודלו.
זיכרון בכונן קשיח/פלאש (כונני קשיח או פלאש) שבו מאוחסנים בדרך כלל קבצים, להיפך, יש לו מהירות גישה נמוכה אבל גודל גדול. אז כאשר אנו קוראים קובץ של 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 ג'יגה (למשל סרט HD). כתוצאה מכך, אנו מקבלים צליל פצפוץ מהדיסק הקשיח הפועל כאשר התוכנית קורסת ב-Windows. KamAZ זרק את הגופה עם חול ושבר את ארגז החול! מה אנחנו עושים? בואו נזכור עוד עובדה אחת. קבצים במערכת ההפעלה מאוחסנים בדרך כלל בחלקים (אשכולות) של 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 ג'יגה-בייט שיפרנו את הביצועים ממספר
שעות לשברירי
שניות !!! עם עובדה צנועה זו, נסיים את הניסוי ונשפר את הקוד הראשוני. התקדמנו במובנים רבים - אנו מרוצים מהאינדיקטורים החדשים של צריכת זיכרון וזמן פעולה. כמו כן, במקרה זה, אנו לא מושכים אוספים חסרי תועלת מהספרייה הרגילה. נ.ב מישהו יגיד שהדוגמה מופרכת וכו'. אבל יש הרבה משימות דומות - לנתח נפח עצום של אלמנטים שיש להם מספר סופי של מצבים. לדוגמה, תמונות (RGB - מאוחסנות בדרך כלל ב-24 בתים, במקרה שלנו long[] arrRGB = new long[256*256*256] יתפוס רק 64MB בזיכרון), מוזיקה (משרעת בד"כ דיגיטאלית ב-16 או 24 ביטים ) או חיישני מחוונים נפרדים וכו'.
GO TO FULL VERSION