RMQ高速化

データ系列の任意区間から最小値(もしくはその位置)を取得する操作を 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