実装編②HashTable,JavaAPI

Slides:



Advertisements
Similar presentations
【事例演習5】  字句解析     解 説  “ハッシュを用いた字句解析の方法”.
Advertisements

Generic programming と STL
アルゴリズムとデータ構造 2013年6月18日
アルゴリズムとデータ構造1 2005年7月8日
~手続き指向からオブジェクト指向へ(Ⅰ)~
Ex7. Search for Vacuum Problem
アルゴリズムとデータ構造 2010年7月5日
データ構造とアルゴリズム論 第6章 探索のアルゴリズム
Ex8. Search for Vacuum Problem(2)
プログラミング基礎I(再) 山元進.
データ構造とプログラミング技法 (第8回) ーデータの探索ー.
第9回 並び替えアルゴリズム ~さまざまなアルゴリズムを比較しよう~.
アルゴリズムとデータ構造 2012年6月14日
情報工学概論 (アルゴリズムとデータ構造)
独習Java ・ 10.6  Hashtableクラス ・ 10.7  String Tokenizerクラス  12月12日    小笠原 一恵.
卒研:データベースチーム 第4回 DOMを使った処理
第8回 プログラミングⅡ 第8回
アルゴリズムとデータ構造 2011年6月13日
データ構造と アルゴリズム 第八回 知能情報学部 新田直也.
第20章 Flyweight ~同じものを共有して無駄をなくす~
アルゴリズムとデータ構造 2011年6月14日
アルゴリズムとデータ構造 2011年6月20日
データ構造と アルゴリズム 第十一回 理工学部 情報システム工学科 新田直也.
データ構造と アルゴリズム 第四回 知能情報学部 新田直也.
第13回 ハッシュテーブルを使ったプログラム ~高速に検索するには?~.
~手続き指向からオブジェクト指向へ[Ⅱ]~
第11回 アプリケーションの構成 ~CUI自動販売機の完成!~.
ハッシュテーブル.
ハッシュ表 データ構造とプログラミング(12)
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造1 2006年6月16日
プログラミング 4 記憶の割り付け.
Collection, Generics, Iterator
講義では、Cプログラミングの基本を学び 演習では、やや実践的なプログラミングを通して学ぶ
オブジェクト指向 プログラミング 第七回 知能情報学部 新田直也.
データ構造と アルゴリズム 第五回 知能情報学部 新田直也.
アルゴリズムとデータ構造1 2009年7月9日
アルゴリズムとデータ構造1 2005年7月5日
アルゴリズムとデータ構造1 2005年6月24日
アルゴリズムとデータ構造 2010年6月21日
2005年度 データ構造とアルゴリズム 第6回 「ハッシュ法を用いた探索」
アルゴリズムとデータ構造 2010年7月26日
オブジェクト指向 プログラミング 第六回 知能情報学部 新田直也.
プログラミング 4 探索と計算量.
オブジェクト・プログラミング 第8回.
データ構造とアルゴリズム 第11回 リスト構造(1)
アルゴリズムとプログラミング (Algorithms and Programming)
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
オブジェクト指向 プログラミング 第六回 知能情報学部 新田直也.
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造 2012年6月11日
JAVA入門③ 配列とコレクション.
アルゴリズムとプログラミング (Algorithms and Programming)
コレクション・フレームワーク J2EE I (データベース論) 第6回 /
コレクション・フレームワーク データベース論 第7回.
アルゴリズムとデータ構造1 2008年7月24日
サブゼミ第7回 実装編① オブジェクト型とキャスト.
第8回 データを収納する (スタックとキュー)
アルゴリズムとデータ構造1 2006年6月23日
アルゴリズムとデータ構造1 2009年7月2日
アルゴリズムとデータ構造 2012年6月21日
データ構造と アルゴリズム 第四回 知能情報学部 新田直也.
アルゴリズムとデータ構造1 2005年7月12日
アルゴリズムとデータ構造1 2007年7月6日
オブジェクト指向 プログラミング 第六回 知能情報学部 新田直也.
JSFによるWebアプリケーション開発 第7回
オブジェクト・プログラミング 第10回 オブジェクト指向設計のキモ.
計算機プログラミングI 第2回 2002年10月17日(木) 履習登録 複習 ライブラリの利用 (2.6-7) 式・値・代入 (2.6-8)
計算機プログラミングI 第5回 2002年11月7日(木) 配列: 沢山のデータをまとめたデータ どんなものか どうやって使うのか
プログラミング論 バイナリーサーチ 1.
Presentation transcript:

実装編②HashTable,JavaAPI サブゼミ第8回 実装編②HashTable,JavaAPI

Objective 連想配列(ハッシュテーブル)の概念を利点欠点を明らかにしながら説明できるようになる ハッシュテーブルを使ったプログラムが書けるようになる JavaAPIを使ったプログラムが書けるようになる

前回のモデル ・配列を管理するクラスを導入したクラス図 このままでは追加と表示しかできません

検索するには ☆例えば、商品番号1055の価格が知りたい場合 番号=1001 商品名="コーラ" 価格=150 番号=1055 商品名="DDレモン" 価格=120 番号=1022 商品名="ソーダ" 価格=140 [1] [2] [3] [4] 配列を順繰りにたどって探す(リニアサーチ) しかし遅いO(N)

検索するには ☆例えば、商品番号1055の価格が知りたい場合 番号=1001 商品名="コーラ" 価格=150 番号=1022 商品名="ソーダ" 価格=140 番号=1055 商品名="DDレモン" 価格=120 [1] [2] [3] [4] 商品番号順にならんでいれば(バイナリサーチ) なかなか速いO(logN)

でも実用性がない ☆商品番号1055の価格が知りたい ということはあまりなく ☆DDレモンの価格が知りたい という使い方をしたい

商品名で検索する ☆例えば、DDレモンの価格が知りたい場合 番号=1001 商品名="コーラ" 価格=150 番号=1022 商品名="ソーダ" 価格=140 番号=1055 商品名="DDレモン" 価格=120 [1] [2] [3] [4] 配列を順繰りにたどって探す(リニアサーチ) しかし遅いO(N) ではどのように検索したらよいのか

どのように検索したら 速くなるのか 現状の問題点を整理しよう 早くするためのアイディアを考えよう

こんなのが欲しい list[0].getPrice() list[1].getPrice() このような配列を 「連想配列」(ハッシュテーブル) といいます。 list["コーラ"].getPrice() list["DDレモン"].getPrice() perlなどでは標準でできる Javaでは、そのようなオブジェクト を作る

ハッシュテーブルを作るには まず、文字として扱っている間は、コンピュータでは検索できないので、何らかの数字に変換します。 インデックスシング、ハッシング 例えば、こんなやり方があります(詳しくは専門書を見て) 変換表 コ 98 コーラ    → 9810367 - 103 ラ 67

大きい配列を作る!? コーラ → 9810367 これをそのまま配列のインデックスにしようとすると、相当大きい 配列が必要 コーラ    → 9810367 これをそのまま配列のインデックスにしようとすると、相当大きい 配列が必要 list[9810367].getPrice() →現実的ではない

小さい配列で済むためには 1000要素の配列で済ませることを考える コーラ → 9810367 → 367 コーラ    → 9810367    →    367 プログラムで9810367→367と変換するには 9810367%1000 (1000で割ったあまりを求める)

ハッシュ関数 高速検索できるように、文字列から、一定範囲の数字を求める関数のこと 詳しくは「アルゴリズムとデータ構造」を見てみよう 今回の説明でのまずいところを発見しよう JavaではObjectクラスにhashcode()メソッドがあるので、どんなオブジェクトでも、簡単に求めることができます。

衝突が起こる 違うオブジェクトが同じハッシュ値になる可能性がある コーラ → 31256448 → 448 コーラ    → 31256448    →    448 ソーダ   → 587648448    →    448

衝突回避① 空き番地法(線形探索) ソーダも入りたい! ・・・・・ 1 2 3 4 447 448 コーラ 449 ソーダ 500 DDレモン ・・・・・ もし計算されたアドレスにすでにデータが格納されていた場合 次のアドレスにデータを格納する。 次も格納されていたらさらに次のアドレスに格納しようとする 検索するときにはハッシュ値を求めた後、そのアドレスから 順に配列の中身をリニアサーチで調べる

空き番地法(線形探索)の問題点 クラスター化 →平方探索に変えると第2種クラスター化 1 2 3 4 5 6 7 8 9 10 11 12 13 →平方探索に変えると第2種クラスター化 →クラスター化を防ぐためにダブルハッシュ などの技法を使う必要あり

衝突回避② 分離連鎖法 ・・・・・ 衝突したら、そのアドレスからさらに連結リストを使ってデータを格納しておく方法 1 2 3 4 447 448 コーラ 449 500 ソーダ DDレモン ・・・・・ 衝突したら、そのアドレスからさらに連結リストを使ってデータを格納しておく方法 検索するときにはハッシュ値を求めた後、そのアドレスから 順に連結リストを使って調べる

ハッシュテーブルの 利点、欠点を考えてみよう

ハッシュテーブルの概念整理 key value 辞書、住所録みたいなものに 適している 青山 090-xxx-xxxxx 海保 高嶋 松澤 ”コーラ” colaObject ”ソーダ” sodaObject ”お茶” chaObject ”DD” ddObject

ハッシュテーブルの問題点 データの保持に内部的には配列を使用するので  事前に用意した配列が満杯に近づいてくると  検索、挿入の効率が格段に落ちる 保持するデータを昇順や降順に  ソートして取り出すといった機能はない 高速な検索が必要で確保するべきデータ量が ある程度予測できる場合に使う

JavaAPIを利用する API Application Programming Interface アプリケーションを作るためによく使う機能を提供するプログラム →ライブラリ Javaでは関数群ではなく、よく使われるクラスの集まりと考えればよい Swingや、Servletなどもそれに当たります。

APIを使おう 配列で作ったリスト、連結リスト、ハッシュテーブルなどは良く使うので、 既に作られている。 配列で実装された リストクラス 連結リストで実装された リストクラス

APIを利用した設計

Listの使い方 特徴 主な実装クラス 主なメソッド データを順番に並べて格納する 格納するデータは重複してもかまわない ArrayList・・・単方向リストを配列で実装したもの LinkedList・・・配列で実装した連結リスト 主なメソッド add(Object)・・・リストにオブジェクトを追加する get(int)・・・リストから引数の位置にある        要素を取り出す remove(Object)・・・指定された要素を削除 size()・・・リストの要素数を返す iterator()・・・リストのIteratorを返す

使い方を調べる JavaAPIドキュメント これを使えば知らない機能や 知らないクラスなども調べて使うことができます。 メソッドの使い方を忘れてしまったり、知らない機能を 追加したいときはまずAPIを見てみる癖をつけましょう! http://java.sun.com/j2se/1.3/ja/docs/ja/api/index.html

Listを使った実装ー定義ー import java.util.*; public class 取扱商品型 { private List 商品情報リスト;//取り扱う商品情報のリスト /** * コンストラクタ */ public 取扱商品型() { 商品情報リスト=new ArrayList();//ArrayListを初期化する }

Listを使った実装ー追加ー /** * 取扱商品に商品情報を追加するメソッド */ public void 商品追加(商品情報型 追加商品情報){ 商品情報リスト.add(追加商品情報); }

Listを使った実装ー検索ー /** * 商品を商品名で検索するメソッド */ public 商品情報型 検索(String 検索名){ //リニアサーチ!こんなプログラムは実際には書くなよ。-->Hashでね int len = 商品情報リスト.size(); for(int i=0;i<len;i++){ 商品情報型 商品情報 = (商品情報型)商品情報リスト.get(i); if(商品情報.get商品名().equals(検索名)){//見つかった return 商品情報; } return null;//見つからなかった

Listを使った実装ー表示ー /** * 登録されているすべての商品情報の商品名とID、価格を出力するメソッド */  /** * 登録されているすべての商品情報の商品名とID、価格を出力するメソッド */ public void 商品表示(){ int len = 商品情報リスト.size(); for(int i=0;i<len;i++){ 商品情報型 商品情報 = (商品情報型)商品情報リスト.get(i); System.out.println(商品情報.get商品名()+" "+商品情報.get商品価格()+"円"); }

Collectionフレームワーク

今週の課題① APIドキュメントを読んで、 CollectionクラスとCollectionsクラスの違いを説明しなさい JavaAPIを使ってソートする方法を調べなさい。そしてそのソートはどんなアルゴリズムを使っているか答えなさい スタック、キューを作るにはどのクラスをどんな風に使えばよいのか調べなさい

今週の課題② 先週配布したソースコードを 改良して取扱商品は HashMapを使い、取扱貨幣は ArrayListを使ってデータを 格納するように改良してください。 また取扱商品には検索()メソッドを 追加してください。 必ずHashMapのAPIを調べてから行うこと。

課題のために APIドキュメントとスケルトン(持ってない人は)ここからダウンロードも可能です http://nautilus.crew.sfc.keio.ac.jp/seminar/2001fall2/sub8/

発展課題 HashMapのソースコードを読んで、 実装が、「空き番地法」「分離連鎖法」のどちらでなされているかを答えなさい。

冬休みの課題 自分の作るシステムをCUIベースのアプリケーションで完成させてください。 CUIができれば、Webアプリにするのはあとはそう難しくありません