データ構造とプログラミング（第２回）大岩元ＴＡ: 武田林太郎ＳＡ: 明石敬 array.java の問題点と改善 • クラスとメソッドがそれぞれ一つしかない手続き型プログラム • 改善の第１段: データ構造をオブジェクトとして独立させ、他をユーザーとする • 改善の第２段: データ構造とユーザーの間の情報伝達を改善する LowArray.java • クラス LowArray が配列を包み込み、メソッドを通じてしか内容に到達できない – setElem(), getElem(), LowArray • • • • データを収納するクラスをコンテナクラスと呼ぶ LowArrayApp クラスが LowArray を使う表示をLowArrayAppがやっている配列の index を LowArrayAppが管理している highArray.java • 何をやりたいか(what)と、どうやるか(how) が分離された • HighArray には、コンストラクタ, find, insert, delete, display が用意されている • HighArrayApp は index を扱わない orderedArray.java • 整列した配列は二分探索が使える • 二分探索は線型探索より格段に速い（後述） • delete, insert には、線型探索を使っている – 移動に時間がかかるため二分探索しても時間がかかる Log2(x) 比較回数範囲 10 100 1,000 10,000 100,000 1,00,000 10,000,000 100,000,000 1,000,000,000 必要な比較回数 4 7 10 14 17 20 24 27 30 0 1 2 3 4 5 6 7 8 9 10 x 2**x 1 2**0 2 2**1 4 2**2 8 2**3 16 2**4 32 2**5 64 2**6 128 2**7 256 2**8 512 2**9 1024 2**10 Big O 記法 • O(1): 非順序配列への挿入(追加） • O(log2(N): 二分探索 • O(N): 線型探索、順序配列への挿入・削除、非順序配列における削除 classDataArray.java • 配列のタイプがdouble から Person に変った • 比較は == でなく、 String.equals() を使う • highArray.java とほとんど同じ演習問題 • orderedArray.java の insert を二分探索に改善せよ。 • orderedArray.java の内容を文字列にせよ。さらに Person に拡張せよ。ふりがなのフィールドを導入してもよい。