「僕、C言語が使えます」に対する短い考察
最近僕は「所属する組織」に基づく評価を受けることが多くあり、これはある種正しい傾向を得られるにしても、それでその人自身を全て評価するのは早急すぎる、と考えていた。「人を評価することはすごい難しいことである」とこの頃実感している。（別に実際に評価するような仕事はしていないけれども）
人の評価に関連して、別の場面において、「就活で、”僕、C言語が使えます”というのが役に立たなかった」というのが話題に上がった。その時は「ある言語を使える、のレベルが人によって全然違う」と返したけれども、よく考えてみると、もっと深く広がってくる話題なのでは、と思い自分の浅い経験を元に考察してみる（間違っていたら指摘して頂けると嬉しいです）。
まず、発端である「就活で、”僕、C言語が使えます”というのが役に立たなかった」、というのは何故起こったのか。自分が想像するに、
１．企業がそもそもそういう人材を欲していない
２．企業にC言語が使えるかどうかを判断できる人がいない
のような理由を挙げられると思う。１．は受けた企業がIT業界なら、そこからSIerとかの話になってくるのでここでは割愛して、２．を掘り下げていってみようと思う。
C言語が使えるかどうか？について
「C言語を使えるかどうか」についてはかなり宗教的な議論になってしまうのではないかな、というのが深く考える前も後も思っている。「そもそも言語というのはツールなので、C言語を知っているかどうかは重要ではない」「C言語はオブジェクト指向ではないから、オブジェクト指向的考え方（＝コードをできるだけ再利用する、というのがここで想定している意味）が測れない」等等、様々な反論が考えられるにしろ、とりあえず、ここから深めていくとすれば例えば以下のような質問でしょうか：
１．ポインタはどういう場合に有用か？
=>これは変数自体に破壊的な代入をする際に有用である（e.g. 配列の中身を変える関数を書きたい）、という答えが欲しいので聞く。まあそれをそもそも許していいのかどうか自体は宗教的な問題としてあるけれども。グラフを表現する際に人の直感に即している等の答えも考えられる。
２．一度定義した配列の長さを拡張したい場合はどうするか？
（追加の質問として）動的配列を実装する場合は例えば何故新しい要素を挿入する時にO(1)になるのか？
=>なぜ一次元可変長配列がPythonとかで採用されているのか、長さを拡張するようなシチュエーションに出くわした際にパフォーマンスを意識したことがあるかどうか、というのを見たいので聞く。
更に、上で出てきた「言語を知っているかどうかは重要ではない」という考え方なら、アルゴリズムとデータ構造、スレッド、ロック等の質問をぶつけるのかな、と思う。（ちなみにここらへんはCracking the coding interview 5th editionの考え方に強く影響を受けております）
じゃあアルゴリズムとデータ構造をテストする際に、例えば「簡単な再帰関数がさくっと書けるか」、「動的計画法を用いて計算量を落とせるか」を見たい場合は、よくある「n番目のフィボナッチ数列を返す関数を実装してください」という質問を投げかけると思う。ちなみに上記の「さくっと」というのは人によっても違うし、さくっと書けることによって仕事において必要なコミュニケーション等に時間を割く事ができるし、別の機能を実装することにも時間を割けるので、重要な意味合いを持っていると思う。
、、、と考えている内に「C言語を使えるかどうか」を測るには、どうやら今のコーディング面接のようなスタイルにならざるを得ないのかな、と思った。もちろん実際の仕事では、ちゃんと必要な場合に連絡を取るか、等のソフトスキルも重要になってくるとは予想するので、今のスタイルが最適な訳ではないけれども。（というのはProgramming Interview Exposed 3rd editionからの影響です）
雑記：
あまり関係ないけれどもここのサイトのコラムにある「コンピュータ業界は宗教的」、というのは妙に納得した。
追記：
就職活動を振り返る 後編に共感を覚えました。
Patricia Trieの実装する上での基礎事項
※Javaコードの実装が追いついていないので、実装でき次第追記しておきます。
Trieは辞書を参照する等で非常に便利なデータ構造なので、ちょっとメモしておく。今回はこのTrieの一種であるPatiricia Trieのお話。
基数木とも呼ばれているが、僕は基本的にPatricia trie（パトリシアトライ、パトリシア木）と呼んでいる。Trieのノードもしくはエッジが文字列に対応する事によって、余計なノードを確保せずにすむのでメモリの節約になる。
実装する上（自分はJavaを想定）での注意点を列挙した。基本的なことであるが「問題を細分化して、自分の理解可能なレベルにまで落とすこと」は非常に重要なことであるので、やってみた。
Trieからの変更点
最もナイーブな実装である「アルファベットの数だけ、配列を確保する」とメモリを浪費してしまう
何も考えずに分岐点に256個のポインターを配列として並べたらそれだけで32bitアーキテクチャーでも1024bytes。いくらなんでもこれでは富豪すぎるというものです。
algorithm - Patricia Trie (Radix Trie) を JavaScript で
これを避けるため、子ノードを動的に確保する。ただし、ソートをしない場合は子ノード探索時に全ての子ノードを線形探索する。ソートをしておけば、二分探索等はできるが、Patricia Trie構築に時間がかかる。
※ちなみに構築と探索のオーダーは、Mはそのノードにおける子ノードの個数とすると、
二分探索木の使用やソートするなら構築に、O(NlogN)、（子ノード）探索にO(logM)、
ソートしない場合は構築にO(N)、（子ノード）探索にO(M)。
ハッシュを使えば、構築にO(N)、子ノード探索にO(1)。ただし、理想的な状況下（ハッシュが衝突を起こさない等）を想定する上、その分メモリは食う。
以上から、構築、探索、メモリのトレードオフになっている。
Insertが少し面倒になる
例えばappleとappsを挿入する際に
１．appleという文字列に対応するキーを持つノード（又はエッジだが、以下ノードに統一する）をルートから挿入する。
２．appsという文字列を挿入する時：
A. appというノードを用意する。
B. leというノードと、sという文字列に対応するノードを用意して、appノードにつなぐ。
キーに対応するバリューのGetは一文字ではなく、接頭文字列になる。
これはWhile文で一致長をインクリメントすればいいだけだから、さほど難しくない。
Deleteもノードの削除と、親ノードのキー変更がいる
１．appsに対応するノードを削除する（＝デストラクタを起動？）
２．
A. leというノードを削除し、appのキーを持つノードのキーに「le」を追加する。
B. もしくはそのまま放置
雑記：
より最適化したPatricia Trieはcrit bit treeというビット列のTrieにより実装できる。これは動作が複雑で、まだ理解しきれていないので、また後日。。。あとダブル配列やLOUDSも構築、探索、メモリのトレードオフをぶち壊して、より最適に近くなるはず。詳しくはcedar - C++ implementation of efficiently-updatable double-array trieとかを参照するとライブラリ間のパフォーマンスが比較されていて良いはず。
僕が便利だと思うgitコマンド
いやー暑いですねー。ということで、最近まで主に使っていたgitコマンドを紹介します。
gitコマンドに関しては短縮するaliasを書いておいた方が、生産性が向上します。おすすめです（とこれも人から教わった知識ですが）。こことかを参考にしながらやるのが良いかと思います。
git status
ーどのファイルが変更されているかを表示する。
git log
ー現在のブランチのコミット履歴を見る。
git pull upstream master
ー最新のものを上流のマスターブランチから取り込む。upstreamはウェブサービスの実際稼働しているコードがあるレポジトリと仮定している。
git push origin master
ー取り込むなら、自分のコードも上げる操作も当然必要なのでpushする。originは自分個人のレポジトリを指し、masterはブランチ名を指す。
git commit -v
ー-vを加えることによる、今回のコミットによる変更分が表示される。
git br
ー短縮していなければbranchである。ブランチの一覧を表示する。-Dで消すこともできる。
git co ブランチ名
ーcheckoutと本来打つべきだが、短縮するaliasでcoになる。指定したブランチに移動する。
git stash
ー今のブランチでコミットしていない変更分を一時的に保存する。コミットしたくないけど、ブランチをcheckoutしたい時に使用する。
git rebase HEAD ~(k+1)
ー最新のコミットから上位k件までのコミットに関して編集する。k個前まで遡ってコミットしても良いし、k個のコミットをsquashして一つのコミットにまとめてしまっても良い。
git revert コミット名
ー過去のコミットに対して、取り消すコミットをする。ちゃんとログに残るので、他の人にわかりやすい。
git cherry-pick コミット名
ー指定したコミットのみを適用する。コミットを整理したい時でコミット数が少なければ、ブランチを切り直してcherry-pickした方が早い場合もある。
検索インデックス周り（主に接尾辞配列周り）に関する基礎の話
資料リンク集みたいなものですね。不完全なので、徐々に詳しく書いていきたい記事です。
接尾辞配列がなぜ巷で「痺れる、憧れるぅ！」状態なのかを理解した。
検索速度、スケーラビリティ、網羅性の観点から優れているみたいだ。
Lucene（Solr）を扱う際は、接尾辞配列のインデックスをサポートしていないみたいです。
接尾辞配列配列の生成にO(n^2logn)というのを常識のごとくウィキペディア日本語版に書かれていたのだが、よくわからなかった。
O(nlogn)回の比較ソートが必要なのはわかるが、一回の比較にO(n)の時間がかかるとは？
・・・ここを見ている時に「文字列の比較」であることを思い出した。「あれ、nって要素の数じゃない」と一瞬思ったが、接尾辞配列においては「文字列の長さ＝接尾辞配列の要素数」であることをまた、思い出して勝手に納得した。
検索クエリの長さをmとすると、二分探索を用いればO(mlogn)での探索が可能です。それはいいんですが、その後のO(m + logn)に時間計算量の改善に関して「？」が大量に頭に浮かんできました。ここらへんが知りたいんですよ、僕は。最長一致接頭辞（Longest Common Prefix)を使う、という記述を観測するも、具体的な方法が書いていない。記述するのはいいんですが、リンク貼って頂けるとありがたいです。
O(m + logn)の謎はStackoverflowが解決してくれました。QuoraとStackoverflowは大抵の事を解決してくれます。
参考：How does LCP help in finding the number of occurences of a pattern?
少し面倒になってきたので、今は全部翻訳はしませんが、一番重要な箇所は「前処理で構築されたLCP arrayを使用する」と「クエリの各文字は必ず一回しか比較に使用されないこと」。O(mlogn)の探索の問題点は「比較の際に毎回接頭辞を比較するため、O(m)になってしまうこと」でした。それが必ず一回になるためO(m + logn)となります。
（ちなみにここらへんの話はウィキペディア英語版の接尾辞配列に載っていました）
あと残りの疑問点としては「LCP arrayはどうやって構築するか」ですね。これは英語のウィキペディアを参照すると良さそうです。英語のウィキペディアやばすぎますね。僕は日本語が大好きなのですが、僕が観測している範囲内では接尾辞配列に関しては情報量に差がありすぎますね。
Luceneを始めるにあたっての資料：
http://d.hatena.ne.jp/arahk/20101028/1288263461
http://d.hatena.ne.jp/sleepy_yoshi/20110405/p1
参考資料：
Suffix ArrayとSedue周りのお話（すごいわかりやすい、転置インデックスと接尾辞配列を用いたインデックスが違うことにはじめて気が付いた）
Suffix ArrayによるインデックスとLuceneとの性能検証
Suffix Arrayの構築アルゴリズムに関して
http://stackoverflow.com/questions/7857674/whats-the-current-state-of-the-art-suffix-array-construction-algorithm
雑記
ちなみに初心者向けと言われるこの本
- 作者: 森大二郎
- 出版社/メーカー: 日経BP
- 発売日: 2011/03/10
- メディア: 単行本（ソフトカバー）
- 購入: 8人 クリック: 1,195回
- この商品を含むブログ (27件) を見る
「簡単すぎる、ぬるいな」という方々はここらへんを見て下さい。
最近のSuffix Arrayによる全文検索について調べてみた
情報理論の定義の話
この資料を参考につらつらと書いてみます。
Lecture 6; Using Entropy for Evaluating and Comparing Probability Distributions
今までに「エントロピーは未知の値を定式化」とか他にも色々言われたけど結局よくわかりませんでした。式を見ても、よくわかならいので、例が欲しい、と行き着いた先が上の資料です。
上の資料を翻訳しただけですが、これはわかりやすかったです。
まず、僕は今NLP（自然言語処理）の領域にいるので、NLPの例に考えます。あと最近トピックモデルも勉強しているので、各文が「圧縮」、「言語モデル」、「その他」のいずれかのトピック（話題）について話しているとします。
例：
ハフマン符号すげー！ （圧縮）
ニューラル言語モデル、時間かかりすぎワロタ （言語モデル）
コミケ初日と東京湾花火大会は被っている！！！ （その他）
僕がそれぞれの話題を話す確率を仮に
圧縮：0.8
言語モデル：0.15
その他：0.05
とします。
どういう話題が出てきたかを、符号化する（1と0で表す）時、一つの話題に関して何ビット必要なのか？1ビットは1と0から成るので、一番直観的な解答は2ビットですね（2^2 = 4 > 3より）。例えば、圧縮：00 言語モデル：01 その他：10 と割り振ってみましょう。
上の例を符号列で表すと、00(圧縮) 01(言語モデル) 10(その他)と3つの話題があるので6ビットになります。
ただここではそれぞれの話題を話す確率がわかっているので、「よく現れる話題には短い符号を割り当てる」ことで、符号列が短くなりますね。例えば
圧縮:0 言語モデル:10 その他:11
とした場合、符号列は
0(圧縮) 10(言語モデル) 11(その他)
と5ビットに短くなりますね。
では理論的に最小のビット列の長さは何でしょうか？情報理論の定義がそれを導きだしてくれます。
:確率変数
:確率
Xのエントロピーとは、
これがよく教科書とかでも出てくる「情報理論的下限値」とかですね。実際に上の例を計算してみましょう。
X:話題であるとし、
H(X) = -(0.8 * log(0.8) + 0.15*log(0.15) + 0.05 * log(0.05))
=~ -(-0.258 + -0.411 + -0.216) ※下3桁で四捨五入してます
= 0.88
すなわち話題を表す符号列は一話題辺り平均0.88ビットで表せる、ということですね。「え、1ビット切ってる！？私のエントロピー低すぎ！？」と驚かれるかもしれませんが、これは「一つの話題に関してしか話さない人は話題の符号列はいらない=0ビット」より、1ビットを切っています。
つまり、上の例は理想的には約0.88 * 3 = 2.64ビットで表すことができます。5ビットの約半分ですね。どうやるんでしょうね。
ちなみに、上の定義では理論値はわかりますが、実際にどのように符号化すればいいかは教えてくれません。そのあたりの話を多分次回、符号化や圧縮の話の所で書きます。
あと、上の話題の確率が0.33ですと一話題辺り平均約1.5ビットになります。話題が豊富な人はエントロピーも高いんですね。
LOUDSの基本事項
LOUDSとは木を表現する簡潔データ構造の一つである。
以下のリンクの練習問題を全て解いたらLOUDSについての理解が進んだので、それについて簡単にメモしておく。
情報系修士にもわかるLOUDS
※ノード番号とは、木を根から（左の子優先の）BFSで辿った順番であり、indexとはビット列を配列に例えた際の添字番号の事である。
※また、rankとselectは簡潔データ構造の基本操作であるが、それらは言葉で軽く説明している
※以下特に言及しない限り1と0はビットを意味する
LOUDSの基本事項
1. LOUDS bit string (LBS、要するにただのビット列)「10」から成るスーパールートであるノード番号0を入れる
2. 0が親ノードの区切りである。
3. 子ノードの数だけ1を列挙した後、0を入れる。
子ノード番号intから親ノード番号を取得する方法：
子ノード番号intからindexは「左から数えてint番目の1が立っているindex」すなわち、子ノードindex = select(1, 子ノード番号int)
子ノードindexから親ノード番号は「左に何個0があるか」すなわち、親ノード番号 = rank(0, 子ノードindex)
親ノード番号xから子ノード番号を取得する方法：
1. 左からx番目の0のindexを取得する、すなわち index = select(0, x)
2. その次のindexから1が続く限り列挙する
それぞれの子ノードindexからそのノードの番号は「左から数えて自分自身を含めて何個1が立っているか」すなわち、子ノード番号= rank(1, 子ノードindex) + 1
LOUDSは木を表現するので、一つの子に対しては一つの親しか存在しない。そのため、エッジに関する情報は、子ノードにそのまま格納して良い。
Trie木は各エッジが文字に対応している。そのため、補助配列を用いればLOUDSでTrie木を実現することができる。
例：
（汚い手書きは気にしないでください。。。Keynoteを覚えるべきですね。。。）
LOUDSによる木の表現：
| 親ノード番号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| LBS | 10 | 1110 | 10 | 0 | 1110 | 0 | 0 | 10 | 110 | 0 | 0 | 0 |
補助配列：
| ノード番号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 文字 | なし | なし | i | a | l | n | a | i | b | e | l | s |
最近点対問題について語ってみる
2013年6月29日追記：
先に証明した補題の方では実装上遅くなってしまうことが、考えていてわかったので修正しました。
内容は表題の通り。非常に初歩的な内容なのだが、某所で説明した際に、一部の「なぜ？」という疑問に答えられなかったので、その鬱憤を晴らしてみる。
なお、Pythonで実装したコードはここにある。（あとで紹介する補題を適用していないので、このままだと遅い）
参考にしたリンクは以下の通りである。
１．Closest pair of points problem - Wikipedia, the free encyclopedia
２．Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. MIT Press and McGraw-Hill, 2009. Pages 1039-1043 of section 33.4: Finding the closest pair of points.
（第二版と第三版では載っているページが違うから、注意する）
３．UCSB Lecture Notes
（このスライドの8枚目の方が、Intro. to Algorithmsに載っていて、かつ下に述べる補題についてはわかりやすいと感じた。実装時はこのスライドを参考して、探索する点を境界線上に射影し、各点に対して高々6つの点を探索した方がよい。）
以下二点は面白そうなリンクである。
４．http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lineSweep 分割統治法を使用していない方法。ちょっと時間計算量についてまだ考えていないので、不確定
５．面白CS論文紹介まだ元論文を読んでいないが、面白そうなアイディアである。
まず（二次元における）最近点対問題とは何かを定義する。
「ある点集合が与えられた時、その中のある点対に対して、それらの点の間の距離が最小となる距離を求める」ことである。
なおここでの距離の定義はユークリッド距離とする。また、点の数をnとする
例を挙げると、点集合P = [(1,0), (1,3), (1,4), (1,8)]においては点対(1,3)と(1,4)間の距離がとなり、最小である。
最もナイーブな実装では、全ての点対を調べれば良いので時間計算量はO(n^2)であり、メモリ計算量はO(1)である。しかし分割統治法をうまく使うと、メモリ計算量O(n)で、時間計算量O(nlogn)に落とすことができる。以下そのアルゴリズムの概要を述べる。
０．利用する配列はX、Yである。
１．点集合Xと点集合YをそれぞれX軸、Y軸の座標をキーとして、ソートする。もし、Xの点数が＜3ならばペアは一ペアしか存在しないため、そのペア距離を調べ、最短距離を返す。
２．X軸において、中間値x_medianをとり、そこを分割線としてその中間値よりX座標が小さい点はX_l, 大きい点はX_rに分類しておく。なお、X_lに分類された点に対して、Y軸の座標をキーとしてソートされた点集合Y_l、またX_rに対応したY_rも保持しておく。
３．分割された点集合それぞれに対して、最短距離δ_l, δ_rを算出し、その内の小さい方をδとして保持する。
４．ここで問題になるのが、点対の片方がX_lに属し、もう片方がX_rに属しているかつ、その点対の距離がδより小さい場合である。それらの点対間の距離を算出するため、点集合Y_l, Y_rに対して、中間値x_medianの点よりx軸方向に距離δ以内に存在する点を全て取得し、その集合をY'とする。
５．Y'の全ての点pに対し、x軸方向においてδと-δ以内、かつy軸方向に-δ以内の点を取ってくる。そういった点p'に対して、pとp'間の距離δ'が距離δより小さい場合はδ=δ'と値を更新する。なお、後の補題ではそういった点p'が高々7つ（点p自体は含めないため、7つである。より工夫すれば5つ）であることを示す
なお、時間計算量を求める際に問題としては、５．において、pよりδ以内の点がどれだけあるのかが問題になってくる。仮にnこあるとし、Y'の点の最大数をnとすると、O(n^2)になってしまうため、高々定数個であることを言わなければならない。（ちなみにここの部分を説明できなくて詰まってしまった）
補題
ステップ５．において、Y'内の点pより2δ×δ（x軸に2δ、y軸にδ）の長方形内に存在する点はY'内では高々8こである。*1
証明：
中央値x_medianの点は二つ存在するとしたら、最悪のケースは片方の点がX_lに、もう片方の点がX_rに分類されたときである。（この時最短距離δ'は0となるが）。
まずステップ２．において分割された際に、X_lもしくはX_rに含まれる点対は最低でもδ以上である。（δ以下の場合は、その点対が最短距離δとなっているはずである。ただし、点対に内、片方の点がX_lに、もう片方の点がX_rに所属していた場合、点対の距離がδ未満はありうる。このケースをケースAとする。）
すなわち、点pより2δ×δの長方形の各頂点に対応する点であり、自分自身を含めれば、その点は高々8こである。
（なお、上記のケースAの場合、すなわち2δ×δの長方形内に距離δ未満の点対が存在している場合は、点の数は8こより少ない。）
（証明終わり）
実際の実装では、点対間の最短距離δを求めるだけならばδ未満を調べれば良いので、高々7n点を調べれば良い。ゆえに、ステップ５．は時間計算量O(n)で完了する。
ステップ３．における再帰の回数は、二分木の高さと等しいのでlognである。これをnこの点に対する時間計算量T(n)を再帰式で表すと(以下Intro. to Algorithms、1043ページより抜粋)
となる。
この再帰式を解くとT(n) = O(nlogn)となる。（∵ T(2) = 1, T(4) = 2*T(2) + O(n) = 2*1 + O(n), T(8) = 2*(2*1 + O(n)) + O(n), ... T(2^i) = 2^{i-1} + 2(i+1) * O(n)となり、n=2^i より i = lognであるからT(n)=O(nlogn)）なお、一番最初にソートをしているが、(比較）ソートは時間計算量θ(nlogn)で可能なので、時間計算量O(nlogn)に変わりはない。
