『人工知能が私たちを滅ぼすのか --- 計算機が神になる100年の物語』 読了
1．概要
下記書籍を読了した．備忘録として，内容の簡単なまとめを記載する．
なお，適当にまとめたので，後日ちょいちょい加筆修正する予定．
人工知能は私たちを滅ぼすのか―――計算機が神になる100年の物語
- 作者: 児玉哲彦
- 出版社/メーカー: ダイヤモンド社
- 発売日: 2016/03/18
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (3件) を見る
2．各章まとめ
全体の流れとしては以下のような感じ．
- 大型コンピュータができるまで
- パーソナルコンピュータができるまで
- インターネット，ウェブ，クラウドができるまで
- スマートフォンができるまで
- AI研究の急激な進化
- 今後のコンピュータ関連技術の進化予想と社会の変化予想
- 今後の人工知能の進化予想
なお，6，7章に関しては，予想という面が強く，普遍的な知識や歴史ではないため，まとめは省略した．気になる方は買って読んでくれ．
2．1．大型コンピュータができるまで
2．1．1．流れ
その後ブール代数を元に，クロード・シャノンによって情報理論が確立される．
第二次世界大戦において，アラン・チューリングは情報理論に基づいたチューリングマシンという概念を提唱する．これにより，ナチスドイツのエニグマ暗号の解読に成功し，連合軍が勝利を収める．
また，ジョン・フォン・ノイマンにより，チューリングマシンの具体設計である，ノイマン型コンピュータが提案される．その後，史上初のコンピュータであるENIACを作成した．
こうしてコンピュータはできたが，技術的なハードルもあり，サイズは大きいものばかりだった．ここに大型コンピュータは誕生した．
2．1．2．用語
●ジョージ・ブール
人間の論理的思考を数式で表現できるブール代数という概念を作った人．
・ブール代数…
人間の思考は0，1の組み合わせで表現できる，とした数学の概念．
ブール代数を元に，電気回路がスイッチのON，OFFの切り替えで
制御できることを発見．それを発展させて情報理論を提唱する．
全てのコンピュータの元となるチューリングマシンという概念を生み出した人．
第二次世界大戦においては，ナチスドイツが使用したエニグマ暗号の解読に成功．
内部状態を保ち，入力により内部状態が変化し，変化は内部状態に依存する
マシン．
AIが十分な賢さを持っているかをテストする．コンピュータを介した対話にて，
被験者に人間とAI双方とやり取りを行ってもらい，AIだと気付かなければ合格．
ノイマン型コンピュータを提案した人．
第二次世界大戦においては，原爆の開発に従事．
・ノイマン型コンピュータ…
中央演算装置，記憶装置，入出力から構成されるコンピュータ．
2．2．パーソナルコンピュータができるまで
2．2．1．流れ
【人工知能】
人工知能研究は，アラン・チューリングが「人の心も計算の繰り返しでできている」という発言に基づき，盛んに行われる．
クロード・シャノンやマービン・ミンスキー，ジョン・マッカーシーなど多くの研究者により研究は進められるが，『フレーム問題』や『中国語の部屋』を代表とする，コンピュータの性能が足りない，概念を獲得する方法がわからない，といった問題が露わになり，人工知能の研究は頓挫する．
【パーソナルコンピュータ】
バネーバー・ブッシュにより，『メメックス(Memory Extension)』という情報検索の概念が登場する．この概念は『人の機能をコンピュータによって拡張する』という側面も持ち合わせていた．
この概念に影響を受けたジョゼフ・リックライダーは，同じく影響を受けたダグラス・エンゲルバートに対して研究資金を提供する．
ダグラス・エンゲルバートはスタンフォード研究所内に強化研究センター(略称ARC，通称ノア)にて，対話コンピュータ，マウス研究，文書の相互リンクなどパーソナルコンピュータやウェブに繋がる研究を進めた．
その後，ダグラス・エンゲルバートのデモを見ていたアラン・ケイが，ダイナブックを提唱し，パーソナルコンピュータという言葉が生まれた．
パーソナルコンピュータの流れを加速させた要因として，アップルの登場がある．
大型コンピュータは政府や大企業，学術機関などしか使えない貴重なものだったため，中央集権的な体制による個人への抑圧のシンボルとなっていった．
西海岸では当時の政治的・経済的背景に反発するカウンターカルチャーが芽生えており，このカウンターカルチャーの方法論などを記載していた雑誌が『ホール・アース・カタログ』である．
カウンターカルチャーの雑誌ではあったが，コンピュータに関しては肯定的に取り上げられており，コンピュータは抑圧のためのものではなく個人の抵抗のための道具である，といった主張をしていた．
この主張に影響されたスティーブ・ジョブズはAppleⅠを作成し，コンピュータの存在を世界に広めることになった．
2．2．2．用語
人工知能研究者．AIという言葉を初めて使ったと言われている．フレーム問題を
提唱した．
フレーム問題…
コンピュータリソースは無限ではないという点から，人工知能が考えなければ
ならない範囲を絞る必要があるという問題．
●バネーバー・ブッシュ
『メメックス(Memory Extension)』という情報検索の概念を提唱した人．
文献がフィルムに保存されており，操縦桿のようなデバイスを用いて，文献間を
サーフィンできる仕組み．
●ダグラス・エンゲルバート
現在のパーソナルコンピュータやウェブの大元を作った人．全てのデモの母．
●スチュアート・ブランド
カウンターカルチャーの象徴とも言える，『ホール・アース・カタログ』を
立ち上げた人．
ダイナブックを提唱した人．また，暫定版ダイナブックを実際に作成し，これが
マッキントッシュやWindowsの大元となった．パーソナルコンピュータという言葉を
作ったのもこの人だと言われている．
想像を伴った学びを支援するメディア．A4サイズ程度の大きさが理想とされた．
2．3．インターネット，ウェブ，クラウドができるまで
2．3．1．流れ
【インターネット】
パーソナルコンピュータの流れができた頃と同じ頃に，ジョゼフ・リックライダーによってコンピュータ同士を繋げる銀河間ネットワークが提唱される．
しかしながら，銀河間ネットワークを実現しようとすると，各コンピュータを個別にネットワーク接続することになり，台数が増える度に組み合わせが爆発していく．
そのため，ネットワークとネットワークを繋げるインターネットを実現する必要があり，そこからドナルド・デービスによってパケット交換方式が編み出された．このパケット交換方式によるインターネットは，エンドツーエンド原理を用いている．
こうしてできたインターネットの原型をARPANETという．
その後，インターネットは急激に成長していくが，それを説明する法則として，ロバート・メトカーフがメトカーフの法則を提唱した．
【ウェブ】
ウィリアム・ギブスンの『ニューロマンサー』という小説が元となり，サイバースペースがインターネット上に作成され始める．いわゆる掲示板的なもの．
『ホール・アース・カタログ』を作ったスチュアート・ブランドは，『ホール・アース・エレクトリック・リンク』，通称WELLと呼ばれたサイバースペースを作成した．ここからカウンターカルチャーは，サイバーカルチャーへと転換されていく．
その頃，素粒子物理学研究所セルンで研究文書を手軽に参照できる『ワールド・ワイド・ウェブ』，通称wwwがティム・バーナーズ＝リーによって作成された．
wwwは脳のように分散型で偶発的な連想が発生するようなアーキテクチャで作成されており，エンドツーエンド原理を用いている．
このwwwは，ティム・バーナーズ＝リーが創設した標準化団体の活動やエンドツーエンド原理によるコンテンツの増大，専用ブラウザであるモザイクの登場などにより利用者が増え，メトカーフの法則に従って価値が増大した．
モザイクの登場に危機感を覚えたビル・ゲイツは，マイクロソフト製品のインターネット対応を決め，ここからインターネットやwwwが本格的に普及した．
【クラウド】
インターネットやwwwが普及したことにより，コンテンツ数が莫大なものになったため，コンピュータによる効率的な自動整理・検索を行う検索エンジンが必要になった．
この検索エンジン分野で高い人気を誇ったエンジンが，ラリー・ペイジ，セルゲイ・ブリンらのエンジンだった．この二人は後にこのエンジンを元にGoogleを創業した．
Googleは，検索エンジンやGメールといったサービスのために，膨大なサーバを保有するようになる．その結果，サーバで動いているソフトをブラウザを通して見る，という今までにないコンピュータの使い方をするようになった．これを，空の上の雲の世界でコンピュータが動いているように感じることから，クラウド・コンピューティングと呼ぶようになった．
2．3．2．用語
●ジョゼフ・リックライダー
銀河間ネットワークを提唱した人．コンピュータのジョニー・アップルシードと
呼ばれている．
●ドナルド・デービス
パケット交換方式を考えだした人．
パケット交換方式…
別のコンピュータを経由して目的のコンピュータにデータを届けるデータ交換方式．
ネットワーク研究者．
ネットワークの価値は接続端末数の二乗に比例する，とした法則．
SF作家．サイバーパンクSFというカテゴリを作った．
●ティム・バーナーズ＝リー
エンジニア．wwwを開発し，wwwの標準化団体を創設した．
マイクロソフト創業者．
グーグルの創業者．学生時代に検索エンジンを作成した．
2．4．スマートフォンができるまで
2．4．1．流れ
マッキントッシュの発売で波に乗っていたアップルだったが，後続の商品が続かず，会社内で軋轢の原因となっていたスティーブ・ジョブズは，ジョン・スカリーによって解雇されてしまう．
その後，ジョン・スカリーによって，パーソナル・デジタル・アシスタント，通称PDAが提唱され，それを実現したニュートンが販売されるも，精度の悪さなどから人気は出なかった．
スティーブ・ジョブズは，アップルを追い出された後，ネクスト，ピクサーといった会社を経営して結果を出す．
アップルはニュートンが爆死したこと，ジョン・スカリーが去ったこと，次期OSの開発が行き詰まっていたことなどから経営が難航しており，苦肉の策で次期OSを外部から買収することで解決する．その会社がネクストであり，スティーブ・ジョブズはアップルに舞い戻ることになった．
しかし，アップルの前にまたしても壁が立ちふさがる．当時消費者間でトレンドになっていたデジタル音楽に，アップル製品は対応していなかった．
アップルは対応策として，iTunes(音楽ソフト)のリリースや『デジタルハブ』構想の提唱，iPod(音楽デバイス)の発売などを行った．
その頃日本では，携帯電話向けインターネットサービスとして，夏野剛が開発したiモードが人気を博していた．iモードはマービン・ミンスキーの『心の社会』に影響を受けて，キャリアやコンテンツ，ユーザを巻き込んで盛り上がるような仕組みで作られていた．
このiモードのブーム，そしてジェフ・ホーキンス率いるパームが開発した高精度なPDAの登場，パーソナルコンピュータと同じ入力装置をもつ携帯電話の登場などを受けて，携帯電話とPDAの融合は進んでいく．そんな中パームが初めて携帯電話とPDAを融合させた商品を発売し，スマートフォンの時代がやってきた．
その後アップルによって，iPhoneが発表される．電話・音楽デバイス・コンピュータなどあらゆる機能を兼ね備えたiPhoneは，人間が常にクラウドに繋がっている世界を到来させた．
2．4．2．用語
アップルの元CEO．アップルでAppleⅠやマッキントッシュの作成を指揮するも，
一度アップルを追い出され，その後ネクストやピクサーを経営した後，アップルに
舞い戻った．デジタルハブ構想を提唱した．
デジタルハブ構想…
音楽だけではなく，写真や動画などの個人コンテンツも記録し，
整理し，利用する，とした構想．
アップルの元CEO．パーソナル・デジタル・アシスタントを構想し，
ナレッジ・ナビゲーターというコンセプトビデオを公開した．
パーソナル・デジタル・アシスタント…
人工知能のエージェントとの音声の対話による，情報検索や
スケジュール調整を行える電子秘書
●夏野剛
iモード開発者．『心の社会』に影響を受けながらiモードを開発した．
心の社会…
心とは，単一のものではなく，色々なエージェントが強調したり，対立したりして，
全体で見ると意味を持つ，社会のようなものである，といった考えを説いた
ミンスキーの名著．
パームという会社を創設し，同名の高精度PDAを開発した．
2．5．AI研究の急激な進化
2．5．1．流れ
ノーバート・ウィナーにより，生物のように賢く振る舞う機械を研究するサイバネティクスという学問が作られた．
このサイバネティクス学問の立ち上げの際に，ウォーレン・マカロック，ウォルター・ピッツらが招集され，彼らが発表したニューラルネットワークという手法が人工知能の世界に持ち込まれる．
ニューラルネットワークは，人間の神経細胞における情報伝達の仕組みを簡単な数学モデルにしたものだった．このモデルによってチューリングマシンを作れることから，人間の脳も機械で表現できることが示された．
その後，フランク・ローゼンブラットにより，ニューラルネットワークを三層で表現する，パーセプトロンという手法が発表される．
しかしながら，マービン・ミンスキーにより，パーセプトロンは分布図を直線で分けられるようなものにしか適用できないという欠点が指摘され，人工知能の研究はまたしても行き詰まる．
その後，ジェフリー・ヒントンにより，パーセプトロンの欠点を打ち破ったニューラルネットワーク，ディープラーニングの原型が発明される．
しかし，この手法は膨大な計算がかかること，そしてそもそも機械学習用のデータを集めることが大変であることから，発明当時は日の光を見ることはなかった．
その後，コンピュータの性能向上，ウェブの膨大なデータなどに後押しされて，ディープラーニングが発表された．
ディープラーニングは色々なコンテストやプロジェクトで結果を出している．
【応用例の登場】
ジョン・スカリーが発表したナレッジ・ナビゲーターに影響されたアダム・チェイヤーは人工知能アシスタントの研究を行い，後にiPhoneに搭載されるSiriを開発した．
Siriの特徴として，正確な音声認識技術と，意味解釈技術がある．音声認識技術はレイ・カーツワイル率いるニュアンスという会社のものを使用していた．意味解釈技術は独自のものだった．
IBMは自社で進めていた人工知能研究の集大成として，『ジェパディ！』というクイズ番組に，ディビッド・フェルーチが開発したワトソンという人工知能を参加させる．仕組み自体はエキスパートシステムやニューラルネットワーク，キーワード検索，その他の機械学習技術など既存技術を組み合わせたものだが，入力データにウェブの膨大なデータを使用するなど，学習に時間を割くことで，最終的にクイズチャンピオンに勝利するまでに成長する．IBMはこの結果により，人工知能は十分に実用的なレベルに達したと判断し，医療分野や料理分野に応用している．
Siriやワトソンは人工知能ではあるものの，あくまで入力されたパターンに応じて反応しているにすぎず，入力されたデータから自ら概念を学ぶ，といったことはできていなかった．
しかし，ディープラーニングの登場により，そういったものも現れた．
ジェフリー・ヒントンと同じグループで研究していたアンドリュー・センはグーグルブレインというディープラーニングを用いたプロジェクトにおいて，入力したデータから自分で概念を学ぶ人工知能の開発に成功した．
また，ディープマインド社は，囲碁チャンピオンに囲碁で勝利する人工知能の開発をディープラーニングを用いることで成功している．
2．5．2．用語
●ノーバート・ウィナー
ノイマンの時代の研究者．サイバネティックという学問を作った．
●ウォーレン・マカロック，ウォルター・ピッツ
神経細胞の伝達の仕組みに基づく計算手法である，ニューラルネットワークを
発明した．
●フランク・ローゼンブラット
ニューラルネットワークの最初の実例であるパーセプトロンを発明した．
●ジェフリー・ヒントン
従来のものよりも多層で複雑な情報にも対応できるニューラルネットワーク．
出力層から入力層に向かって出力のエラーが少なくなるように調整していくという，
脳が入力と記憶を照らし合わせる工程が含まれている．
●アダム・チェイヤー
人工知能研究者．Siriを開発した．
Siriで使われている音声認識技術を開発した．また，シンギュラリティの到来を
提唱した．
シンギュラリティ…
その後起こることについて，持ちうる知識では予想できなくなる瞬間のこと．
一般には，人工知能が人類を超える瞬間と言われている．
●ディビッド・フェルーチ
自然言語のエキスパート．ワトソンを開発．
●アンドリュー・セン
ディープラーニング研究者．
3．感想
全体的に，聖書になぞらえた構成になっていた．こじつけかとおもいきや，意外と流れが一致していたりしてて，ほほぅって感じだった．
また，コンピュータの歴史に関して，当時の政治的背景などを交えながら説明していて，非常に分かりやすかった．
それと，AIに絞った話なのかなと思いきや，コンピュータの歴史を一通りなぞる感じだったので，勉強になった．
技術的な学びとかはないけど，AI関連の読み物としてはかなり良質な部類に入るのではなかろうか．AI関連の読み物はこれしか読んだことないんだけど．
買っても損はないと個人的には思ってる．
どうでもいいが，7章にちょろっと出てくる脳科学におけるホムンクルスは，大脳新皮質における各機能マップの面積を元に人型モデルを作ってみたら，頭でっかちで身体が小さいモデルができた，という所から来ていると記憶しているので，この本に記述されているホムンクルスの捉え方はちょっと違うような気もする．色んな見方があるということかしらね．
なお，各章まとめは，書籍内の面白い話とか細かい話とか誰と誰が繋がっているのかとかを大分はしょっています．その辺が気になる方は是非書籍を購入してください．
今度こそ
三日坊主すらできなかったけど、とりあえずアウトプットを続けていこうという意思を示すために、全体公開＋ブログ名の変更を行った。
基本的に備忘録であり、他人に見せるものではないので、書き方とかも適当だけど、誰かに見られているかもしれないという意識は、曖昧な知識を記述する可能性を低くしてくれると思う。
とりあえず当分は読んだ本とかについてまとめていく。
ブログ説明文にもあるが、今までの傾向上一度更新したら当分更新しない（気がする）。
備忘録ブログとして再スタート
前回の記事を見てみたら、三日坊主にならないようにしていたようだった。
が、見事に三日坊主になっていましたウケル。
唐突だが、最近気付いたことがある。
それは勉強の方法についてだ。
私は基本的に勉強ができない人間で、中高の成績は一夜漬けの恩恵、大学の成績は友達の恩恵だった。そんな自分も社会に出る直前に勉強の大事さに気づき、勉強をしてみることにした。
現在やっている勉強方法は、単純に『本を読む』というものだ。お恥ずかしいことに昔から活字というものが大の苦手で、読んでいると眠くなってしまうし、読む速度も人の数倍時間がかかる。それでも、一冊にいくらかかってもとにかく最後まで読むようには心がけている。
この方法を取るようになってから、とりあえず本への抵抗は消えた。
また、数学関係の本を簡単なものではあるが読むようになったので、数学への抵抗も消えた。（専門的な記号などは未だに嫌だが…）
実際にどの本のどの知識が役に立ったか、などは特に思い出せないが、数学への抵抗がなくなったことは少なからずプログラミングに役に立っているような気がするし、その他の本も何となく役に立っている気がしなくもない（雑）
一方で、この方法は良くないことも何となくわかった。
無論本を読むことは悪くない。本を読んだだけで終わっているのが良くないのである。
インプットするだけしてアウトプットしていないので、記憶への定着率がかなり低い。また、勉強するにも体系的に学んだ方が効率が良いと思うが、今までどういう流れで学んできたかが記憶頼りになるので、途中で何やってたかわからなくなる。
ということでひとまずの結論として、備忘録をつけるべきだと思った。
本の内容を章毎に要約したものだったり、用語の意味だったりをどこかにアウトプットすべきだ。
ということでタイトルになるわけだ。
できれば読んだ記憶がある本を全てまとめ直していきたい所だ。
どういうカテゴライズでまとめるか、なども考えなければならない。基本的には技術カテゴリと本の題名をタグに残すべきかなぁ。
読書速度もあまりはやくないし、のんびりやっていくつもりだ。
今度こそ三日坊主にならないといいが…
プロコン小技
目指せ三日坊主越え
周期
こんな問題があったとします。
問題：
n人が集まってゲームをやっている。各人は各々1から順に番号を持っていて、ゲームは1,2,3...n,1...という風に繰り返される。k回のゲームを行い、各人は自分の番が回ってくる度にカードを引く。そして、そのカードの値を自分の持ち点としていく。人数とゲーム回数、カードの数列が与えられた時、ゲームが全て終わった時点で一番多く点を保持している人の番号を出力してください。
input
5 12 (n k)
1 2 3 4 5 1 2 3 4 5 1 2 (a1 ~ ak)
output
5
例なので、範囲に関しては考えないでください(
こういう問題だと
int a[n];
int tmp;
int count = 0;
while(k--){
cin >> tmp;
a[count] += tmp;
count = count>=n?0:count+1;
}
int maxc = 0, idx = 0;
for(int i = 0; i < n; i++){
if(maxc<a[i]){
maxc = a[i];
idx = i;
}
}
cout << idx << endl;
こんな感じになるでしょう。単純に考えたら。
無論悪いコードではないです。基本的にはこれで十分そう。
ただもうちょい綺麗にかけたりします。
こんな感じです。
int a[n];
int maxc = 0, idx = -1;
for(int i = 0; i < k; i++){
cin >> tmp;
a[i%n] += tmp;
if(maxc<a[i%n]){
maxc = a[i%n];
idx = i%n;
}
}
cout << idx << endl;
めんどくさかったので、最大を求める奴も入れてしまいましたが、入れないと
int a[n];
for(int i = 0; i < k; i++){
cin >> tmp;
a[i%n] += tmp;
}
こんな感じになります。大分綺麗になりましたね。
剰余を取る際に、割った数をnとすると必ず
0,1,2,3~n-1
という範囲で値を取ります。今回のように、渡される入力は一列だが問題としては特定の周期でループしている場合などは、一周辺りの数で剰余を取ることで、常に一定の感覚で同じ値を得られるということです。
なので、例えば1周期3で考えると、
1,4,7,10,13...
は全て剰余が1になります。
このように、数学的(算数的？)考え方を取り入れることで、ごり押しで実装するよりも美しく実装することが出来ます。
ごり押しが悪いわけではありませんが、ある一定の水準を超えた後は、コードに綺麗さを求めるのも楽しいですよ。
今日はここまで。ではまたの機会に。
プロコン小技
ブログの第一回目がもう4カ月くらい前ということで、三日坊主にすらなれなかったわけですが、卒論を前にして現実逃避がてら復活することになりました。
ということで、本日のネタはプロコンの小技です。
要素の比較
こんな問題があったとします。
問題：
要素数nの数列がm個与えられます。1つの数列の中で要素が重複している場合はYES、そうじゃない場合はNOを出力してください。
例：
input
3
1 2
1 2 1 3
4 5
output
NO
YES
NO
まぁ例えなので、nの範囲がわからんやんけとか数列の各要素の範囲わからんやんけとかmの範囲わからんやんけとか、諸々の突っ込みはなしでお願いします。
この問題を解く時に真っ先に思い浮かぶのは、いわゆる全探索だと思います。
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i==j) continue;
//ここでなんらかの処理
}
}
みたいな。こんなん思いつかんか。まぁどう考えても無駄が多いですね。何度も同じところを比較する羽目になりますし。1つのテストケースの中に要素数1万の数列が10とか入ってたりしてたら確実にダメです。
ではこれをどうすればいいか。これは簡単に解けます。
bool ex[n] (falseに初期化されてると思ってください)
とかを作っておきます。そして、
bool f = false;
for(int i = 0; i < n; i++){
if(ex[数列[i]]){
cout << "YES" << endl;
f = true;
break;
}
ex[数列[i]] = true;
}
if(!f) cout << "NO" << endl;
こんな感じで組みます。
添え字 = 要素
とすることで、定数時間でその要素の有無を確認できるわけですね。線形時間で解けるのでさっきのより早いです。1つのテストケース内に要素数1万の数列が10個あっても余裕で解けます。1万個あってもギリ解けるでしょう。前者のがo(n^2)で後者がo(n)です。
ということで、今回の話の本質は2つです。
- 添え字 = 要素という配列の使い方
- 同じ計算を繰り返さないよう工夫
前者はよく使う手法で、メモリがよほど切迫してない限りはわかりやすい実装をするためにも重要なものです。
後者もかなり重要な手法で、この考え方がDP(動的計画法)につながります。(多分)
皆さん早くて分かりやすい実装を心がけましょう。
今日はここまで。ではまたの機会に。
segment tree と union find tree
早速備忘録を活用する。
今日はsegment tree と union find treeについて学んだ。
union find treeは概念的なことだけ、segment treeは実際にCodeIQというサイトのクロッシング問題で使ってみた。
segment treeの感想としては、今までは実行速度等を気にせず気ままにコーディングしていたが、実行速度の重要性をしらしめられ、その上で探索の速度を考えると素晴らしいデータ構造だなぁという感じ。
といっても実際に解いた問題では速度はあまり出ず(というかその前までで配列で解いた方のが速かった)、実際に恩恵には授かれなかったんだけども。
まぁこれは自身のコーディングやアルゴリズムの組み方に問題があるのであって、segment treeそのものはやはり素晴らしい構造である。
70万くらいの入力でも、再帰のネストは20以下くらいで収まるし。
本当素晴らしい。
union find treeはわからん。概念だけで考えると、まぁ便利なこともあるんだろうなという感じ。クラスカル法やプリム法で使うらしいが、両方まだ使ったことないのでわからん。
今度やってみよう。
以下各データ構造の持つ機能と実現方法に関してメモ
【union find tree】
ノードとノードをある条件によってツリー構造にする際、どちらかを親として、もうひとつのノードから参照出来るようにする。
1 2 3 4 5 6 7 8
とあって1 2 3と4 5 6と7 8をグループにしたい。条件は値が大きい方が子ノードとする。って時に、
1<‐2<‐3みたいな感じで*rootとかが親を指すようにして1の*rootをNULLとかにすれば実現出来る。
これによって、
1、グループの統合が楽に出来る。
2、ノード同士のグループが一緒かどうかを判定出来る。
という利点が生まれる。
一方、グループの分割とかは出来ない。
前述した繋ぎ方は単純に繋いだだけだが、いくつもノードが縦に繋がっている場合は、各ノードの*rootを一番上の*rootに書き換えることで繋ぎなおして、経路を短縮したり、長さによってランク付けをして(ノード数1ならランク1、ノード数2ならランク2)、グループを統合する際の指標に使う等の工夫が出来る。
活用法は前述したクラスカルとかプリムとかだと思う。ここはまた後日ということで。
【segment tree】
あるデータ群n[i, j]があった時、二分木の要領で分割していく。
そして、その範囲の中の最大値だったり最小値、何かしらのカウントしたいデータと範囲をノードに持たせることで、rootから値を検索した時に、一番下のノードまで行かずに途中のノードで受け止めることが出来る。
実装方法は配列で出来る。
完全二分木なので最大要素数*2-1の配列を用意し(n+n/2+n/4...=2n-1)、0をrootとして順々にノードを格納していく。
０
１ ２
３ ４ ５ ６
みたいな感じ。子ノードには2n+1と2n+2でアクセスすることが出来、親ノードには(n-1)/2でアクセス出来るため、配列だとスムーズにアクセス出来る。
なお、rootに向かってデータの範囲が広がるので、データの格納等は子ノードからrootに向かって行う。
例えば前述したツリーだと、値の格納をスタートする位置は3の段(n-1でアクセス出来る。ちなみに今回の場合だと要素数は4で配列の長さは2*4-1で7ということになる)からで、そこから(n-1)/2で上の段にアクセスして最終的にrootまでアクセスしたら終了、といった感じ。
また、範囲は半開区間で行うと良いらしい。実際に便利だとは思ったが、個人的にはきっちり範囲を区切りたいのであんまり考えたくはないが。
基本的に再帰で簡単に実装出来る。
なお、別に配列じゃなくても実装出来るとは思う。が、私が勉強した時は配列で実装されていたため、ここでは配列での実装例を挙げておく。
以上が簡単なメモ書き。もっと利点とか欠点とかあるだろうが、まだまだ勉強不足なのでこんな感じで勘弁。
ちなみに勉強時に使ったのはこれ
http://www.slideshare.net/iwiwi/ss-3578491
書いてるiwiwiさんは、プロコンの世界ではかなりすごい人で、世界で戦っている人の一人。そこまで行けるよう頑張らねば。
【追記】
segment treeの所で、ノードに範囲も持たせると書いたが、範囲をわかりやすくするために一番下の段は一から順番に並べて、ない数値の場所は0かINFにしておけば、ノードに持たせなくても再帰の引数で管理できる。
てかこっちの方が普通の使い方ぽいので、そうした方が良い気がしなくもない。
【更に追記】
追記で書いたことはむしろ必要条件。
segment treeを考える上で1~nまで並ばせないといけない。
例えば、○以上の値が出てきた回数をカウントするといったタスクの場合、範囲ごとに区分けされていることで途中の段で受け止めることが出来るが、ばらけていた場合、範囲の重複が大量発生してしまい、結局最下段まで見る必要がある。
これは普通に配列等で考えるよりも繰り返しが多くなって意味がない。
クロッシング問題で早くならなかった理由はこれだった。
また、他の注意事項として
1、ノード総数nは2のべき乗にしないと計算が合わない
これはsegment treeが完全二分木であるため。要素が9でも16として考えなくてはいけない。(この場合は配列数は2*16-1で31となる)
これ気をつけないとマジやばい。要素9とかでやると、
0
1 2
3 4 5 6
7 8 9 10 11 12 13 14
15
みたいになってしまって、9でのカウントが1のカウントが入ってるはずの場所に加算されてしまう、みたいなことになる。
2、範囲に気を付ける
「えーと1から16を見たいんだからleftを1に、rightを16にすればいいよね！」
あほ言っちゃいけない。2のべき乗で範囲を区切らないとちゃんと要素にアクセスできないため、8個の要素を見たいなら1<=x<9で1から9、16個の要素を見たいなら1<=x<17で1から17を指定しないといけない。半開区間で実装している場合は。
半開区間で処理をした方がぶっちゃけわかりやすい。前言撤回である。
再帰呼び出しの時も
saiki((left+right)/2, right);
saiki(left, (left+right)/2);
で区分けできるし。半開区間ではなく開区間でやってしまうと
saiki((left+right)/2+1, right);
saiki(left, (left+right)/2);
とか書かなきゃいけなくて実装時無駄に気を使うことになる。
まぁ普通に考えてa<=x<bとa<=x<=bだったら、前者の方が馴染みあるよね。for文とかでさ。本文書いてた時の俺は頭おかしかったんだきっと(
以上、ちゃんと実装してみて気づいた点でした。
開設記念
前々から、メモ用にブログを開設しようと思っていたが、面倒くさがりな性格が影響して中々実行しなかった。
が、最近アルゴリズムやデータ構造について学ぶことが多く備忘録がどうしても必要になってきたので、思い切って開設することにした。
ここには、アルゴリズムやデータ構造、その他プログラミングに関することと、日常の愚痴(主に研究とか人間関係とかだろう)等を書き込んでいこうと思う。
いずれ全体公開した時にこのブログについて何ぞやと思った人のために書いておく。
