Махсус барои
Биёед оғоз кунем
Дар сатҳи 18, аввалин вазифаҳои хондани файлҳои byte ба byte оғоз ёфт: файлро хонед, пас byteҳои минималӣ/максимумро пайдо кунед ё онро дар шакли фармоишӣ баровардан ва ғайра.
Мардуми ин ҷо хеле оқил ҳастанд. Онҳо дар бораи коллексияҳо медонанд ва онҳо метавонанд ҷудо ва дохил кунанд. Коллекцияхо механизми тавоно мебошанд. Ва бисёриҳо қабл аз JavaRush онҳоро умуман истифода намебурданд. Албатта, омух-тани онхо ва кушиши дар чойхои нодуруст задани онхо шоёни тахсин аст. Пас. Биёед як масъалаеро гирем, ки дар вазифаҳо нест (то он ки ҳангоми ҳалли он ҳеҷ гуна вайронкуниҳо набошад), аммо мушкилоти хеле монанд мавҷуданд:
- Номи файлро аз консол ворид кунед
- Ҳама byteҳоро аз файл хонед.
- Такрорҳоро нодида гирифта, онҳоро аз рӯи bytecode бо тартиби кам ҷудо кунед.
- Намоиш
- Ҷараёни вуруд/чорро пӯшед
Намунаи byteҳои файли воридотӣ
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 гирифта шудаанд, онҳо каме ҳастанд. танҳо барои ҷудокунӣ бо тартиби афзоиш тағир дода шудааст, хуб аст - яъне онҳо REAL мебошанд !!)
Биёед онро сари вақт ҳал кунем:
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.");
}
}
Ҳама чизро олӣ ҳал мекунад! Санҷиш (агар мебуд, бо як таркиш мегузарад). Аммо дар ҳаёт кам файлҳо мавҷуданд, ки танҳо сатри "Модар кадрро шустааст". Биёед барномаи худро бо файли 46 МБ таъмин кунем (аз рӯи стандартҳои имрӯза, он чандон зиёд ба назар намерасад). Ин чист, барнома 220 сония кор мекунад. Кӯшиши ғизо додани файли 1 Гб дар шом (андозаи филми MPEG4 аз беҳтарин сифат нест) бебарор буд. Ман ҳанӯз саҳар барномаро хонда будам - ва ман бояд аллакай ба кор равам. Мушкил чист? Эҳтимол дар истифода аст
ArrayList<Integer>
, ки дар дохor он 1 миллиард элемент дорад. Ҳар як унсури он ҳадди аққал 16 byteро ишғол мекунад (Сарлавҳа: 8 byte + Майдон int: 4 byte + Ҳамоҳангсозӣ барои зиёдшавии 8: 4 byte). Дар маҷмӯъ, мо ихтиёран 16 Гб маълумотро ба хотира бо андозаи RAM 8 мегузорем. Мо беҳтар кор хоҳем кард. Биёед ба коллексияҳо амиқтар ғарқ шавем. Ва тез, мо чизи лозимаро ёфтем.
Бо TreeSet вохӯред
Ин бисёр аст:
- имкон намедиҳад, ки ду унсури якхела нигоҳ дошта шаванд (яъне мо ба ҷои як миллиард, ҳамаи 255 элементро дар хотира нигоҳ медорем!)
- ҳангоми идора кардани унсурҳои худ, он ба таври худкор ташкил мекунад (худ ба навъҳо ҷудо мекунад - ин аст, баландии комorят!)
Мо ба даст меорем:
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 сония. Файли 1 Гб - 3 соат 5 дақиқа. Пешравй равшан аст. Мо тавонистем натиҷаҳоро "интизори" кунем ва файли 46 МБ ба таври назаррас зудтар коркард мешавад. Ба пеш. Биёед кӯшиш кунем
, ки аз коллексияҳо даст кашем (ин барои баъзеҳо тоқатфарсо хоҳад буд). Мо массивҳои оддиро истифода хоҳем кард (ин хеле ибтидоӣ аст). Биёед як
чизи муҳимро қайд кунем . Миқдори byteҳои дучоршударо метавон ба массиви дарозии 256 ворид кард. Ҳамин тавр, мо танҳо элементи массиви мувофиқро ба byteи хондан як маротиба зиёд мекунем.
Массив - byte ба 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.");
}
}
Натиҷа: файли 46MB, 158 сония. Файли 1 Гб - 2 соату 55 дақиқа. Боз як такмил, вале хурд. Ва мо ҳама чизро бо асбобҳои оддӣ анҷом додем.
Барои кашидани нохунҳо микроскоп истифода набурд .
Акнун як дурнамои лирикӣ. Биёед сохтори компютерро ба ёд орем.
Хотираи RAM (DRAM) , ки дар он барнома одатан иҷро мешавад ва тағирёбандаҳо нигоҳ дошта мешаванд, суръати дастрасии баланд дорад, аммо андозаи хурд дорад.
Хотира дар диски сахт/флешдор (HDD ё флеш-дискҳо), ки дар он файлҳо одатан нигоҳ дошта мешаванд, баръакс суръати дастрасии паст дорад, вале андозаи калон дорад. Ҳамин тавр, вақте ки мо файли 1 Гб-ро byte ба byte мехонем (яъне мо ба HDD миллиард маротиба дастрасӣ пайдо мекунем), мо вақти зиёдро бо дастгоҳи пастсуръат кор мекунем (мо донаи қумро аз бадани мошини КамАЗ интиқол медиҳем) ба қуттии қум). Биёед кӯшиш кунем, ки онро минбаъд такмил диҳем.
Биёед, ТАМОМИ КАМАЗ-ро якбора реги реем!
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 массиви byte аст, ки унсурҳои он арзиши -128..127 доранд
Аз ин рӯ, барои ҳисоб кардани byte, мо конструксияеро истифода мебарем
arrBytes[fileImage[i] & 0b11111111]++;
, ки битро танҳо аз нав танзим мекунад ва ба мо арзишро дар диапазони 0..255 бармегардонад
Ва ҳамин тавр, натиҷаҳо: файли 46MB 0,13 сония (камтар аз як сония). Файли 1 Гб - 9 сония. Мо инро кардем! Мо бениҳоят сард ҳастем! Суръат аз 3 соат то 9 сония. Хамин аст, шумо метавонед дар курсии худ нишаста чой нӯшед. Ва ҳоло озмоиши дигар - биёед файли 32 Гб (масалан, филми HD) -ро санҷем. Дар натиҷа, мо аз HDD-и корӣ садои тарқиш ба даст меорем, ки барнома дар Windows кор мекунад. КамАЗ ҷасадро бо қум рехта, қуттии қумро шикаст! Мо чӣ кор мекунем? Боз як фактро ба хотир меорем. Файлҳо дар ОС одатан дар қисмҳо (кластерҳо) аз 2-64 Кб (вобаста ба намуди системаи файлӣ, танзимот ва ғ.) нигоҳ дошта мешаванд. Мо қисм-қисм мехонем, масалан 64000 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();
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 сония (камтар аз як сония). Файли 1 Гб - 0,9 сония (камтар аз як сония). Файли 32 Гб - 31 сония. Дар хотир доред, ки барои файли 1 Гб мо иҷрои онро аз чанд
соат то
фраксияҳои сония беҳтар кардем !!! Бо ин далели хоксор, мо таҷрибаро анҷом медиҳем ва рамзи ибтидоиро такмил медиҳем. Мо аз бисёр ҷиҳатҳо пешравӣ кардем - мо аз нишондодҳои нави истеъмоли хотира ва вақти корӣ хурсандем. Инчунин, дар ин ҳолат, мо коллексияҳои бефоидаро аз китобхонаи стандартӣ намегирем. PS Касе мегӯяд, ки мисол дур аст ва ғайра. Аммо бисёр вазифаҳои шабеҳ вуҷуд доранд - таҳлor миқдори зиёди элементҳое, ки шумораи ниҳоии ҳолат доранд. Масалан, тасвирҳо (RGB - одатан дар 24 byte нигоҳ дошта мешаванд, дар ҳолати мо long[] arrRGB = new long[256*256*256] дар хотира ҳамагӣ 64МБ мегирад), мусиқӣ (амплитуда одатан дар 16 ё 24 бит рақамӣ карда мешавад. ) ё сенсорҳои нишондиҳандаҳои дискретӣ ва ғайра.
GO TO FULL VERSION