平衡二分木の世界では近年では赤黒木(Red-Black Tree, RB-tree)が標準的である。追加、検索、削除がそれぞれ最悪O(log N)というすぐれものだが、場合分けが多く実装はけっこう面倒だ。

赤黒木というのはB木(Balanced tree)の一種である2-3木/2-3-4木をベースにした平衡二分木で、ノード内のリンクを赤、ノード外とのリンクを黒とラベル付けし、赤リンクの数が黒リンクの数を上回らず、黒リンクのみを数えた高さで見て平衡、つまりlog Nの高さを保証したというもの。つまり赤リンクを含めても2*log N以下に必ず納まるのだ。詳しく知りたければ調べてください。

昨年にRobert Sedgewick氏によって発表されたLLRBツリー(Left-Leaning Red-Black Tree)というのは、2-3木/2-3-4木を2分木に表現した赤黒木の赤リンクの形式に制約をかけ(左寄せする＝Left-Leaning)、一意になるようにして場合分けを少なくし、実装しやすくした赤黒木の改良版だ。赤黒木に対して性能が上がるということはないが、実装のしやすさは格段に向上しているという触れ込み。実際、Javaのソースで200行を切っており、この操作だけでパターンを網羅していることが理解できれば、かなり楽に実装できてしまう。

processingが面白そうだなぁと思ってました。ほぼJavaなんですね。なるほど。ただ、ちょっと予約語(?)が多いかなぁという気もする。たとえばwidthとかheightとか…色が変わるから分かるけどね。 書いたものがすぐに絵になって、JavaアプレットだけどWebにも乗せられるってのはまあ、楽しいかもしれませんね。 実際に試しに作ってみた最初のsketchをどうぞ。マウスカーソルに当たるとグレーになって弾が止まります。 (IEだと動かないですね…)

**This browser does not have a Java Plug-in.

Get the latest Java Plug-in here.**

ソースは以下の通り。

int N=150;
bullet[] bl = new bullet[N];
int w=640;
int h=480;

void setup(){
  size(w, h);
  background(0,0,0);
  noStroke();
  for(int i=0; i<N; i++){
    bl[i]=new bullet(w/2,h/2,10);
    float x=sin(TWO_PI/N*i);
    float y=cos(TWO_PI/N*i);
    bl[i].setdir(x,y);
  }
  // smooth();
}

void draw(){
  background(0);
  for(int i=0;i<N;i++){
    bl[i].move();
    bl[i].check_hit();
    bl[i].display();
  }
}

class bullet{
  float sz;
  float x,y;
  float dx,dy;
  boolean bound=true;
  boolean stop=false;
  bullet(float init_x, float init_y, float init_sz){
    sz=init_sz;
    x=init_x;
    y=init_y;
  }
  void display(){
    if(stop){ fill(102); }else{ fill(255); }
    ellipse(x,y,sz,sz);
  }
  void setdir(float ndx, float ndy){
    dx=ndx;
    dy=ndy;
  }
  void move(){
    if(stop) return;
    x+=dx;
    y+=dy;
    if(bound){
      if(x<0 || x>width){ dx*=-1; }
      if(y<0 || y>height){ dy*=-1; }
    }
  }
  void check_hit(){
    if(abs(x-mouseX)<sz/2 && abs(y-mouseY)<sz/2){
      stop=true;
    }
  }
}

最近は久々に独身生活ですので更新が連日の長文になります。この独身生活で、右上のバナーもやっと修正できました。

成長した矢島の完全移籍での復帰も良いニュースですが、ACLの組み分け出ましたね。対戦相手の国自体はまあ枠の割り振りから予想できたことで、中国韓国オーストラリア。韓国の浦項は名門ですね。他はまーちょっとよく知らないクラブですね。ACLに出てくるからには強いのだとは思いますが。初戦はアウェイホームで天津泰達と、3/11です。中国は広いのにタイムゾーンは1種類、日本との時差が1時間だそうです。おもしろいですね。

川崎は来季(2009シーズンという意味です)から高畠監督がヘッドコーチに退き、関塚監督が復帰してACLに挑みます。

私は関塚信者だからいいけど、高畠ファンは関塚監督復帰をどう思っただろうか。自分としては高畠さんには2004の祝勝会でタオルをくれた恩義もありますが、やはり関塚信者なのですね。

高畠監督時代に残した成績は非常に良いもの。最終戦まで可能性を残しましたしね。そう言えば最終戦前の私の口癖は「優勝するのに必要なのはビッグスワンで勝つことではなかったし、日本平で勝つことでもなかった、ましてや万博で勝つことでもなかった。むしろガスや大宮に勝つことですらなかったんだよえへへ」というものでした(笑)。日本平で負けていては優勝なんかできない、みたいに考えてた歴史もあったわけで。

正月休みはほぼ毎日等々力緑地を散歩してました。トーマス転炉はいつ見てもいいですね。あのあたりから見えるスタジアムの姿も好きです。

というわけで、等々力の大改修署名について。昨年だけで目標以上の12万人の署名が集まったそうで、よかったですね。そして2008シーズンの準優勝の賞金から1000万円が改修費用として川崎市に寄付されたそうです。来年ACLとCWCを取ったら7億くらいの賞金が手に入りますよ。これこそ取らぬ狸のアレですな。。。

本件について私は正直なところ何もできませんし、署名が集まる前にどうのこうの言うのは気がひけたので、今になってから書いておきます。真面目な話ですよ。いろいろ思うところがあるんです。

等々力の設備については市にメールで意見したことがあります。施設はすぐに直せないにしても、運用面ではすぐに改善してくれましたので、ちゃんと対応してくれるんだなぁと思いました。たぶん、改修する時には施設に関する要望も反映してくれるんじゃないかな。

1/7.5秒の間隔で連写された912x684の画像が縦横4x4個、16コマぶんつながって1つの画像ファイルになる、というのがS連写/M連射の仕様。Sはシャッターボタンを押してから1/7.5 x 16 = 約2.13秒間、Mはシャッターボタンを離してから1/7.5 x 16 = 約2.13秒間。1/7.5ということは、7.5fpsだ。

動画モードでは30fpsの640x480のMotionJPEGで撮れて音声も入るから、動画が欲しいならS/Mの連写を使うよりは動画のほうが断然良い。解像度はS/M連写のほうが1.425倍も良いが…S/Mではない普通の連写の場合はfpsはさらに悪化するが画素数が多いのでそこはメリットになると思う。

まあ、S/M連写してしまった画像を切り取って動画にすることを考えると、画像を分割して、ffmpegでエンコードすればよい。たとえばMotionJPEGの場合は以下の通り。

ffmpeg –r 7.5 –i “$tmpdir/$base%02d.jpg” –vcodec mjpeg –sameq out.avi

私にとって、これまでのフロンターレで最も自分に重ねられることのできた選手。原田拓が川崎を去ることになった。原拓好きというのは川崎においては珍しいと思われるかもしれないけど、好きな理由は上記の通り、なんとなく存在が自分に似てるかなぁということ。似てるのは容姿ではないですよ(笑)。しかしフロンターレって、自分に似てると思える選手はほとんどいないんですよね。遠いようで近いようでやっぱり遠い、そんな存在なんです。その中にあって原田が一番近いと思ったわけですね。

ファン感ではサインをもらって写真も撮らせてもらいましたし、昨日も最後に握手してもらいましたが、いい人でした。「ありがとう」とだけ言いました。

大橋加入以前はFKが最も上手く、大宮戦ではビューティフルゴールを決めてトニーニョのオウンゴールを防いでその名を轟かせたし、ACLで決勝トーナメント進出を決めた「はつのり」試合でも貴重な得点をゲット。あの試合の原田はまさにキレキレでしたな。そのあとしばらくするとサテでの出番が主になりました。今季はリーグ戦に2試合4分の出場でイエロー1枚ゲット、ナビでは出番がありませんでした。

Jのサテは実戦の場としては試合数も少ないですし、ユースを使ってくるチームもあって相手にムラがありすぎ、モチベーション的な問題も。移籍先にもよりますが、川崎を出ること自体は原田本人にとっては悪くない話になるのでは、と思います。

by king man

感極まった涙声の我那覇よりも噛んでましたよ。送別会にて。

今後の成長に期待です。

それにしても、箕輪が川崎を出るとはねぇ。レンタルの時にも驚いて、いまだに言ってますけど。

3点差での勝利がノルマだった試合。3点差は達成できませんでしたが、勝ってヴェルディをJ2自動降格に突き落とし、名古屋が引き分けだったため、2位を確保。来季はまたACLに参戦です。結果的には鹿島が勝ったのでどうしようもなかったとは言え、3点差を達成できなかった事実は大きいと思います。鹿島は負けても優勝だったわけで、拍子ぬけもいいとこだったでしょう。これで鹿島が負けて優勝していたら、この日の記憶は悔やんでも悔やみきれない傷として残っていたはず。

今シーズンの川崎にはいろいろトラブルがありまして、しかも2006年と違って強豪の一角を占めると他チームから警戒されていたはず。それで2位というのは立派です。初めて最終節まで優勝の可能性を残した。しかし鹿島もACLの予選・トーナメントを勝ち進み、小笠原や中田といった中心選手を怪我で失う、スタジアム内の騒動などいろいろあったわけで、それを乗り越えてのリーグ優勝。これはもう我々の数段上を行っていると認めるほかありません。

ずいぶん圧倒されましたが、川島が大当たりで、守備も粘って0に抑えて勝ちを掴んだ。最終節を前にして首位との勝ち点差3、得失点差は4。鹿島が負けて川崎が3点差以上で勝てば首位の鹿島を抜けるという状況。鹿島が負ける可能性は低く、名古屋もいるのでほとんど絶望的ではあるものの、最終節まで可能性を残した。2008年は川崎史上もっともJ1優勝に近づいたシーズンに！！

試合のほうはヴィトールが怪我で菊地を使った4-3-3でスタート。ヴィトール来日以前の形ですね。これで調子が良かったこともある。勝負所で大橋や黒津を投入するという作戦だろう。

キックオフ。オフサイドをかいくぐったテセにジュニーニョからのスルーパスが通り、あっさり先制1-0。このあと前半20分くらいまでは一進一退、20分以降は神戸がホームの川崎を圧倒するという展開。しかし得点を許さず、1点リードのままどうにかハーフタイムまで逃げ込んだ。前節に目立っていた勇介の前進も頻度が少なく、明らかに悪い内容。どうにか修正しないと…