m分割検索法と最適化条件
7
0
0
全文
(2) 近 畿 大 学 短 大 論 集Vol34,Nα1 §1.は. ク ス を 指 標 に し、 適 合 した フ ィ ー ル ド内 の 情 報 を. じめ に. 近 年 、 コ ン ピ ュ ー タ を 取 り巻 く環 境 が 大 き く変. 読 み と る も の で あ る。 逐 次 法 と2分. 化 して き た 。 一 つ は 、1GHz以. 上 の 高 ク ロ ッ クで 動 作 し、. 探 索 法 の処 理 系 は簡 単 で あ るが 、. 一 般 に 逐 次 法 は2分. 探 索 法 に 比 べ 処 理 効 率 は低 く、. 画 像 や 音 声 を 中 心 に した マ ル チ メ デ ィ ア 処 理 を 高. そ れ ぞ れ デ ー タ数nとlog,nに. 速 に 行 う た め の 命 令 を 持 っMPUの. 間 が 必 要 に な る。 一 方 、 ハ ッ シ ュ法 で は 検 索 速 度. 開 発 、MPU. よ り も 多 くの 半 導 体 を 集 積 し 、3.2Gテ secも. の 高 速 で3D画. ク セ ル/. 像 処 理 の 可 能 なGPUの. 発 、 高 速 大 容 量 のHDD、. 開. 高 速 読 み 書 きの 可 能 な. RDRAMやDDRSDRAMの. は 前2者. 比 例 した 検 索 時. と比 べ 速 い が 、 デ ー タ検 索 用 の デ ー タ テ ー. ブ ルの 作成 が必 要 に な る た め処 理 工 程 が複 雑 に な る。. 開 発 な ど コ ンピュー. そ こで 、本 論 文 で は 今 日使 用 され て い る検 索 方. タ の 基 本 性 能 は 確 実 に 向 上 して い る。 も う 一 方 は ネ ッ トワ ー ク 環 境 で あ る。. 法 を改 良 したm分 割 検 索 法 の処 理 速 度 の測 定 を行. 新 た に 開 発 さ れ た 高 速 ネ ッ トワ ー ク の た め の 通. い、 単 純 な処 理 系 で な お かっ 高 速 検 索 の可 能 なm. 信 技 術 に よ り 、 通 常 回 線 を 利 用 す るADSL、 用 回 線 に よ るCATV、. 専. 光 フ ァイ バ ー通 信 網 を 使. 分 割 処 理 プ ロ グ ラ ムを検 討 す る。 さ らに 、情 報 検索 の た め の最 適 化 条 件 を検 証 す. 用 し た 光 フ ァ イ バ ー ネ ッ ト ワ ー ク やFTTH. る。 そ の た め の準 備 と して、 逐 次 法 プ ロ グ ラ ムや. (FibertotheHome)、. さ らに衛 星 回 線 を使 用 す. 2分 探 索 法 プ ロ グ ラ ムで使 用 され る各 命 令 の処 理. る も の ま で 、 高 速 ネ ッ トワ ー ク 環 境 が 利 用 可 能 に. 時 間 を 計 測 し、 そ の結 果 か ら高 速 検 索 が可 能 な処. な っ て き た。 同 時 に 、 高 速 サ ー バ の 導 入 に よ り、. 理 系 の 考 案 とそ の最 適 化 条 件 を検 討 す る。. 多 くの 情 報 源 を 検 索 対 象 と す る こ と が で き、 居 な が らに して 高 品 位 の 情 報 を 短 時 間 に 収 集 す る こ と が で き る よ う に な って き た。 こ の よ う に 、 高 性 能 化 さ れ た コ ン ピ ュ ー タ と高. §2.一. 般 的 な 検 索 法 に よ る検 索 時 間 の 測 定. 各 検 索 プ ロ グ ラ ムを使 用 した場 合 の検 索 時 間 及 び各 命 令 の 処理 時 間 を 測定 す るた め に、 次 の機 器. 速 ネ ッ トワ ー ク を 利 用 す れ ば 、 こ れ ま で 多 くの 時. と プ ロ グ ラ ム を 使 用 し た 。 な お 、BASICは. 間 を 費 や して い た デ ー タ検 索 も比 較 的 短 時 間 に 処. タ ー プ リ タ ・コ ンパ イ ラ形 式 で あ り、 各 検 索 プ ロ. 理 で き る よ う に な る。 特 に 各 種 デ ー タ ベ ー ス を 利. グ ラ ム に 用 い る 命 令 は で き るだ け 同 じ もの と した。. 用 した デ ー タ 検 索 や 情 報 抽 出 は 、 今 後 の 研 究 活 動. 表1使. イ ン. 用 した 機 器 お よ び プ ログ ラム. に は 不 可 欠 な もの で あ る。 しか し、広 域 ネ ッ トワ ー ク や 巨 大 な デ ー タ ベ ー ス に よ り活 用 で き る情 報 源 が 増 大 す る こ と は 、 逆 に 検 索 領 域 や デ ー タ量 を 爆 発 的 に 増 加 さ せ る こ と に な る た め 、 高 速 コ ン ピュ ー タ を 使 用 し た と して も、 そ の 処 理 時 間 も増 大 す る こ とが 予 想 され る。 その た め、 高 速 コ ンピ ュ ー タ. 表1に. 各 命 令 の 処 理 時 間 を 計 測 した 結 果 を 示 し. を 有 効 に 利 用 す る た め の 効 率 の 良 い情 報 検 索 用 ア. た 。 時 間 測 定 に はTime$関. ル ゴ リズ ムが 必 要 に な る。. 間 分 解 能 は1秒. 一 般 に 使 用 さ れ る デ ー タ検 索 用 ア ル ゴ リ ズ ム に は 、 逐 次 法 、2分. 探 索 法 、 ハ ッ シ ュ法 な どが あ る。. い ず れ の方 法 も イ ンデ ッ ク ス を設 け 、 そ の イ ンデ ッ. 数 を用 い た た め 、 時. で あ る。 有 効 数 字 を3桁. め に 計 測 は108∼10iO回. 行 っ た。. に す るた.
(3) 黒 田:m分. 表2各. 命令 の処理時間. 割 検 索 法 と最適 化 条 件. な お 、 処 理 に 多 く の 時 間 を 必 要 と す る結 果 表 示 命 令 は 、 プ ロ グ ラ ム の 動 作 確 認 後 に 削 除 した 。 さ ら に 、 検 索 デ ー タ は 昇1順 と した 。 表2の. 結 果 を 用 い る と 、 逐 次 法 プ ロ グ ラ ム と2. 分 探 索 法 プ ロ グ ラ ム で の 検 索 時 間 は、 デ ー タ件 数 をn、. 繰 り 返 し回 数 をRep、. を τFOR、 τA、. 各命 令 の処理 時間. τIFと す る と 、 デ ー タ群 の 最 後. に 検 索 デ ー タ が あ る場 合 、 す な わ ち 最 大 時 間 は. な お 、 比 率 は繰 り返 し命 令 を1と した場 合 の も. T逐 次 冨Rep・. の で あ る。. τFoR十Rep・n・(τFoR十. =Rep・(τFoR十n・(τFoR十. τ 【F))…(1). 今 回 使 用 した シ ス テ ムで は、 複 数 の 処 理 を 行 う 関 数 演 算 命 令 が最 も多 くの処 理 時 間 を 必 要 とす る. T2探. 索=Rep・(2τA十. こ とが 分 か った。 これ らの 命 令 か らな る逐 次 法 プ ロ グ ラ ム と2分 探 索 法 プ ロ グ ラ ム は次 の もの を使 用 した。 〈逐次法プ ログラム1>. τwHILE十log2n・. (τ[NT十3τIF))(2) と な る 。 (1)(2)式. を 、 表2よ. <2分. τIF). り. 探 索 法 プ ログ ラ ム2>.
(4) 近 畿 大 学 短 大 論 集Vo憾4,No.1. ム1・2は. 一 般 性 を 保 持 し て い る こ と が 示 され た 。. ま た 、 今 回 の シ ス テ ム に お け る 検 索 速 度 は 、2分 探 索 法 が 逐 次 法 に 比 べ 約90倍. と近 似 し、 τW肌Eを. 無視す ると. §3.検. 程 度 高 速 で あ った。. 索 法 の最 適 化 条 件. 検 索 時 間 は デ ー タ数 に 大 き く依 存 す る こ と が § 2の 結 果 示 さ れ た 。 そ こ で 、 検 索 の た め の 判 断 処 理 の 前 段 処 理 と し て 、 検 索 対 象 と な る デ ー タ数 を 検 索 デ ー タ の イ ン デ ッ ク ス を 指 標 と し たm群. のサ. ブ デ ー タ群 に 分 け る こ と に よ り、 見 か け上 検 索 時 間 を 減 ら す 判 断 処 理 を 設 け る 方 法 を 検 剖 す る。 こ の よ う に 、 検 索 時 間 は デ ー タ数 に 依 存 す る こ と が 分 か っ た 。 こ こ で 、lo藻nは. 前判定反復処 理. 下 記 逐 次m分 ク ス でm個. で の 繰 り返 し回 数 で あ る。 そ こ で 、 ⊥ 記 プ ロ グ ラ ム1・2を. 口∫能 な 限 り、 同 一 の 条 件 で 比 較 を す る た め に 、. 使 用 した場 合. 割 法 プ ロ グ ラ ム3に. お いて イ ンデ ッ. に 分 類 さ れ た サ ブ デ ー タ群 に 対 し、 日. 的 とす る 検 索 情 報 が ど の デ ー タ群 に 属 す る か を 前. の 検 索 時 間 の デ ー タ数 依 存 性 を測 定 し た。 結 果 は、. 処 理 で 行 う以 外 は 、 前 述 プ ロ グ ラ ム1・2と. Fig1、F噛2で. 命 令 で 構 成 し、 そ の 基 本 的 構 造 も ほ ぼ 同 じ も の と. あ る阜 な お 、 検 索 デ ー タ は(最. 終 デ ー タ ー1)番. 同 じ. した 。. 目 の デ ー タ と した。. Spを デ ー タ群 の分 割 数 と し、 逐 次 法 に よ る結 果 で あ る式 ㈲ に表2の 結 果 を適 応 す る と、m分 割 法 に よ る処 理 時 間T呂pは 、. Fig.1逐. 次 法 に よ る 検 索 時 間 の デ ー タ 数依 存 性. と近 似 で き 、 分 割 数 と デ ー タ数 に 依 存 す る 関 数 に な る。 こ こ で 、C、Dは. シ ス テ ム に よ り 決 ま る定. i数で 、C=7A・Rep、D冨4A・Repで. Fig、22分. 探 索 法 に よ る検 索 時間 の デ ー タ数 依 存 性. 検 索 時 間 は 、 逐 次 法 で は デ ー タ数nに 分 探 索 法 で はlo齢nに. 、 ま た2. 比 例 す る こ と が 示 され た. こ とか ら、 今 回 の 検 索 時 間 測 定 に 用 い た プ ロ グ ラ. さ らに. あ る。.
(5) <逐 次m分. そ こ で 、Spを. 割 法 プ ロ グラ ム3>. 変 数 と して プ ロ グ ラ ム3を. <2分. 探 索m分 割 法 プ ロ グラ ム4>. 用い. て検 索 時 間 の 分割 数 依 存 性 を 計 測 す る と、近 似 式 {7)⑧ の 特 性 を 示 すFig.3の. 結 果 を得 た。 ま た 、 ㈲ 式 よ りm分 は 、dT/dsp=Oよ だ し、Zは. Tmin≒. Fig.4は Fig.3逐. 次m分. 割 法 に よ る検 索 時 間 の 分 割 数 依 存 性. 割 法 に よ る検 索 時 間 の極 小 り、 次 の よ う に 旭 っ た 。 た. 定 数 でG.76で. あ つた。. 伍. (9〕. 、 デ ー タ数 自を 変 数 と し た 場 合 の 、 検. 索 最 小 時 間Tminを. 示 した もの で あ る⇔.
(6) 近 畿 大 学 短 大 論 集Vol.34,N⑪,1. 式 翻 が 示 さ れ た 。 実 測 し た 計 数Zの で あ り 、 言1'算 値0.76と. 値 は α59. 比 較 的良 い 一致 を み た。. Fig.5近. Fig.4最. 適 分 割 に よ る 検 索 時 間 の デ ー タ数 依 存 性. プ ロ グ ラ ム1で 5000に. 似 式 ㈲ に よ る 検 索 時 間 の シ ミ ュ レー シ ョン結 果. の 結 果 と比 較 す る と 、 デ ー タ 数. お い て9⑪0:55と. な り約150倍. の処 理効. 率 の 改 薔 が 認 め られ た 。. 一 方 、 プ ロ グ ラ ム2にm分. よ る検 索 時 間 の 近 似 式 は 、 次 の よ う1. +﹂. グ ラ ム4に. 割 法 を導 入 した プ ロ F喧、ε2分 探 索m分 割 法に よ る検 索 時間 の分 割 数依 存性. な った。. 以 上 の結 果 、m分 割 逐 次 法 は2分 探 索 法 とほ ぼ 同 程 度 の 処理 効 率 に ま で改 良 が可 能 で あ る こ とが 示 され たが 、総 合 的 に構 造 の単 純 な2分 探 索 法 が 優 れ て い る こ とが 示 さ れ た。 そ こで 処理 効 率 の 高 い2分 探 索 法 を基 本 に し、 ︺ O 1 ︹. デ ー タ分 割 が よ り有効 に作 用 す る処 理 法 を試 作 し た。m分 割検 索 プ ロ グ ラ ム5を 作 成 し、 これ を 川 近 似 式qO}に 基 づ く シ ミュ レー シ ョ ンを 行 う と、 Fig.5が. 示 す よ う に 、Spの. 変 化 に 対 し顕 著 な 極. い同 様 の条 件 で検 索 時 間 を測 定 した。 検 索 す る デ ー タの 位 置 に よ り検索 時間 は異 な り、. 小 は 認 め られ な か っ た 。 ま た 、 測 定 結 果 は 次 の. プ ロ グ ラム に対 し特 異 的 な位 置 に あ る デ ー タに 対. Fig.6に. な り 、 極 小 と な る検 索 時 間 が 導 入 以 前 の. して は分 割 数 の 増 加 に 対 し処理 時 間 も増 加 し分 割. 結 果(図. 中O、. の効 果 は認 め られ 慧 か った。 しか し、 特 異 的 な 位. 口)に. 比 べ 平 均 的 に 長 くな り 、m. 分 割 法 に よ る 処 理 速 度 の 著 し い 向 上 は 認 め られ な. 置 に な い デ ー タに対 して は分 割 の効 果 は顕 著 で 、. か っ た.. 分 割 数 哩で極 小 の検 索 時 間 を記 録 した。 これ は、m分 割 法 の 基 本 形 が2分 探 索 法 で あ る た め、2分 探 索 法 で 、 デ ー タ数 を1/10に させ るた め に は4∼5回. 減少. の検 索処 理 が必 要 に な る. 特 性 が現 れ た もの と思 わ れ る。 こ の結 果 か らm分 割 法 を適 用 す る場 合 に は、 分 割 数 は 些∼5分 割 が 効 果 的 で あ る とい え る。.
(7) 黒 田;m分 と 、(最 終 位 置 一1)番 <m分. 割 法 プ ログ ラ ム5>. 割 検 索 法 と最 適 化 条 件. 口の デ ー タ と任 意 の 位 置. に あ る デ ー・タ を 検 索 し た 場 合 や 分 割 数 に よ り検 索 時 間 に 差 は あ る もの の 、 今 回 の 測 定 に 用 い た シ ス テ ム で 最 も処 理 効 率 の 優 れ て い た2分 と比 較 して 、 平 均 的 に 約3倍. 探 索 の場 合. の 処 理 効 率 の改 善が. 確 認 で き た 。 ま た こ の 結 果 は 、 逐 次 法 の 約30⑪ 倍 で あ っ た。. §4.ま. とめ. 既 存 の逐 次 法 と2分 探 索 法 を組 み合 わ せ 、使 用 す る シス テ ム の各 命 令処 理 時 間 を計 測 す る こ とに よ り、 高 速 で デ ー タの検 索 が 可能 な処 理 系 の 開発 を試 み た。 プ ロ グ ラム の構 造 は単純 で あ るが 、 全 デ ー タを m群 か らな る サ プデ ・ 一タ群 に分 け る こ とに よ り、 検 索 対 象 で あ る デ ー タ数 を 見 か け上減 少 させ る こ とが で きた。 そ の結 果 、 検索 処 理 時 間 は逐 次 法 に 比 べ 約300倍 、2分 探 索 法 に比 べ3倍 程 度 の 処 理 効 率 の 改 善が 確認 され た。 今 後 は、m分 割 法 を改 良 し最 適 化 条 件 を 検 討 す る予 定 で あ る。. 参考文献 1. た だ し現 実 に は 、処 理 行 程 や処 理 内容 に よ り、 Fig,7が 示 す よ うに検 索 時 間 最 小 を示 す 分 割 数 は. N88-BASICに 河 西 朝雄. 2. よ る は じめ て の ア ル ゴ リズ ム 技 術 評 論 社(199B)111-304. 数 学 公 式1・. 皿 ・皿. 森 口繁一 ほか. 変 化 した もの と思 わ れ る。. 岩 波 書 店(1979)1-47、2』-217、. 268-一 且呂5. 3. プ ロ グ ラ ム 事 典(第1巻) TF林 雅 英. 4. 5. 6. 技 術 評 孟偉i相1(1993)123-16岨. 平林 雅英. 技 術 評 論 社(1993)41-6L、75-90. ア ル ゴrJズ. ム事典. 奥村 晴彦. 技 術 評 論 社(工992)IO1一. BASIC/9日f且. 言tu5ε ゴ5エTlalluaI. 船 山 竣 彦KSP(19盟)90-m5 7. Fig.7m分. BASIC/9剖. 且8tRoforenoεmanu乱1. 船 山 俊 彦KSP(1992)10-3⑪5. 割 法 に よ る検 索 時 間 の 分割 数 依 存 性. m分 割 法 と2分 探 索 法 で の処 理 効 率 を比 較 す る. 一29一. 、230-267. プ ロ グ ラ ム 事 典(第2巻). 認9、42⑪.
(8)
関連したドキュメント
ポートフォリオ最適化問題の改良代理制約法による対話型解法 仲川 勇二 関西大学 * 伊佐田 百合子 関西学院大学 井垣 伸子
定率法 17 条第１項第 11 号及び輸徴法第 13
11 Properties of a Complex Logistic Equation and... 13 Properties of a Complex Logistic
静岡大学 静岡キャンパス 静岡大学 浜松キャンパス 静岡県立大学 静岡県立大学短期大学部 東海大学 清水キャンパス
送料 コスト
（大防法第 18 条の 15、大防法施行規則第 16 条の 8、条例第 6 条の 2、条例規則第 6 条の
静岡大学 静岡キャンパス 静岡大学 浜松キャンパス 静岡県立大学 静岡県立大学短期大学部 東海大学 清水キャンパス
3.3.2.1.3.1 設置許可基準規則第 43 条第 1 項への適合方針 (1) 環境条件及び荷重条件（設置許可基準規則第 43 条第 1 項一）.
