NISの環境からLDAPへの移行

今まで研究室のアカウント管理はNISで行っていましたが,やはり様々なサービスを一元管理できるLDAPの方が良いのではないかということで,LDAPに移行することにしました.研究室内のドキュメントはCrowiで管理しているためマークダウンで記述可能であり,ブログにそのまま投稿できます.そこでこちらのブログにも備忘録として残しておこうと思います.

LDAPの仕組み

NISとくらべてLDAPは様々なことが出来ますが,その代わり比較的複雑です.そこで簡単にですがLDAPを俯瞰することから始めてみようと思います.

基本的な考え方

LDAP (Lightweight Directory Access Protocol)とはディレクトリのように階層構造をなした,データベースのようなものです.一般的なデータベースと言えばSQLなどを指しますが,階層構造があるという点が大きく異なります.わかりやすく説明するのが難しいのですが,素晴らしい参考資料がネットの海に漂っていましたので,ここに挙げておきます.
LDAPの基礎知識
20070423odagiri2.pdf

一応簡単に説明すると,エントリーと呼ばれるノードが階層構造をなして木構造的になったようなものがLDAPで扱うデータです.

上の図では,comが一番根本のエントリーで,そこからpeopleまで枝が伸びています.これをlinux的なディレクトリ構造では/com/test/www/peopleと表現することになるわけですが,LDAPではou=people,dc=www,dc=test,dc=comという長ったらしい表現で表します.ここでouとかdcは属性と言って,それが一体どんなエントリーであるか(linuxで言えばどんなデータが入ったディレクトリなのか)を説明し,イコールで結ばれた右辺はその値(属性値)を表します.属性には主に次のような種類があります.

属性名 属性表記 意味
cn common name 人やモノの名前など
dc domain component ドメイン名
ou organization unit name 組織単位
o organization 組織名

したがって,ou=people,dc=www,dc=test,dc=comは,dc=www,dc=test,dc=comというドメイン配下のpeopleという組織単位のエントリーであるということを意味します.例えばpeopleにTanakaという人を追加したいときには,uid=Tanaka,ou=people,dc=www,dc=test,dc=comというエントリーを作成すれば良いわけです.また,エントリーは木構造をなしているので,枝分かれをしてもかまいません.例えば,dc=www,dc=test,dc=comだけでなく,dc=mail,dc=test,dc=comというドメインを同時に作ることが出来ます.この場合は,どちらもdc=test,dc=comの下に作成されることになります.

ドメインはあたかもネットワークのFQDNのような形をしていますが(例えばこの場合,www.test.com),必ずしも現実のFQDNに従う必要はありません(おそらく).単にそういう習慣付けが行われているだけだと思います.

ある団体があって,それがdc=www,dc=test,dc=com以下にエントリーとしてデータを持っている場合を考えましょう.このとき,例えば組織内のグループを表現するエントリーou=Group,dc=www,dc=test,dc=comの配下にあるkame_sann_teamにアクセスするためには,cn=kame_sann_team,ou=Group,dc=www,dc=test,dc=comと書かなければなりません.これがまた別のグループにアクセスする場合も同様に,ドメイン名dc=www,dc=test,dc=comをつけて表現しなければいけないわけです.これは使用するエントリーの基準(すなわちdc=www,dc=test,dc=com)が決まっているのなら冗長です.できればlinuxで言うところのカレントディレクトリからの相対アドレスのようにエントリーを表現できると嬉しいわけですが,当然LDAPにもそのような仕組みが備わっています.LDAPに於けるカレントディレクトリはベースサフィックスと呼ばれ,そこから相対的なエントリーをrdn (relative distinguish name)によって指定します.例えば,ベースサフィックスがdc=www,dc=test,dc=comで,rdnがou=peopleであれば,ou=people,dc=www,dc=test,dc=comを表現していることになります.

さてここでは,ベースサフィックスがdc=www,dc=test,dc=comのときに,rdnとしてuid=Tanaka,ou=peopleというエントリーがあった場合を考えましょう.LDAPはNISの代わりとして使用できるので,このuid=Tanaka,ou=peopleはlinuxのアカウント情報を内包することもできるはずです.linuxにログインするために必要な情報はいくつかありますが,ここではログインシェルの情報を例にとってどのように格納されるを説明します.

先程も言いましたが,それぞれのエントリーはディレクトリのようなものを表しています.したがって各ディレクにおけるファイルのようなものがあります.LDAPに於けるファイルとは,属性と属性値の組を指します.ここでややこしいのは,すでに出てきているou=peopleなども属性と属性値の組であるという点です.普通のLinuxのディレクトリ構造ではディレクトリとその中身が同一であるということはありえません.しかし,LDAPでは各ディレクトリの識別子としてディレクトリ内の要素が使用されるのです.

正しい理解のためにこれらは次のように説明できます.

図に示した通り,一番下のエントリ(ここではTanakaと書かれたやつ)は複数の属性と属性値を持ちますが,この内,識別子(dn:distinguish name)として使用されるのは,cn=Tanakaとなります.これはlinuxのユーザ管理では同じ名前のユーザ名が存在してはいけないということを考えれば非常に合理的であることがわかります.ここでdnとしてloginShellを使用してしまっては,同じシェルを使ってる人どうして区別できなくなり困ることが予想されます.

さて,各エントリーは属性と属性値を持つことはすでに説明しましたが,実際に使える属性にはどのようなものがあるのかはまだ説明していませんでした.LDAPでは,エントリーに割り当てることがかのうな属性は決まっており,ユーザが自由に決めることは出来ません.使える属性はエントリーに与えるobjectClassによって指定されます.objectClassはSQLなどにおけるスキーマを表しますが,LDAPの特徴としてobjectClass自体も属性として表現されます.例えば,先程cn=Tanaka,ou=peopleにはloginShellという属性がありましたが,これはデフォルトでは使用できません.cn=Tanaka,ou=peopleのエントリーのobjectClass属性に属性値としてposixAccountを指定する必要があります.これは裏を返せば,linuxのアカウント情報を表現する属性が一意に定まることになるので,LDAPによって認証する側にとっても都合がいい事が分かります.

使い方

すでに説明したとおり,結局はエントリーの属性値を追加したり変更することがLDAPにおける処理の殆どになります.ldapにはエントリーについて記述したldifというファイルを元にデータベースの編集を行います.例えば,ou=People,dc=www,dc=test,dc=comにuid=tanakaを追加したい場合には次のような内容のldifファイル作ります.

一番上のdnは識別子を表します.これは追加したいエントリーの名前を表しているわけです.またその後uid: tanakaからhomeDirectory: /home/tanakaまでの行は,エントリーの中身(各属性とその属性値)を表しています.見ればだいたい何を表しているかわかると思いますが,userPasswordだけは不思議な記号になっており,パスワードのようには見えません.これは元のパスワードがわからないようにハッシュ化されているためです.このようなldifファイルを作成してあとは,

とすればtanakaというユーザを追加できます.ここで,test.ldifは先ほど作成したldifファイルを表しています.あと,まだ説明していませんでしたが,LDAPには管理用ユーザが存在します.この管理用ユーザもLDAPによって管理され,ここではcn=admin,dc=www,dc=test,dc=comというエントリーで表されています(-Dオプションの引数).LDAPのデータベースを自由に改変できては困るので,この管理用ユーザを介してエントリの変更を行うことが決まっています.

NISからの移行方法(サーバ編)

LDAPからNISへの移行方法を説明します.ここではOSはdebianとし,すでに運用しているNISが存在しているとします.ここで説明する方法はローカルのユーザ(/etc/passwd)の情報を用いても同様に使えるので,特別NISに限った方法ではないことを断っておきます.

まず必要なパッケージをインストールします.

すると色々聞かれますが,とりあえず今ここでちゃんと設定してもしょうがないので,エンターを連打します.質問をやり過ごしたら,

で編集画面に入り,

を追加してください.ここで,BASEのところは上で説明したベースサフィックスになります.自分の設定したいようにドメインを指定してください.URIのところは自分のipアドレスを指定する必要があります.ネットワークのドメイン名でもいいですが,名前解決が正常に行われてるのかどうか確認するのがめんどくさいのでipのほうが楽です.

次に

とします.すると色々聞かれるのでここ適切に答えます.
– OpenLDAPサーバの設定を省略しますか? → いいえ
– DNSドメイン名は? → ドメイン名を入力
– 組織名は? → これはベースdnの属性oの属性値になります
– 管理者用パスワード → 適当に決めてください
– 利用するデータベース → なんでも大丈夫です
– slapdをパージ(削除)した時に,データベースも消しますか? → はい(残す意味はあんまりない気がする)
– 古いデータベースを残しますか? → お好きで
– LDAPのv2を使いますか? → 古いマシンがあれば「はい」.一新するなら「いいえ」

以上で,LDAPの下地は出来たはずです.つぎに,linuxのユーザを管理するためのou=People,dc=www,dc=test,dc=com(dc=www,dc=test,dc=comは自分のさっき設定したやつに合わせて)とグループ用のou=Group,dc=www,dc=test,dc=comを作ります.そのために次のbase.ldifを作成します.

これを

で適用します.この時,LDAPのパスワードを聞かれますが,これは先程のLDAP用の管理者パスワードになります.またcn=admin,dc=www,dc=test,dc=comはdpkg-reconfigureのときに,自動で作られています.

次に,NISのユーザとgroupからldifを作る必要があります.ただしこれは数が膨大で大変です.そこで,自動生成するためのツールであるmigrationtoolsを使います.そのために

として,

の部分を

に変更してください.その後は,

としてください.すると/tmp/ldap_workにpasswd.ldifとgroup.ldifが作成されるはずです.ここで,sudoがないとパスワードがちゃんと書き込まれないので注意してください(/etc/shadowや/etc/gshadowがルート権限がないとアクセス出来ないため).あとは,これらを先程と同様に

で適用すれば終わりです.

NISからの移行方法(クライアント編)

まず必要なパッケージをインストールします.

すると色々聞かれますが,とりあえず今回は無視して適当にエンターを連打してください.これは,初回のインストール時での質問ではうまく設定してくれないという既知の問題があるため,エンターを連打してやり過ごします.二回目以降ではうまくいくことがわかっているので

を実行して,もう一度質問してもらいます.以下のように答えてください.
– LDAPサーバのURI: ldap://サーバのIPアドレス
– 検索ベースの識別名: dc=www,dc=test,dc=com
– LDAPプロトコルのバージョン: さっきサーバで指定したやつ
– LDAPデータベースはログインを必要としますか?:いいえ
– rootへの特別なLDAP権限?:はい
– オーナのみ設定ファイルの読み書きができるようにしますか?:はい
– rootのLDAPアカウント:cn=admin,dc=www,dc=test,dc=com
– 管理用パスワード:さっき設定したパスワード
– LDAPサーバのURI: ldap://サーバのIPアドレス
– 検索ベースの識別名: dc=www,dc=test,dc=com
– LDAPプロトコルのバージョン: さっきサーバで指定したやつ
– LDAP管理アカウントがローカルのrootのように振る舞うことを許しますか?:はい
– LDAPデータベースはログインを必要としますか?:いいえ
– rootのLDAPアカウント:cn=admin,dc=www,dc=test,dc=com
– 管理用パスワード:さっき設定したパスワード
– 使用するハッシュ:crypt
– 有効化するPAMプロファイル:必要なものを選択して了解
答え終わると色々設定してくれますが,重要なファイルである/etc/ldap/ldap.confがうまくやってくれていないので,これを編集して

を加えます.
次に/etc/nsswitch.confを編集します.

最後に/etc/pam.d/common-password を開いて,

のuse_authtokを削除します.これで設定完了です.

内容についてどう思いますか?
  • いいね (3)
  • だめ (0)

ハンドフルート

最近めっきり更新してなかったので,昨日今日と色々書いてみようと思う.

ハンドフルートという手だけを使ってリコーダのような音を奏でる方法がある.詳しくはこのページなどを見てもらえれば分かる通り,両手をお祈りのように組んで息を吹き込むだけで音がなる.

原理としては非常に簡単だが,実際に音がなるまでは恐ろしいほど大変だ.私はある日,手だけで音がなる笛があるんじゃないかと思い調べた際にハンドフルートを知り,その手軽さと面白さに惹かれて始めたのだが,すでに半年近く続けているにも関わらず,未だ上手に吹けている気がしない.試しに千と千尋の神隠しで有名な曲(曲名を忘れてしまったが)を吹いてみて録音したものをアップロードする.

微妙に音がずれてしまっているところなどが多々存在している.いつかこういった部分も含めてうまく引けるようになりたい.

内容についてどう思いますか?
  • いいね (5)
  • だめ (2)

ビッグファイブ

心理学にビッグファイブと呼ばれる性格診断があるらしい.世の中で有名な性格診断といえばMBTIだとかエニアグラムなどがあるだろうけれど,これらには科学的根拠があまりないことが知られている.

対して,ビッグファイブは統計的な,もしくは脳科学や行動遺伝学的な観点からある程度の信頼が置けるものであることがわかっている.多くの場合,性格診断といえば怪しげな占いのような印象を抱く人が多いのではないかと思うが,ビッグファイブはそういった今までの性格診断とは一線を画している.詳しい話は,良書があるためそちらに譲るとして,ここでは簡単にビッグファイブがどのように性格を分析するのかを述べてみようと思う.

ビッグファイブの概要

ビッグファイブは特性論の一つであり,人の性格は幾つかの要素の足し合わせで表せると考える.数学に強い人は線形代数のようなものを思い浮かべてもらえればいい.性格を表す正規直交基底が存在し,それらのスカラー倍(強い,弱い)の総和で人の性格が表現できると考える.これだけだとMBTIに非常に近いと思われるかもしれないが,MBTIとは違いビッグファイブではその名の通り5つの要素が登場する.これらの要素の強弱で表現されるため,MBTIのようなタイプ別(例えば,ENTPのように4つのアルファベットの組で人の性格が表現されるような)というよりも,5次元空間上の点という見方をする.

多くの日本人が信じている性格診断に血液型診断があるが,それに対するよくある反論は人の性格が高々4つ程度で表せるわけがないというものである.確かに,今まで出会った人々の性格をたった4つのグループに分けろと言われれば,ある一側面で分けることは出来ても,それでその人の性格を表せているとは言えないだろう.同様にMBTIでは人の性格が(中間を許す場合を除いて)16タイプしか存在しないことになる.これをベクトル量子化とみなせば,点数を増やすことで精度は向上しているかもしれないが,人間の性格が離散値ではなく連続値であることを考えれば,不充分であることは明らかだ.実際,今まで関わってきた人々の性格が離散的な代表ベクトルで表現できると考えるのは難しいように思われる.それに対してビッグファイブのような連続値的な考えは非常に納得が行く.

さて,ビッグファイブをなす構成要素とは,勤勉性,調和性,外向性,神経質傾向,開放性である.英語がもとであるためか,これらの用語には決まった日本語訳が存在しないため,文献により表現が変わっているかもしれないが,基本的には同じことを言っている.以降ではこれらについて説明する.

勤勉性

私は宿題が非常に嫌いで,特に夏休みの宿題は大っ嫌いだった.最終的にはやらなければならないことはわかっていても,夏休みに余裕がある内は決して宿題を取り出すことはせず,本当にギリギリになったところで焦って終わらせることが恒例行事となっていた.読者の中には,真面目で早めにきっちり終わらせる人もいるかもしれないが,私のようなタイプも相当数いると思う.さて,このようなギリギリまでサボってしまう人々の共通点とは一体なんだろうか.ビッグファイブにおける勤勉性の低い人とは,まさにこのようなサボりグセがある人のことを指す.宿題の例から言えば,勤勉性とはすなわち計画的に物事を遂行できる能力と言い換えることもできる.勤勉性が高い人ほど,自分を律して今やらなければならないことを行うことができる.したがって,世の中で真面目と呼ばれるような人たちは,勤勉性が高いと考えられるわけだ.

また,勤勉性は単にその人の真面目さを表す指標だけではなく,依存症のなりやすさを表すものでもある.ギャンブルやアルコールなどの依存症の原因は,それらをやりたい使いたいというよりも,それらをやめることが出来ないことにある.例えば麻薬を常習的に使用する人々は,比較的早い段階で免疫がつき,薬の効果が弱くなってくる.単に快楽が原因であれば,効果が次第に弱くなる麻薬をいつか手放す日がやってきてもいいはずだ.しかし,実際にはそうはならない.これらの常習者は,麻薬を断つことが出来ないのだ.

今までの話を総合すると,勤勉性はとにかく高いほうが良いと思われるだろう.しかし,ここで生物の進化という点に着目してみる.生物は生き残るのに有利な個体が増えることで繁栄してきた.したがって,もし勤勉性が高いほうが生きていく上で有利であれば,そうではない個体は不利となり減少していくことになる.しかし,実際は勤勉性の高い人も低い人も世の中には多くいる.このように均衡が保たれているのは,裏を返せば勤勉性の低い人も生物学的には必要であることにほかならない.では,勤勉性が高すぎると何がいけないのだろうか.

勤勉性はすでに述べたとおり,計画性に関わっている.その為,高すぎる勤勉性は,計画通りに物事が進まないと精神をやんでしまう,強迫性パーソナリティ障害という病気を引き起こす.これは自分の中のルールに囚われ,秩序や完璧主義が行き過ぎ日常生活に支障をきたす病気だ.例えば,会社である資料を作成しなければいけないとする.資料は出来る限り完成度が高いほうが望ましいが,期限に間に合わなければなんの意味もない.作らなければならない資料の期限がすでに差し迫っているのであれば,たとえ雑であろうと完成させて提出するのが普通の感覚だろう.しかし,強迫性パーソナリティ障害の人は締切よりも,資料が完璧であることのほうが優先順位が高い.そのため,たとえ締め切りを破って上司に怒られたとしても,資料を完璧に作り上げようとする.

強迫性パーソナリティ障害は非常に偏った場合だが,そこまででなくても高い勤勉性は柔軟性を損なわせる.臨機応変な対応が求められる場合ほど,勤勉性は低いほうが望ましい.したがって,どちらのほうがよいなどという議論は意味がなく,勤勉性が高くても低くても,一長一短であるといえる.これは勤勉性に限らず,これから述べるすべての因子でいえることでもある.

調和性

他人に対して共感できるかどうかを表す指標がこの調和性である.他人に共感する能力は面白いことに動物の中で人間しか持っていない能力であることが知られている.例えばチンパンジーで次のような面白い実験を行った例がある.まず隣接した2つのオリを用意する.それぞれに一匹ずつチンパンジーを入れ,お互いの様子が視覚的にわかるようにしておく.片方のオリの中には2つのレバーを用意しておき,1つめのレバーを引くとレバーがあるオリにのみ餌を与え,2つ目のレバーを引くとどちらのオリにも餌が与えられる.もしこれが人間であれば,隣の檻の様子を考慮してどちらのオリにも餌が与えられるレバーを引くだろう.ただし,他人に完全に無関心であれば,どちらのレバーを引いても自分が得る利益は変わらないので,結果的に2つのレバーがランダムに引かれるはずである.

実際,これをチンパンジーで実験すると,レバーを無作為に半々の割合で引くことが知られている.すなわち比較的人間に近いチンパンジーですら,他の個体を意識してレバーを引くことはないということである.その為,この調和性という他人への共感能力は人間だけの特異なものであると信じられている.調和性が高い人は,他人への思いやりが強く,進んでお世話をする.対して,これが低い人は他人に無関心で,自己中心的な行動が多くなる.低すぎる調和性は,サイコパスや自閉的な行動を誘発しやすくなるため,人間関係でトラブルが起きやすいと考えられる.

外向性

外向的な人といえばアウトドア派で,パーティなどを進んで主催し,他人との交流が好きな人というイメージが有るだろう.また,反対に内向的な人といえばインドア派で内気,パーティに参加するくらいなら一人で読書することを好むような人といったイメージだろうか.このような世間一般に想像されるものと,ビッグファイブにおける外向性は近いものはあるものの,実際には少し違った意味を持つ.ここでの外向性を適切に説明するためには,それが脳のどのような機能によるものなのかを説明する必要がある.そこで次のような実験を紹介しよう.まず被験者はMRIに乗せられ,実験中の脳の活動状態を観測される.MRIの中で被験者は複数の画像を見せられる.それは例えば子供が楽しげに遊んでいるようなポジティブなものだったり,反対に特になんでもない街の風景だったりといった様々なものだ.これらの画像を見たときの被験者の脳の活動を見ると,子供の写真のようなポジティブな写真を見た際には,報酬系と呼ばれる快楽を司る部分の働きが強くなることがわかった.特に,外向性のスコアと,報酬系の働きには正の相関が見られたそうだ.これは何を指しているかというと,外向性とはポジティブなことがあった際に,どれくらいそれを嬉しいと感じるかを図る指標となるということである.では外向性が低い人はネガティブな画像を見たときに,気持ちが落ち込みやすいのかというとそうではない.外向性が低いことは単に,報酬系の働きが弱いことを表しているに過ぎない.ネガティブ要因に対する反応性の高さは,外向性ではなく神経質傾向の高さによる.

ビッグファイブにおける外向性は,何か行動を積極的に起こそうとするかどうかを表す指標になっている.例えばパーティで様々な人と交流することや,旅行に行ったりすること,また異性と一夜をともに過ごすことなどのいろいろなことが,外向性が高い人にとってはとても魅力的なことに感じられる.対して,外向性が低い人からすれば,それらのことはそれほど魅力的には映らない.その為,あえて危険を犯すような行為,例えばエベレストを登ることや,起業することなどを外向性が低い人々は行わない.ここで重要なことは,外向性が低い人(内向的な人)は人前に出て発表するようなことを嫌がるタイプではないということである.彼らは,発表することが嫌いなのではなく,発表することで他人に注目をあびることがそれほど嬉しいことではないため,積極的に発表をしないだけである.発表を嫌がる人たちは,内向的な人ではなく,発表することで失敗することを恐れているシャイな人たちなのである.またそれはこのあと説明する神経質傾向の高い人であることを意味している.

神経質傾向

疲れたのでまたあとで更新

内容についてどう思いますか?
  • いいね (2)
  • だめ (1)

conemuでWSL使用時に256色使用する

罠だらけだったので備忘録.

手順

基本的なやり方は,公式ページのとおり.
ただ,なかなかうまくいかないので,自分の方法を示す.

conemuでWSL(Windows Subsystem for Linux:BoW)を直接使用した場合は256colorにならない.ただしcygwinを通すと256色にできるので,cygwinとWSLのブリッジ(wslbridge)を使用する.
ただし当然,これを起動するためにはcygwinが必要だが,WSLを使っているのにcygwinを入れるのは何か違う.そこですでにビルドされたものを使用する.それはここからダウンロードできる.インストーラを実行すると,デフォルトでC:\Users\username\AppData\Local\wslttyにインストールされる.

また,conemuでwslbridgeを利用するのにconemu-cyg64.exeも必要となる.それはここからダウンロードする.
7zを展開すると,conemu-cyg64.exeが手に入るので,これを先程のwslttyのbinフォルダに突っ込む(C:\Users\username\AppData\Local\wsltty\bin).

ここまでくれば必要な実行ファイル類は全て揃う.
次にC:\Users\username\AppData\Local\wsltty\bin\wsl.cmdを次の内容で作成.

この部分は,公式ページと少し違うので注意.

最後に,ConEmuのSettingsから,Startup → Tasksで{Shells::WSL}を作り,

を実行コマンドに指定すればok.

このタスクを実行すれば無事256色になっているはず.

内容についてどう思いますか?
  • いいね (5)
  • だめ (0)

昔より感動がなくなった

これを見てくれる後輩がいるらしく、更新されてないと言われてしまったので何か書こうかなと。

一昨日くらいに、大阪で串かつとたこ焼きを食べた。この2つは、大阪の定番中の定番グルメだろう。今から5年くらい前にも一度食べたことがあって、そのときには非常に感動した覚えがある。それを久しぶりに食べて見たら、思ったより普通で拍子抜けだった。あの頃はまだ高校2年生(高専だったけど)だけれど、それでも味覚が今とそれほど違うとは思えない。それとも5年間の間に、俺の味覚が大きく変化してしまったのだろうか。

とにかく、昔ほどの感動がなくなってしまい、なんだかすごく損した気分になった。年をとるに連れて急速に感性が衰えてきてるのかもしれない。何事楽しく感じれるかどうかは、その人の受け取り方によるというのを、強く実感した。でも今更初心に戻って感動を味わうことは難しいし、楽しく感じるものが減っていくのは避けられないのだろう。つらすぎる

普段から、面白いこと探しをしてるわけだけど、年をとるに連れて難易度がどんどん上がっているのかなと思う。俺以外の人たちは、この面白いと思える範囲の縮小はどのくらいの速度なんだろうか。

内容についてどう思いますか?
  • いいね (1)
  • だめ (0)

技術系のブログを書いてて思うこと

書き始めると連日投稿してしまうのは,関心がブログに向くとき向かないときに波があるからだ.本来コンスタントに続けるということが非常に重要なのはわかっているつもりだが,実際のところ気分屋の私には非常に難しい話である.

ブログという媒体に関して

自分を売り込むというくだらない理由でやり始めたこのやる気のないブログだが,地味に続いていて,やはり金をかけてサーバを借りているということの重みがわかる.まあそれはいいとして,私としては細心の注意を払って各記事を書いているつもりだが,記載している情報については多くの間違いを含んでいる可能性が多分にある.
そもそもブログという媒体の性質上,それほど堅苦しく厳密さを求めるようなものではないので,間違った内容を含んでいることは,むしろあって当然という気がする.別に内容を誰かが査読しているわけでもないし,私個人の趣味で書いているようなものなので,これをお読みの皆様には疑ってかかってほしいくらいの気持ちである.

そもそもブログというものは,自由にかつスピーディーに投稿できるということが最大の利点であって,中身の正確さや厳密さは二の次にしている.ただし,私がまだブログを殆ど書いたことがなかった頃は,ネット上で調べたときに引っかかった,なんの信憑性もないブログ記事を深く信用して読んでいたように思う.まあそれはネット上には優れた人たちがたくさんいて,間違いの少ないよくできた記事を大量に提供してくれていたおかげなのだろう.世の中の記事がみんな悪質なものだったら今ほど信用して技術系ブログを読んでいなかったのではないかと思う.

ただし,こうして自分でブログに技術系の内容をまとめてみると,案外多くの人が見てくれていることに気がつく.私のブログでアクセス数が多いのはCPUをFPGAで作ったやつと,モンゴメリ乗算の2つだ.1日あたりのアクセス数はそれほど多いというわけではないが(マイナーだろうし),ちりも積もればなんとやらで毎日一定数の人に見てもらっているということは,総和としては多くの人の目に触れているのだろうと思われる.

私は昔から人に何かを説明するのが好きだったし,今でもそうだがその場合には質問という形で,私に対して何かしらの反応があるものだが,ブログという形態はコメントという形を取らなければならないので,躊躇してしまう人が多いのだろうと思う.個人的には,内容の不備や質問は随時受け付けたいと思っているわけだが,なかなかそうは行かないものだ.そこで各記事の最後には内容についての評価をボタンという形で簡単に投票できるようにしている.まあこんなのはただの気休めにすぎないわけだが,ないよりは全然いいのだろう.身内の人が多いのかも知れないが,それでもそこそこボタンが押されている形跡がある辺り,役目を果たしているのだと思っている.

でもしかし,実際にはコメントをくださる方もいらして,過去に記事の訂正を行ったこともある.そういったコメントをこんなわけの分からないブログにくださる方には非常に感謝している.私としては,疑問や質問,もっと説明してほしい,お前の言ってることはおかしい等々,好きにコメントを書いてほしい.読者の方々のフィードバックが私の原動力になっていると言っても過言ではない.

さて,ここまでごちゃごちゃといろいろ言ってきたが,結局渡しが言いたいことは,私のブログを疑ってかかりながら読んでほしいということだ.間違っている可能性は十分あるわけで,何も考えずうのみにすることは私にとっても,これを読んでいる方にとってもマイナスにしかならない.それに勉強というのはアウトプットしたときが最も負荷がかかって,良いトレーニングとなる.受動的な姿勢で読むのではなく,能動的な姿勢で批判的に受け取ることがwin-winの関係をもたらすのではないかと思う(と言っても私もそれは全くできていないわけだが).

内容についてどう思いますか?
  • いいね (2)
  • だめ (0)

正解するカド

ここ最近色々考え込んでいて,全く何をするやる気もなかったわけだが,ようやく回復してきて久しぶりにアニメをみた.

今回見たのは今季放送中の正解するカドである.この作品,どうやらアニメ原作らしくまだ9話までしか放送していない現時点では,一体どのような最後を迎えるのかはわからない.
しかし,ここ最近ではいくらか面白いと思うアニメであることや,珍しく3D作画で成功しそうな気配を感じるので,感想を述べようかと思った次第である.
ちなみに2chではすごい勢いでスレが伸びているようで,見た感じセカイ系なのかで盛り上がっているようである.まあ私としてはどちらであるかはそれほど重要ではないのだが.

正解するカド

羽田空港の滑走路に突如として謎の1辺が2キロメートルを超す超巨大な正立方体が出現し、出現場所に居合わせた旅客機256便(ボーイング777型)が、乗員乗客もろとも立方体に飲み込まれた。政府が関係各省と連携を取り合い、この立方体の調査と飲み込まれた乗員乗客の救命に奔走する中、立方体上部にヤハクィザシュニナと名乗る人物と、偶然256便に乗り合わせていた凄腕の交渉官真道 幸路朗が現れる。(wikipeida)

上記がwikipediaに記載されているあらすじである.突如羽田空港に出現した巨大立方体に主人公である真道が飛行機ごと飲み込まれ,そこで謎の人物ヤハクィザシュニナと出会うことから物語が始まる.
始まりとしては一見シンゴジラに近いものを感じるが,実際はあまり関連性はなさそうである.そもそも政府とか国際連盟とかを引き合いに出す割には,後半に進むにつれその存在は希薄になってしまう.シンゴジラは,そういった官僚や国といった不自由な存在が話の根幹をいくらかになっているように感じたが,正解するカドではそこには重きは置かれてなさそうだ.これが2chでセカイ系だどうだと叩かれてることの理由の一つであろう.

人類の進歩

作中で,人類に接触した異方の存在であるヤハクィザシュニナは,当時の技術力では到底達成できないようなアイテムを人類に無償でプレゼントする.1つ目が異方と我々が生きる宇宙をつなげる存在であるカド,2つ目が無限の電力を提供できる球状物体ワム,3つ目が人類が睡眠を取らなくても大丈夫なようになるサンサ,4つ目が異方の制御がおこなえるナノミスハインである.
これらのまるでドラえもんのひみつ道具のような魔法のアイテムにより,人類は飛躍的な進歩を遂げるだろうということが作中で何度も語られる.多くの登場人物たちは迷いもあるものの,この進歩について肯定的な意見を持っているが,徭 沙羅花はワムの拡散に関して否定的だったりと少数派側の立場に立っている.

この作品の不思議なところは,一見異方からもたらされた贈り物に対する人類の葛藤が一つのテーマのように思わせて,実際のところ主人公の周りを除けばその様子が描かれることがないことである.はじめにワムが日本政府にもたらされたときには,国際連盟がその影をちらつかせ,ワムを取り上げようとするものの,最終的にはワムの製造方法を全世界に配信することで国際連盟の思惑は水の泡になってしまう.このときにはロシアの首相が悔しげな表情を浮かべるなど,他国の様子が多少なりとも描画されていた.ところが,サンサの件については,ワムのときとは異なり,国や国際連盟による干渉は一切行われず,たかが一企業が全世界にサンサを放送してしまうことを決定してしまう.サンサを放映することによる影響について語られる場面がないわけではないが,それもほどほどに全人類は睡眠という枷から解き放たれることになる.あれほどワムのときには過干渉を行ってきた国際連盟が,サンサの件については無関心というのも納得の行かない話である.

結局のところ,人類にもたらされた異方の贈り物が人類にどのような影響をおよぼすのか取り沙汰される割には,そのことに関してはほとんど取り扱われることがない.したがって,この物語は別段,異方によりもたらされたアイテムによる人類の進歩による影響は,あまり重要ではないということである.

宇宙の存在と異方の目的

現在最新話である9話では,宇宙というのがどういう存在で異方が一体何の目的で人類に接触してきたのか明かされる.そして9話の最後にヤハクィザシュニナは真道に一緒に異方に行くことを提案するが,好ましい返事が得られないとなると,打って変わって真道を殺そうとする.ここで突如徭 沙羅花が現れ,真道を命からがら助けるのだった.

この時,徭 沙羅花がどうやらこの世界の管理者であるということが判明するわけだが,ここから何故徭 沙羅花が人類の進歩に否定的だったかが垣間見えてくる.要するに,管理者たる徭 沙羅花にとっていきなり外から現れたヤハクィザシュニナはイレギュラーな存在であり,それによりもたらされる異方の贈り物は好ましいものではなかったということである.そう考えると,この物語はいきなりチープなものに感じられてくる.すなわち,人類や世界と言った広大な話をしていたはずが,実のところヤハクィザシュニナ,真道,沙羅花の3名による内輪もめに過ぎないということだ.他のいろいろな要素は話を面白くするためのお膳立てに過ぎず,特に物語中で一貫したテーマは存在せず,実際は小さいところで話が収まってしまう.まだ最終話まで放映されていないとはいえ,おそらくそのような流れになるだろう.

結局はセカイ系の大したお話ではないのかも

最初に否定したものの,結局セカイ系ということが本題の中心に来てしまった.一見何も考えずに見てる分にはそこそこ面白いものの,よく考えてみると話のあらが目立つ残念な作品なのかもしれない.ただ私としては,ここまで批判的だったとは言え,多少なりとも面白いと感じさせてくれたという点において非常に良かったと思っている.内容はどうあれ,続きすら気にならないようなアニメさえある昨今においては,最後まで見ようと思える珍しい作品ではないかと思う.

内容についてどう思いますか?
  • いいね (1)
  • だめ (1)

ICPC 2005 Domestic D Traveling by Stagecoach

最近,なんやかんやあってICPCの問題を解いている.せっかく解いたのでD問題について解説してみる.もっといい方法もあるのだろうけど,とりあえず基本方針だけでも.

問題:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1138&lang=jp

考え方

この問題は馬車券によって馬の数が変わるため,それによりグラフの重みが変化する.したがって,ダイクストラ法のような経路探索アルゴリズムは使用できない(厳密には嘘.馬車券の状態まで含めてノードにすれば使える).かと言って,深さ優先探索や,幅優先探索するにもグラフが大きすぎるため厳しいものがある.一見手も足も出ない用に見えるけれど,こういう場合は動的計画法でどうにか出来ないか考えてみるといい.

この問題はよくよく考えてみると,今まで進んできた経路はどうでもいいことに気がつく.大切なのは,今どこのノードにいて,そこにたどり着くまでにどれだけのコストと馬車券を使用したかということだけ.そのためにどういう道順できたのかは,わからなくたって問題ない.これを使って漸化式を建てられれば,解けそうな予感がするので,実際にやってみる.

立式

式に落とすために変数を定義しよう.まず都市の集合を\(A\)とする.このとき,ある都市\(a \in A\)から直接道路でつながっている都市の集合を\(P(a)\)と表記しよう.また都市\(a\)から隣の都市\(b\)への距離を関数\(C(a,b)=C(b,a)\)で表す.次にすべての馬車券の集合を\(B\)と表し,今までに使用した馬車券の集合を\(Q_n\)とする.このとき\(n\)は移動した回数のこと.以上の変数を用いてある都市までの最小の総移動時間(コスト)\(f\)について次のような漸化式が成り立ちそうなことがわかる.

$$f(Q_n, a)=\min_{q\in (Q_n – Q_{n-1}), b\in P(a)} \left( f(Q_{n-1}, b) + \frac{C(a,b)}{q} \right) $$

ここで注意しなくちゃいけないのは,あくまで左辺が与えられたときに右辺を計算するということ.何が言いたいかというと,都市\(a\)にたどり着くために使用する馬車券は決まっていて,それでどれだけコストが抑えられるか計算するのが上の式が表していることの意味.だから\(Q_n\)が与えられたときの\(Q_{n-1}\)を計算することになる.おんなじように\(b\)もaからアクセスできる都市を手当たり次第試す必要がある.あとは上の式を実際に適用して解けばいい.

プログラミング

次が実際に僕が書いたプログラム.中身は上の式をただ落とし込んだだけなんで説明は省略.

 

内容についてどう思いますか?
  • いいね (2)
  • だめ (1)

NP困難とNP完全

最近,証明書が切れたみたいでこのページが危険だって表示されるらしい.そろそろ更新しなきゃと思いつつ,何もしてない(めんどくさい).

さて,今回はNP困難とNP完全の話.よく間違えるので書こうと思います(間違えるのはもしかして俺だけ?).

計算量を議論する際に,知ってる人も多いと思うけれどPとNPという問題のクラスが存在する.Pは多項式時間で解ける問題を表していて,NPは答えを知っているときに問題を多項式時間で検証できる問題を意味してる.多項式時間が英語でPolynomial Timeなので,頭文字を取ってきてPだと思うのはいいけれど,NPをNon Polynomial Timeと考えて,多項式時間じゃない問題だと考えるのは間違い.

NPはNon Polynomial Timeじゃなくて,Non-deterministic Polynomial Timeのこと.意味が違うから勘違いしてはいけない.ただこの紛らわしい命名規則がそもそもの混乱の元のような気がする.

さて,多項式時間で解けるとは一体何を指しているのだろうか.これは簡単に言えば,問題のサイズに対して多項式に比例する時間で解けるという意味.例えばソートの問題であれば,性能の悪いソートアルゴリズムは要素数\(n\)に対して,大体\(n^2\)に比例する時間でソートができる.多項式ってのが例えば\(x^3+2x^2+x+-1\)みたいな形をしてるものを指してることを考えれば,できるの悪いソートアルゴリズムの計算時間が多項式時間であることがわかる.対して,各家庭に宅配をする問題を考えてみる.宅配をしなくちゃいけない家のリストとそれぞれの家の間の距離が与えられたときに,最短で回れるルートを考える問題はめちゃくちゃ難しくて,愚直にやると家の数\(x\)に対して,\(x!\)の時間がかかる.これは多項式じゃないので多項式時間で解けるとは言わない.

基本的には,問題のサイズ(例えば要素数が\(n\)とか)に対して,\(n^a+n^b+…+n^z\)(ただしa,b,…,zは定数)で解ければ,多項式時間で解けるってことになる.多項式時間の場合は別に,このaとかbの値がどのくらいの大きさであってもかまわないので,これがめちゃくちゃ大きければ解くのが大変なわけだけど,それでも宅配の問題のような\(n!\)みたいなのが出てこない限り,ときやすいと考える(たぶん).

Pの問題は多項式時間で解けるものを指しているけれど,NPは答えを与えられたときに多項式時間で検証できるものを表している.多くの場合,答えが与えられたらそれがあってるかどうかを検証することは,答えを見つけることより簡単なことが多い.例えばソートの問題だったら,ソートするよりソートが終わってるかどうかを調べるほうが断然簡単なのは明らかだ.だから,ソートの問題はPにもNPにも属していることになる.

他の問題に部分和問題がある.これは,複数個の数が与えられたときに,そこから幾つか選んで足したものが,ある数\(N\)に等しくなるように選ぶことができるかっていう問題.簡単な例として,1,5,7が与えられてたとしよう.ここからいくつか選んで足し合わせたら6にできるかって聞かれたら,即座に1と5を選べばいいってわかると思う.似たように今度は9にできるかって聞かれたら,できないってこともわかる.ただし,これは個数が少ないからわかるのであって,これが膨大な数から選択する問題だったら,簡単じゃない.ただし,膨大な数が渡されていたとしても,答えがわかっていてそれがあってるか確認するのならきっと直ぐにできる.実際,この問題はNPに属していて,さらにNPの問題の中では特に難しい問題だとわかってる.こういうのをNP完全という.

問題が難しいか簡単かという話は,ある問題を多項式時間で別の問題に帰着できるかどうか判断できる.例えば,幾つかの要素の中から最小のものを探したいとしよう.これは要素すべてを調べればわかるから,要素数\(n\)に計算時間が比例する.だけど,要素全体をソートしてから,一番端にある要素を取ってきても同じことができる.ソートするには一番速くて\(n \log(n)\)の時間がかかることがわかってるので,ソートするほうが遠回りになる.でもソートすることでも解けるということで,最小値を求める問題は,ソート問題に帰着できると言える.この例の通り,帰着元の問題は,帰着先の問題より簡単なので,帰着関係で問題の難しさを言うことができる.似たように難しさがわからない問題があったら,計算量が分かってる問題に帰着させる方法を考えればいい.

NP困難の問題は,クラスNPの中で特に難しい問題だと言ったけど,そういう問題よりも難しい問題がある.要するに多項式時間で検証できないような問題が存在するということ.そういったNP完全な問題と同等か,それ以上に難しい問題をNP困難という.NP困難はNPってついてるけど,必ずしもクラスNPに属してるわけじゃない.NP完全より(以上)は難しいという意味.

部分和問題の話の中で,この問題はNP完全だという話をした.この問題はNPには属していそうだけれど,Pには属してなさそうな感じがするかもしれない.しかし残念ながら,部分和問題は多項式時間で解けるかどうかはわかってない.もっというとPとNPが同じかどうかはミレニアム問題という多額の賞金が出る問題となっていて,今現在も全力を上げて研究者が調べてる.なので,P=NPかP≠NPのどっちであるのかわからないけれど,計算機科学を取り扱ってる多くの人の見解は,同じではないだろうということで一致してるのだと思う(おそらく).

誰か頭のいい人証明して~

内容についてどう思いますか?
  • いいね (6)
  • だめ (2)

やりたいこと

やりたいと思っていることがいくつかある.箇条書きにすると

  • FPGAのCPU実装をもっと頑張る(具体的にはUnix系OSを動かす)
  • Rustをやる(できれば研究とかバイトのコードも徐々に移行したい)
  • 日本語力を上げる
  • もっといろんなことを勉強する(暗号,音声,機械学習,etc)

のような感じ.別に最後のやつは普段のタスクの中に自然と組み込まれている感じなのであまり意識する必要はないだろうけど,上から2つは個人的に時間を作ってやらないとできるとは思えない.3つ目は文章が下手くそなのでうまくなりたいなということ(願望).

FPGAのやつはできればCPUの実装のコード(verilog)をきれいにしたというのもある.研修Aという研究室の自由課題でやったものだから,締切に合わせて結構その場しのぎでやってしまった感があって,それをどうにかしないと次に進む上で障害になりそう.かと言ってあれってそんな簡単に直せるとは思えない… 抜本的に書き直す羽目になりそう.そもそもverilogってアセンブリに近いものがあって全然きれいに書けてる自信がわかないんだけどどうすりゃいいんだろう.高位合成とかと違って結構低レイヤだから記述量が多くなりがちなのが影響して,とてもじゃないけど見やすくならない.あれも結局経験値で決まってくるやつなんだろうな.

Rustについて言えば,とにかく実践で使っていくしかないだろうなって思ってる.入門書とか初心者向けの記事とかをただ追って読んでるだけだと全然頭に入ってこないたちなので,実際に使って鍛えていくしかない.自分もそんなに詳しいわけじゃないんであれだけど,c言語とかc++みたいなシステム周りとか結構低いレイヤのプログラミング言語って,D言語とか他にもあるんだろうけど結局のところc言語 or C++がデファクトスタンダードって感じがあるように思う(マイコンとかの開発環境でC++/C以外の言語を使う場面ってなくはないけど少ない気がする).LLだとか関数型言語とかだと選択肢がありすぎるくらいにはあるのに,低レイヤ向けの,アセンブリより抽象度が一つ上なメジャーな高級言語ってのが,もう何十年も前に発明されたCとかC++のまま変わってないってのは,あまりに時代遅れな感じがする.と言いながらもう10年近くCだとかC++を書いてきた人間がこんなことを言うのは説得力にかけるのかもしれないけど,流石に限界というかこのあたりにもイノベーションがあってもいいよねってのは薄々思っていたところ.確かにC++は最近になってC++14とかC++17とか新しくなってきてるけど,もともと難解だったC++に更に付け足しつけたしで色々くっつけたもんだから複雑怪奇になって来てて,「C++を理解してます」ってのがジョークになるという笑うにも笑えない状態になってる.

だから流石にそろそろ新しくそういうシステム周りもかける言語を習得したいなと思ってたわけだけど,ちょうどMozillaがRustを開発してるという話を知って,これは良さそうと感じた.最近はライブラリも結構充実してきてて特に問題もなさそう.他に最近話題のコンパイルするような静的型付け言語としてはGoとかもあるけど,あれはポインタを叩くような処理をするというよりは,コンパイルできるLLみたいなイメージが有る.Google的には速度が出るLLが作りたかったってことなんかなという印象(素人目線).個人的にはやっぱりLLとシステム記述向けの言語って住み分けができてると思ってて,前者が簡単にかける代わりに詳細な記述をしたり速度を出したりすることが難しいもので,後者がその反対という感じ.よくGoとRustを対比させる記事を見るけど,それはこの2つがちょうどLLとシステム記述向け言語の間くらいに位置する言語だからということなんだろうな.ただGoはどちらかと言えばLL寄りで,Rustがシステム記述向けよりなんだろうと思うし,だからこの2つは用途が衝突するところもあるけど,全くかぶらないところもあるんだと思ってる.

確かにLLって半端じゃないくらいに遅いから早くしたいと思う人が多いのは当然だよね.pythonくらいしか経験がないけど,それでもC++なら一瞬で終わる処理が半端じゃないくらいに時間かかったりするのを見て,何とも言えない感じなることはある.プログラミング界隈で有名な話?に80:20則ってのがあって,プログラム全体の20%が実行時間の80%を占めてるって経験則なんだけれど,LLの哲学的には,重い20%のコードをCとかにまかせて,速度がでなくても大丈夫な80%ところをLLでどうにかするって話だったんだと思う.確かにそれは合理的に見えるし,全部を無駄に書くのが大変な言語で修行のごとく記述していくのは意味がないってのは大いに賛同するところなんだけど,現実はやっぱりなかなか厳しいものがあって,そう簡単じゃない.実際に使ってみると,LLがおそくてその80%が馬鹿みたいに大きくなったりして,僕の書き方が悪いってのはあるんだろうけど,なんだかなーって結果になることも往々にしてある.そんなこんなあって,みんな早いLLを求めてたんだろうから,Goみたいな言語が出て来たんだろうなという予想.本当のところどういうことなのかはGoを勉強しないとわからないけど,今のところGoが重要そうなWeb界隈の方には全く関わりがないので,実用的な観点でやることはなさそう.

とまあ前置きが長くなったけどRustを勉強したいなと思ってる.関数型言語の流れを受けて色々と拡張があるみたいだし,加えてC++とかと比べて安全だと言われればやらない理由も特にない.速度も結構早いみたいだしね.

ということで今年度も頑張っていきたいと思います.

内容についてどう思いますか?
  • いいね (2)
  • だめ (1)