以下のための特別な
始めましょう
レベル 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 ムービーのサイズは最高の品質ではありません) が失敗しました。私は朝になってもまだプログラムを読んでいたのですが、もう仕事に行かなければなりませんでした。何が問題ですか?おそらく内部に 10 億個の要素が含まれている使用中です
ArrayList<Integer>
。その各要素は、最小 16 バイトを占めます (ヘッダー: 8 バイト + フィールド整数: 4 バイト + 多重度 8 のアライメント: 4 バイト)。合計で、RAM サイズ 8 のメモリに 16 GB のデータを自発的に配置しました。今後はさらに改善していきます。コレクションをさらに詳しく見てみましょう。そして万歳、私たちは必要なものを見つけました。
ツリーセットの紹介
これはたくさんあります:
- 2 つの同一の要素を保存することはできません (つまり、10 億要素ではなく、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 のファイルが著しく高速に処理されました。どうぞ。
コレクションをやめてみましょう(これは人によっては耐え難い苦痛になるでしょう)。単純な配列を使用します (非常に原始的です)。
重要な点が1 つあることに注意してください。検出されたバイト数は、長さ 256 の配列に入れることができます。したがって、読み取ったバイトに対応する配列要素を単純に 1 つ増やします。
配列 - バイトごと
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 に 10 億回アクセスするとき)、低速デバイスでの作業に多くの時間を費やします (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 秒 (1 秒未満) となります。1Gb ファイル - 9 秒。 やった!私たちは信じられないほどクールです! 3時間から9秒にスピードアップしました。それで、椅子に座ってお茶を飲むことができます。次に、別の実験です。32 GB ファイル (HD ムービーなど) を試してみましょう。その結果、Windows でプログラムがクラッシュし、動作中の HDD からパチパチという音が発生します。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 秒 (1 秒未満) となりました。1Gb ファイル - 0.9 秒 (1 秒未満)。32Gb ファイル - 31 秒。 1 GB ファイルの場合、パフォーマンスが数
時間から
数秒に改善されたことに注意してください。このささやかな事実を踏まえて、実験を終了し、最初のコードを改善します。私たちは多くの点で進歩を遂げました。メモリ消費量と動作時間の新しい指標に満足しています。また、この場合、標準ライブラリから無駄なコレクションを取得しません。PS この例は荒唐無稽だ、などと言う人もいるでしょう。しかし、有限数の状態を持つ膨大な量の要素を分析するという同様のタスクがたくさんあります。たとえば、画像 (RGB - 通常は 24 バイトで保存されます。この場合、long[] arrRGB = new long[256*256*256] はメモリ内で 64MB しか占有しません)、音楽 (振幅は通常 16 ビットまたは 24 ビットでデジタル化されます) ) または個別のインジケーターセンサーなど。
GO TO FULL VERSION