Floating on the lake

2008年5月15日木曜日

zsh と FDclone

zsh を使うようになってから, なぜか FDclone が使えなくなった. "malloc(): Cannot allocate memory" というメッセージが出て FDclone が死んでしまったのだ. その原因を調べてみたところ, zshrc に HISTFILE と HISTSIZE というのを書いていて, ここで zsh の履歴の設定をしているのだが, この環境変数が FDclone も使っていることが原因だったと分かった.

zsh のために "export HISTSIZE = 100000" と設定していたが, これを FDclone も読み込み, しかも, FDclone 内部では HISTSIZE を short型で取っていたため, 100000 があふれて -31072 になってしまっていた. そのせいで, malloc(-31072) というのを実行して死んだのだ.

解決法としては, FD_HISTFILE と FD_HISTSIZE という環境変数を設定してやればOK.

2008年5月12日月曜日

valarrayのconstructorとresize

valarrayの各要素に同じ値を入れる方法として constructor を使う方法と resize を使う方法があるが, そのインターフェースの違いに戸惑ったのでメモ.

valarray(const T& v, size_t num)
valarray.resize(size_t num, const T v = T())

このように, 引数の順番が逆になっているのに気づいていなかった. T と size_t が異なればコンパイル時にエラーが出るが, そうでない場合はそのままバグになるので気をつけないと.

例:

01: #include<valarray>
02: #include<iostream>
03:
04: using namespace std;
05:
06: int main(void){
07:     valarray<char> v('a', 5);
08:     for(int i = 0; i < v.size(); ++i) cout << v[i]; cout << endl;
09:
10:     v.resize(5,'b');
11:     for(int i = 0; i < v.size(); ++i) cout << v[i]; cout << endl;
12:
13:     return 0;
14: }

2008年5月11日日曜日

C++のテンプレートに悩む

C++のテンプレートにはまった. 下のようにテンプレートの片方のパラメータの特殊化しようとしたが, コンパイルが通らない... C++難しいなあ.

(a.cpp)

01: #include <iostream>
02:
03: using namespace std;
04:
05: template<typename T, int N>
06: struct A{
07:     int val() const;
08: };
09:
10: template<>
11: template<typename T>
12: int A<T,1>::val() const{
13:     return 1;
14: }
15:
16: int main(void){
17:     A<int,1> a;
18:     cout << a.val() << endl;
19:     return 0;
20: }

環境: gcc version 4.2.1 20070719 [FreeBSD]


a.cpp:12: error: invalid use of incomplete type 'struct A'
a.cpp:6: error: declaration of 'struct A'
*** Error code 1

2008年5月10日土曜日

Windows XP SP3

Windows XP SP3 を入れようとしたが, インストールの途中でブルースクリーンが出て失敗. うーん, どうしたものか. 情報を集めないと.

追記(5/11):
PCは ThinkPad X40 なのだが, SP3 を入れる前にソフトウェア導入支援を起動してみたら, Windows のパッチが「重要」として挙がっていたので, それをまず入れてみた. すると SP3 が無事にインストールできた. 普通のWindowsのパッチは「KB???」の形式の名前がついているが, 今回のパッチはThinkPad専用とのことで「Q???」の形式の名前だった. これが効いたのだろうか?

2008年4月29日火曜日

Left-Leaning Red-Black Tree part2

前回の Left-Leaning Red-Black (LLRB) Tree の Haskell のコードがきちんと動くことを大体確認した. HaskellのData.Setと比べた特徴は以下の通り.

insert と member は LLRB の方が早い.
delete は Data.Set の方が早い.

今後の課題としては, Data.Set にある集合演算を LLRB で実装するのも面白いかも.

LLRB の delete を Data.Set よりも早くしようと試行錯誤したがうまくいかなかった. Haskell のチューニングの難しさを実感した. なかなか直感通りにいかなくて大変だ.

2008年4月28日月曜日

Left-Leaning Red-Black Tree

Left-Leaning Red-Black Tree [PDF] というのを見つけて, 実装が簡単だと書いてあったので, 最近練習中のHaskellで書いてみた. PDF に所々ミスがあるし, Haskell に慣れてないのもあって, あんまり簡単ではなかった. まだきちんと検証もしていないがさらしてみる. とりあえず, delete が member でない要素を与えられたときにエラーを返すのは仕様. deleteはPDFに載っているのとは少し変える必要があった上に, 書き直しにかなり悩んだので間違っているかも.

module Main where

data Color = Red | Black deriving (Show, Eq)
data LLRB a = Null | Branch !Color !(LLRB a) a !(LLRB a) deriving (Show)

member :: Ord a => a -> LLRB a -> Bool
member _ Null = False
member x (Branch c l y r) =
    case compare x y of
 LT -> member x l
 GT -> member x r
 EQ -> True

null :: LLRB a -> Bool
null Null = True
null _   = False

empty :: LLRB a
empty = Null

singleton :: a -> LLRB a
singleton x = Branch Red Null x Null

insert :: Ord a => a -> LLRB a -> LLRB a
insert x root = make_black $ insert' x root

insert' :: Ord a => a -> LLRB a -> LLRB a
insert' x Null = singleton x
insert' x h@(Branch _ (Branch Red _ _ _) _ (Branch Red _ _ _)) = insert' x $ colorFlip h
insert' x h@(Branch c l y r) =
    f2 $ f1 $ case compare x y of
 LT -> Branch c (insert' x l) y r
 GT -> Branch c l y (insert' x r)
 EQ -> h
    where 
    f1 t@(Branch _ _ _ (Branch Red _ _ _)) = rotateL t
    f1 t = t
    f2 t@(Branch _ (Branch Red (Branch Red _ _ _) _ _) _ _) = rotateR t
    f2 t = t

findMin :: LLRB a -> a
findMin (Branch _ Null x r) = x
findMin (Branch _ l x r) = findMin l
findMin Null = error "LLRB.findMin: empty tree has no minimal element"

findMax :: LLRB a -> a
findMax (Branch _ l x Null) = x
findMax (Branch _ l x r) = findMax r
findMax Null = error "LLRB.findMax: empty tree has no minimal element"

deleteMax :: LLRB a -> LLRB a
deleteMax root = make_black $ deleteMax' root where

deleteMax' :: LLRB a -> LLRB a
deleteMax' h = let t' = apply_rotR h in
    if isRightNull t' then Null else (fixUp . f . apply_mRR) t' where
    f (Branch c l x r) = Branch c l x (deleteMax' r)

deleteMin :: LLRB a -> LLRB a
deleteMin root = make_black $ deleteMin' root where

deleteMin' :: LLRB a -> LLRB a
deleteMin' (Branch _ Null _ _) = Null
deleteMin' h = (fixUp . f . apply_mRL) h
    where
    f (Branch c l x r) = Branch c (deleteMin' l) x r

delete :: Ord a => a -> LLRB a -> LLRB a
delete x root = make_black $ delete' x root

data NodeCond = NLeft | NRight | NBottom

delete' :: Ord a => a -> LLRB a -> LLRB a
delete' _ Null = error "LLRB.delete: element is not the member"
delete' x h@(Branch c l y r) =
    fixUp $ case compare x y of
 LT -> (f . apply_mRL) h
     where
     f (Branch c l y r) = Branch c (delete' x l) y r
 GT -> (f . apply_mRR . apply_rotR) h
     where
     f (Branch c l y r) = Branch c l y (delete' x r)
 EQ -> case nodecond h of
     NBottom -> Null
     NLeft -> let z = apply_mRL h in
  if eq x z then delleft z else delete' x z
     NRight -> let z = (apply_mRR . apply_rotR) h in
  if eq x z then delright z else delete' x z
     where
     eq a (Branch _ _ b _) = a == b
     nodecond (Branch _ Null _ Null) = NBottom
     nodecond (Branch _ (Branch _ _ _ _) _ _) = NLeft
     nodecond (Branch _ _ _ (Branch _ _ _ _)) = NRight
     delleft  (Branch c' l' x' r') = Branch c' (deleteMax' l') (findMax l') r'
     delright (Branch c' l' x' r') = Branch c' l' (findMin r') (deleteMin' r')

--
-- Helper
--
apply_mRL t@(Branch _ (Branch Red _ _ _) _ _) = t
apply_mRL t@(Branch _ (Branch _ (Branch Red _ _ _) _ _) _ _) = t
apply_mRL t = moveRedLeft t

apply_mRR t@(Branch _ _ _ (Branch Red _ _ _)) = t
apply_mRR t@(Branch _ _ _ (Branch _ (Branch Red _ _ _) _ _)) = t
apply_mRR t = moveRedRight t

apply_rotR t@(Branch _ (Branch Red _ _ _) _ _) = rotateR t
apply_rotR t = t

isRightNull t@(Branch _ _ _ Null) = True
isRightNull t = False

make_black :: LLRB a -> LLRB a
make_black (Branch _ l x r) = Branch Black l x r
make_black Null = Null

fixUp :: LLRB a -> LLRB a
fixUp = f3 . f2 . f1 where
    f1 t@(Branch _ _ _ (Branch Red _ _ _)) = rotateL t
    f1 t = t
    f2 t@(Branch _ (Branch Red (Branch Red _ _ _) _ _) _ _) = rotateR t
    f2 t = t
    f3 t@(Branch _ (Branch Red _ _ _) _ (Branch Red _ _ _)) = colorFlip t
    f3 t = t

moveRedRight :: LLRB a -> LLRB a
moveRedRight h = f $ colorFlip h where
    f t@(Branch _ (Branch _ (Branch Red _ _ _) _ _) _ _) = colorFlip $ rotateR t
    f t = t

moveRedLeft :: LLRB a -> LLRB a
moveRedLeft h = f $ colorFlip h where
    f (Branch c l x r@(Branch _ (Branch Red _ _ _) _ _)) = colorFlip $ rotateL $ Branch c l x (rotateR r)
    f t = t

colorFlip :: LLRB a -> LLRB a
colorFlip (Branch c (Branch c1 l1 x1 r1) x (Branch c2 l2 x2 r2)) =
    Branch (fl c) (Branch (fl c1) l1 x1 r1) x (Branch (fl c2) l2 x2 r2)
    where
    fl Red = Black
    fl Black = Red
colorFlip _ = error "LLRB.colorFlip: tree must have 3 nodes at least"

rotateL :: LLRB a -> LLRB a
rotateL (Branch c l x (Branch c' l' x' r')) =
    Branch c (Branch Red l x l') x' r'
rotateL _ = error "LLRB.rotateL: tree must have 2 nodes at least"

rotateR :: LLRB a -> LLRB a
rotateR (Branch c (Branch c' l' x' r') x r) =
    Branch c l' x' (Branch Red r' x r)
rotateR _ = error "LLRB.rotateR: tree must have 2 nodes at least"

     
-- 
-- test 
--

tree :: Int -> LLRB Int
tree 0 = empty
tree (n+1) = insert (n+1) (tree n)

main :: IO ()
main = do
    print $ member 1 $ (iterate deleteMax (tree 100000)) !! 100000

2008年4月26日土曜日

Firefoxの反応が遅い

最近, 研究室用のマシンの FreeBSD 7-stable 上の linux-firefox の反応が遅くなった. Ctrl-T で新しいタブを作成しようとしても, キーを押してからタブができるまでに数秒のタイムラグが発生するのだ. ちょっとしたら, どこかで修正されるかなと思って我慢していたけど, 改善されないので, 諦めて 6-stable に戻った. 6-stable 上ならキビキビ動く. ちなみに, 後輩の Debian 上の Firefox でも同様の現象が起きていた. Linux用の Firefox 特有の問題なのだろうか.

あと, 後輩にC言語のコールグラフを生成する方法を聞かれたので, 調べてみたら gprof2dot というのを見つけた. なかなか便利そうだ.

Floating on the lake

2008年5月15日木曜日

zsh と FDclone

2008年5月12日月曜日

valarrayのconstructorとresize

2008年5月11日日曜日

C++のテンプレートに悩む

2008年5月10日土曜日

Windows XP SP3

2008年4月29日火曜日

Left-Leaning Red-Black Tree part2

2008年4月28日月曜日

Left-Leaning Red-Black Tree

2008年4月26日土曜日

Firefoxの反応が遅い

プロフィール

ブログアーカイブ

Search

2008年5月15日木曜日

2008年5月12日月曜日

2008年5月11日日曜日

2008年5月10日土曜日

2008年4月29日火曜日

2008年4月28日月曜日

2008年4月26日土曜日

プロフィール

ブログ アーカイブ

Search

ブログアーカイブ