vector

昨日バグっていて困った問題は一応解決した.

理由は分からないが, vectorにつっこんだ要素のメンバ変数をいじるメソッドを呼び出したことが悪かったらしい. しかし, 理由が分からない.

istreamとmudflap

プログラムのデバッグをしようとしてmudflapを使ってみると, エラーメッセージが出るわ出るわでびっくり. 結構気を使って実装していたのになあと凹む.

それで, そのデバッグをしていたところ, mudflapのエラーメッセージの原因がistreamにあるらしいことが分かった. 以下にエラーメッセージが出る最小のコードを載せる. ポイントは is.eof() を operator>> の中で読んでいることらしい. これを除くとメッセージは消える.
# is.fail()を呼んでもエラーが起きる.

さあ, 原因は分かったので対策はどうするか考えないといけないが, 明日の発表資料が未完なので, そっちに移る.

問題のコード

#include<iostream>

using namespace std;

class A{};

istream& operator>>(istream& is, A& a)
        { is.eof(); return is; }

int main(void){
        A a;
        cin >> a;
        return 0;
}

mudflapのエラーメッセージ (g++4.2 on FreeBSD 6-stable)

mudflap violation 1 (check/read): time=1191946554.020591 ptr=0x2821c0a0 size=4
pc=0x28085c12 location=`c.cpp:7 (operator>>)'
[0x0x28083a7a]
number of nearby objects: 0

円の交差判定2

新しいテーマを考えなければならないんだけど, いいネタが思い浮かばないので, 前々から思っていたアイデアをいろいろ実装して円の交差判定の高速化を試した. 走査線法とバケットソートの組み合わせ. 理論的には, オーダーの改善はできていないけど, 簡単な実験の結果だと, 単純にバウンディングボックスのみを使う場合に比べて, 数倍から数十倍の改善が見られたの満足. 教授にこれを報告しよう.

円の交差判定

今の研究の中で大切なパートとして, 「円の交差列挙問題」がある.

n枚の円が与えられた時に, 交差する円のペアを全て列挙する. (ただし, 円の半径は異なってもよい)

Preparata & Shamosの本によると, 交差するペアの数をKとしたとき, 下界はΩ(n log n + K)になる. 現在僕が困っているのは, この最適なオーダーのアルゴリズムが知られているかどうかということ. この本には, 長方形の場合の最適なオーダーのアルゴリズムが紹介されている. また, 線分の場合はBalabanによって記憶量的にも最適なオーダーのアルゴリズムが提案されている.

ところが, 円の場合の最適なオーダーのアルゴリズムが見つからない. それっぽいキーワードでググっても, 別の問題の話ばかりなのだ. 仕方なく, 簡単なアルゴリズムを考えて実装してみた. 計算量はO(n^2)でナイーブな場合と変わらないけど, 実験では数倍早くなった. なんかめっちゃ地味なことしてるわ.

CPUの温度

研究室用の新マシンを買ったときに問題になったのがCPUの温度。
BIOSで確認すると, 起動直後で50度を越えるので驚いた。
自宅の似た構成のマシンでも40度はなかなか越えないからだ。
そんなこんなで, 買った店に連絡して調べてもらったが
結局原因も解決法も分からず, そのときはCPUのファンを高性能な
やつに交換して終わった. 本当はmbmonでも調べるべきだったのが,
マザーボードが対応していないらしく温度を調べられなかった.

さて, 最近coretempがMFCされたので, これを使ってCPUの温度を
調べてみた. csup & make world でシステムを新しくする.
そしたら,

kldload coretemp

で準備完了. あとは

sysctl dev.cpu

をして, "coretemp"の欄を見れば温度が出た.
これによると, 僕のマシンのCPU温度はBIOSでは50度を越えるけど,
coretempでは30度程度で普通ということになった.
マザーボードの温度センサーがおかしいのかな?

PDF viewer

月末の発表を終えて, 発表地獄は一段落.
これで, 腰を据えて研究に取り組めるわー, と安心してたら,
教授から, 論文をすぐに2本書くようにと言われて凹む.
11月に予定していた海外旅行はあっさりキャンセル(涙).

さて, 論文のネタを見つけるためにサーベイを泥縄でしてます.
そんなときに, Adobe Readerが意外に遅いよなあと思って,
なんとなくWindowsにPDF-XChange Viewerというものを
入れてみた. これが予想外にサクサク動くので感動した.
しかも, タブ対応というのがうれしいね.
論文をたくさん開いても安心さ!

と言ったものの, メインのマシンはFreeBSDなので,
X Window対応のタブ付きPDFビューワーが急に欲しくなった.
Adobe Readerの代替はXpdf, Evince, KPDFなのだが
どれもタブ対応じゃなくて残念.
GTK+Cairoベースで作ってやろうかなと一瞬思った.
でも, そんな時間ないよ〜.

sortの比較

挿入ソートは, ほとんどソート済みのデータ列のソートが高速にできる
性質があるのだが, それがどれくらいなのかを簡単に調べてみた.

比較は, STLの std::sort(クイックソート)と
std::stable_sort(マージソート)と
std::__insertion_sort(挿入ソート).

100000のデータ列を20回ランダムにスワップしたものをソートすると
いうのを100回繰り返した.

結果からいうと, std::sortの圧勝.
たしかにスワップ回数が10以下なら挿入ソートに分があるが,
O(N^2)のアルゴリズムなので, スワップ回数が増えると急激に
計算時間がかかる.
マージソートはO(N log N)のアルゴリズムなので傾向はクイックソート
と同じだが, 計算時間は倍くらい遅かった.

データ列がほとんどソート済みという確信でもない限り,
素直にstd::sortを使うのが無難そうだ.