2009年06月08日

発表オワター

発表そのものはひどくはなかったが、質疑応答がぼろぼろだった。

もう少し応答をうまくできるようにならねば・・・

posted by chiguri at 16:50| Comment(0) | TrackBack(0) | 研究

2009年04月03日

やっぱり研究というほどじゃないけど

以前似たようなタイトルの日記を書いたが、今回は用語ではなくアルゴリズムの話。*1

クイックソートという名前なのだが、アルゴリズムを少し勉強した方なら誰もが聞いたことがあるだろう。

厳密に説明するのは面倒なのでここでは適当に説明するが、


数字の列(数字に限らないが、単純化のために数字とする)を与えられたとき、

1:列から一つ、基準を持ってくる。

2:(非常に大雑把には)基準より大きいものと小さいものに分ける。

3:それぞれに再び1から適用、列の中身が一つの時点で1を適用したら終了する。


という感じのアルゴリズムである。

特徴として速いことが挙げられる*2

あとは、安定でない。同じ数字(と見なされるもの)があった場合、その順番が元の列の順番を保存しない。

主に2で分けるときに、partitionというアルゴリズムで分けるためである。

大雑把には、


1:列の中から基準を一つとる。

2:基準より大きいものを列の左から、小さいものを右から探し、最初に出てきたそれぞれを入れ替える。

3:2を繰り返して、「大きいもののある位置」が「小さいもののある位置」より右側にきたら、最後に大小の境界部分に基準を置いて終了。


という作業である。

まあ、入れ替えたりするんだから、前後関係は変わったりしそうだなあ、と思ってもらえれば十分である。


で、わざわざ書く理由は何かというと、明らかに安定な「クイックソート」があるからだ。

いや、これをクイックソートと呼んでいいのか私には判断しかねるが*3

で、具体的にはどうするかというと、partitionに当たる部分が


1:列の先頭の一つを基準にする。

2:次の要素が基準より小さければ「左」の列に、基準より大きければ「右」の列に追加する。

3:列の最後まで2を繰り返し、最後までみたら「左」の列と「右」の列が「分けたもの」である。


というもの。

元のアルゴリズムと比べると、

1:列が余計に増えている(再利用していない)

2:入れ替えじゃないので、位置関係の張り替えが二回行われている

3:安定である*4

という点が異なる。

これ、速いのだろうか・・・?(遅いとは思わないが、操作が増えている気がする)

ちなみに、このアルゴリズムが書かれるのは、Haskell(代入が制限されている)などの関数型言語(の一部)やProlog(代入という概念がない)などの論理型言語である。


良い悪いをここで議論する気はほとんどないが、「わずか〜行で(こんなに簡単に)クイックソートがかけます!」というのはさすがに誇大広告のような気がしてならない。

柔軟性を主張しようにも、そんな型にはまったアルゴリズムを一から書く人間はほとんどいないのだから。

*1:いや、やっぱり用語かも。

*2:理論的な速さとは少し違う観点なのが少し特殊である。

*3:判断していいのはクイックソートの作者であるC.A.R.Hoareくらいだろう。

*4:正しくいえば、安定にできる。

posted by chiguri at 15:09| Comment(0) | TrackBack(0) | 研究

2009年03月18日

正式に

博士課程進学が決定したらしい。

書類がくるのはもう少し先か。

来週手続きのようだし、今週中だといろいろ助かるのだが・・・


追記(3/19):もう書類が来た。研究室に直接だから早いこと早いこと・・・

posted by chiguri at 12:35| Comment(0) | TrackBack(0) | 研究

2009年03月07日

ポスター一応完成

今回は対外的な発表でありながらアレがたくさん・・・

げふげふ。

研究室のサーバー周りをなんとかしたら、研究室の自分のWebページを少しくらい管理するか・・・

あんまり論文とかは載せたくないけど、論文の参照くらいはないとなあ・・・

posted by chiguri at 22:57| Comment(0) | TrackBack(0) | 研究

2009年02月13日

近年?

なんか近年ブームらしい。

で、自分の修論で書いた文章を思い出すと・・・

ああ、書いてるな。

ついでに卒論でも書いたな。


卒論のはあやしいか。確か・・・ソフトウェア検証だっけ?だいぶ昔からある話だ。(実用的になってきたのは最近だと思うが)

今のは・・・いや、アスペクト指向って生まれたの10年少し前だ。

しかしそんなの具体的に書いてもなあ・・・

posted by chiguri at 15:23| Comment(0) | TrackBack(0) | 研究