ぼうメモ帳

2004-05-25 しくしく

落ちた

| 落ちたを含むブックマーク

第一志望にしていた会社に振られました。う〜ん、これからの身の振り方を考えねば。とりあえず、落とされた理由が知りたい。学歴か? それとも、最終面接の印象が悪すぎたか? 最終面接では、なんとかんく緊張感が欠けた態度を取ってしまっただけに、悔いが残る。

でも、なんか思ったよりすがすがしいっていうか、付き合ってた女の子に振られたときほどのショックはないなあ。ま、その程度の志望度だったってことにしておくか。

トラックバック - http://d.hatena.ne.jp/susumu/20040525

2004-05-23 疲れた

今週の進捗状況

| 今週の進捗状況を含むブックマーク

う〜ん、研究が捗らん。

TAの採点

TAの採点を含むブックマーク

普段からもっとソースコードを大切にしてほしいと訴えているにもかかわらず、自分が採点するという大量のソースコードをチェックしなければならない立場に立つと、これほどほどかったるいものはない。

プログラムの意味的な部分に形式的検証をかけて自動で採点する、とか大量のテストパターンを駆使して入出力のブラックボックステストを行うとかすれば良いんだろうけど、それができないから悩みの種がひとつふたつと増えていく。

入力方法好き勝手、出力方法好き勝手、こんなソースコードの採点を毎週100以上もやらなきゃいけないかと思うと…

トラックバック - http://d.hatena.ne.jp/susumu/20040523

2004-05-19 まじめに研究

今週の予定

| 今週の予定を含むブックマーク

  • Balsaの調査
  • Handshake circuitsの青い本を読めるとこまで読む
  • graphsimのドキュメントをまとめる
トラックバック - http://d.hatena.ne.jp/susumu/20040519

2004-05-14 就活中だけに自粛中

就職活動をしていると、下手なことを書いて選考に影響したらどうしようなどと考えてしまい、好きなように日記が書けずにストレスだけが溜まっていきます。私の本名を検索すれば、この日記まで辿れてしまうのでなおさらです。さらに、書きたいネタがP2Pソフトネタで、いま選考結果待ちの会社が京都を本拠地とする会社なので、なおなおさらさらです。とりあえず、選考が一通り終わって落ち着いたら、P2Pソフトネタで一発何か書くぞ!!

ここ1,2ヶ月で買った本・借りた本

| ここ1,2ヶ月で買った本・借りた本を含むブックマーク

就職活動にかこつけて、いろいろと本を買い込んだけど、収穫はあまりなかった。あと他に何か買ったっけかなあ。

トラックバック - http://d.hatena.ne.jp/susumu/20040514

2004-05-09 失敗失敗

ソースコード一致度解析ツール

| ソースコード一致度解析ツールを含むブックマーク

実装しました。そして、利用したときに感じたことです。

  • 正規化の必要性
  • 統計的な何かの必要性
  • 構造解析の必要性

なお、採用したアルゴリズムは、2つのソースコードを字句で分割し、2配列のアライメントの問題へと帰着させ、ダイナミックプログラミングで解くというものです。(参考URL:http://www.genome.ad.jp/Japanese/lect/13-01.html

正規化の必要性は次の理由からです。ダイナミックプログラミングで求められる結果は、ソースコードの性質に依存した値であるということです。私のプログラムでは、比較するソースコードが長くなればなるほど、結果は大きな数字に偏り、ソースコードが短くなればなるほど、結果は小さな数字に偏ります。ですから、そのあたりを一意的に判断するために、何らかの正規化を行わなければならないと考えています。また、このことを発展させれば、統計的な何かが必要であるとも考えられます。

たとえば、あるAというソースコードと、それ以外のソースコードB1,B2,…,BNと比較したときの結果が、R1,R2,…,RNとなったとします。このとき、ソースコードが明らかに似通っているペアは、その結果が他の結果と比較して明らかにおかしい数値を叩き出している場合が多いです。ですから、その明らかにおかしいというのを見抜くためには、統計的な何かが必要です。

構造解析は次の理由から必要です。コードというのは、階層的な木構造をしています。コードAでは関数実装の並びがFA,FBとなっており、コードBではFB,FAとなっていたとします。このとき、採用した方法だと、FAまたはFBのみ一致と判断されてしまいます。FA,FBの中身が完全に同じでもです。ですから、何らかの方法で階層判定をしなければならないと考えました。

はてさて、どうしたものか。

トラックバック - http://d.hatena.ne.jp/susumu/20040509

2004-05-01 ゴールデンウィークなのに。。。

演習採点について思うこと

| 演習採点について思うことを含むブックマーク

TAの採点をやってたら、ものすごく時間がかかった。その割には、全部終わってないし。これ以上時間をかけたら、収支が合わなくなる〜。とりあえず入出力チェックを行うと思ったら、さあびっくり。どうして出力結果ばかり個性を発揮しようとするのかなあ。diffで検査できないじゃん!! 個性を発揮するなら、プログラムの構成で発揮してくれ。人のコピーして、コメントを消しただけ、変数名・関数名を変えただけ、出力フォーマットを弄っただけ、みたいのがゴロゴロ。もし、ソースコードの内容でツリーを構成したら、ルートは5ぐらいしかないんじゃないかと思うぐらい、みんな似たり寄ったり。はあ、これならコードの先頭に、「誰それと内容は同じです」って一言くれたら、採点が楽になるんだけどなあ。いっそ、内容一致度を測るツールを作って、似たコードは一括で採点しちゃおうかなあ。

ソースコード一致度測定ツール

| ソースコード一致度測定ツールを含むブックマーク

1.要件

ソースコードを解析し、その内容がどの程度他のソースコードに一致するかを測定し、その関係図を図示する。

1.1.二つのソースコードの一致度

簡易化のため、ソースコードの構文解析は行わない。まず、行単位の一致度を求める。これは、Unixコマンドのdiffのようなもの。さらに、二つの行を比較するとき、単語間のdiffも行うようにする。このときの一致度を行の一致度として取り扱う。最後に、一致度が最小となる数値の対応表を保存する。

1.2.グラフ

数十人についてのファイルを互いに比較し、その一致度からグラフ化を行う。まずは、互いのファイルの一致度を求めて、テーブルを作成する。次に、このテーブルより何らかのグラフを抽出する。どうやってグラフとするかは、具体的なテーブルの内容を見てみないとわからないので、何とも言えない。あとは、graphvizを使って図化する。

1.3.性能についての考察

1.3.1 1行あたりの実行コスト

C言語ソースコードは1行あたり、多くても10程度の単語しか存在しない。そして、一致度を求めるためには、ダイナミックプログラミングを用いてO(n2)だと思う。

1.3.2 ファイルあたりの実行コスト

一致度を求めるソースコードは、一ファイルあたり多くても100〜200行程度である。これも、ダイナミックプログラミングを用いてO(n2)ぐらいと見積もれる。

1.3.3 グラフ化あたりの実行コスト

すべてのファイル間の比較を行うと、純粋にO(n2)となる。ファイル総数は多くても40である。おそらく比較のほうのコストに比べて、図化のコストは小さいので無視できると思う。

う〜ん、そもそも、単語と行とに分ける必要はあるのか? 分けないでやってみて、遅すぎたら分けてみるか?

トラックバック - http://d.hatena.ne.jp/susumu/20040501
268033