mixi が海外ユーザの登録を Ban

あー、つまり海外のユーザは登録できなくなったという理解でよろしいですか。まぁ、自分はとっくの昔に登録しているから問題ないといえば問題ないけど。
しかし、記事タイトルに「携帯メールアドレス」はいかがなものかと思わないでもない。まぁ、十分通じるからいいといえばいいんだろうけど。

RMS

なにこの選択肢のなさは。
あー、そういや、今週の水曜日に Richard Stallman が "Free Software and Freedom: Free Software in Ethics and in Practice" というタイトルで NYU で講演するらしい。聞いてこようかなぁ。

Richard Stallman will speak about the goals and philosophy of the Free Software Movement, and the status and history the GNU operating system, which in combination with the kernel Linux is now used by tens of millions of users world-wide.

ふむ。

Yahho

Yahho って河合研だったのか*1！だったら Haskell で書かれていたに違いない(河合先生は学部3年の Haskell を使う講義を担当しているらしい)。いや、ふつうに考えてそれはないけど。
しかし、学部3年で Haskell っつうものなんだかなぁ。MIT はいきなり Scheme で不動点関数がどうとかやるらしいけど、まぁ比べるのが間違いだろうか。

*1:実物見たことないけど

Java におけるハッシュテーブルの実装

Wikipedia

主要プログラミング言語におけるハッシュテーブルの実装

  • JavaにおけるMap、HashMap、TreeMap、LinkedHashMap、Hashtable クラス(またはインタフェース)

まて。Map は実装じゃないし、TreeMap はその名のとおり木だ。

論争の弊害

discussion

Isoparametric 『嘘情報は確かにやっかいですね。
ただ、だらだらと経過が書き連ねられて、あのコメント欄のように鬩ぎ合いに発展してしまうのは、
結局ノイズや無意味な（第三者からは判断するのにややこしい）情報の羅列になるだけと思うので、
つい、落ち着いて！　とか思ってしまいます。』

こういう視点は大事かも。
ある程度知識がある人間はコメントに目を通せば大体判断が付くとは思うんだけど、そうでなければ「で、結局？」みたいなことになりかねないし、そもそもあの長大なコメントを読む人間が少なそうではある。間違い(もしくは誤解を招く記述であること)を本人が認めて、それが反映されるならいいんだけど、どうもあの件は筆者の振る舞い(および過去の履歴)を見る限りそれを望むのは無謀といえそう。
しかし、放って置くのもやはり嘘の情報を広げることになりかねないわけで*1、コメント欄で論争が起きていれば「鵜呑みにするのはまずそうだ」という判断にもつながるかも知れないとか思ったりもする。

*1:逆に言及することで返って影響力が大きくなることもありうるけど

RMQ高速化

Algorithm C

データ系列の任意区間から最小値(もしくはその位置)を取得する操作を Range Minimum Query というのだが、これは n 個のデータに対して O(n) の前処理をしておけば O(1) で計算できることが知られている。
で、その実装が九州大学の坂内さんのページで公開されているのだが、プロファイルを取ってみると log2 の計算と LSB*1の位置の計算に割りと時間を食っているようだ。
なので、ちょいとその辺をチューニングしてみたら、20% から 30% くらい高速化に成功した。プロファイル重要ですな。

--- rmq.c.orig  2006-08-24 19:26:38.000000000 +0900
+++ rmq.c       2007-03-20 13:36:51.000000000 +0900
@@ -19,6 +19,7 @@
 #include "rmq.h"
 #include <stdio.h>
 #include <stdlib.h>
+#include <limits.h>

 /* clear the least significant x-1 bits */
 static inline INT clearbits(INT n, INT x){
@@ -30,9 +31,20 @@
  * (use Bit Scan Reverse on some Pentium ? processors)
  */
 static inline INT intlog2(INT n){
-  INT res;
-  for(res = 0; n > 0; n >>= 1, res++);
-  return(res-1);
+  int i = 1;
+  int d = sizeof(INT) * CHAR_BIT / 2;
+  int s = 0;
+
+  while (d > 1) {
+    s += d;
+    if ((n >> s) == 0) {
+      i += d;
+      n <<= d;
+    }
+    d /= 2;
+  }
+  i -= n >> (sizeof(INT) * CHAR_BIT - 1);
+  return sizeof(INT) * CHAR_BIT - 1 - i;
 }

 /*
@@ -41,11 +53,22 @@
  * (use Bit Scan Forward on some Pentium ? processors)
  */
 static inline INT lsbset (INT n){
-  INT res = 0;
-  while(n % 2 == 0){
-    res++; n >>= 1;
+  int i = sizeof(INT) * CHAR_BIT - 1;
+  int d = sizeof(INT) * CHAR_BIT / 2;
+  INT y;
+
+  while (d > 1) {
+    y = n << d;
+    if (y != 0) {
+      i -= d;
+      n = y;
+    }
+
+    d /= 2;
   }
-  return(res);
+
+  i -= ((n << 1) >> (sizeof(INT) * CHAR_BIT - 1));
+  return i;
 }

 /*

*1:Least Siginificant Bit