すかすかの配列から効率良く全要素を取り出す

アルゴリズム プログラミング C言語

一番右端に立っているビットの位置を求めるアルゴリズムが載っていました。

http://d.hatena.ne.jp/siokoshou/20090704#p1
http://chessprogramming.wikispaces.com/BitScan#DeBruijnMultiplation

まさしく黒魔術!良くこんなの思いつくなぁ、と感心する事しきりなのですが、ふと、これを使えばすかすかの配列から効率良く全要素を取り出す事ができるのではないかと思い、やってみました。

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

typedef unsigned long long U64;

/*
  * 実行時間測定用
  */
double current_time,start_time;

void print_time(const char *mess) {
  struct timeval tv;

  gettimeofday(&tv,NULL);
  current_time=tv.tv_sec+tv.tv_usec*1e-6;
  fprintf(stderr,"%s: %-.5f\n",mess,current_time-start_time);
  start_time=current_time;
}

void set_timer() {
  struct timeval tv;

  gettimeofday(&tv,NULL);
  start_time=tv.tv_sec+tv.tv_usec*1e-6;
}

/*
  *  黒魔術
  */
const int index64[64] = {
   63,  0, 58,  1, 59, 47, 53,  2,
   60, 39, 48, 27, 54, 33, 42,  3,
   61, 51, 37, 40, 49, 18, 28, 20,
   55, 30, 34, 11, 43, 14, 22,  4,
   62, 57, 46, 52, 38, 26, 32, 41,
   50, 36, 17, 19, 29, 10, 13, 21,
   56, 45, 25, 31, 35, 16,  9, 12,
   44, 24, 15,  8, 23,  7,  6,  5
};

int bitScanForward(U64 bb) {
  const U64 debruijn64=0x07EDD5E59A4E28C2ULL;
  if (bb==0) {
    return 0;
  }
  return index64[((bb&-bb)*debruijn64)>>58];
}

int main(int argc,char *argv[]) {
  const unsigned int length_of_array=51200000;
  const unsigned int length_of_indexes=length_of_array/64;
  U64 *indexes=calloc(length_of_indexes,sizeof(U64));
  int *array=calloc(length_of_array,sizeof(int));
  int i;

  set_timer();
  for (i=0;i<atoi(argv[1]);i++) {
    int j,k,l;

    scanf("%d",&j);
    array[j]=1;
    k=j/64;
    l=j-64*k;
    /*
      * indexesの各要素は64個の添字を管理する。
      * j==32->indexes[0]の33bit目が立つ。
      * j==72->indexes[1]の9bit目が立つ、と言った具合
      */
    indexes[k]|=(1ULL<<l);
  }
  print_time("input"); // 入力にかかった時間
  for (i=0;i<length_of_indexes;i++) {
    int j;

    for (j=0;0ULL<indexes[i];j++) {
      int len=bitScanForward(indexes[i]);

      j+=len;
      printf("%d\n",j+64*i);
      if (len<63) {
        indexes[i]>>=len+1;
      }
      else {
        break;
      }
    }
  }
  print_time("print"); // 出力にかかった時間
  return 0;
}

argvの扱いや入力部分がいい加減ですが御勘弁を。
次のプログラムは比較用のプログラムです。単純に配列を先頭から調べているだけです。

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

/*
  * 実行時間測定用
  */
double current_time,start_time;

void print_time(const char *mess) {
  struct timeval tv;

  gettimeofday(&tv,NULL);
  current_time=tv.tv_sec+tv.tv_usec*1e-6;
  fprintf(stderr,"%s: %-.5f\n",mess,current_time-start_time);
  start_time=current_time;
}

void set_timer() {
  struct timeval tv;

  gettimeofday(&tv,NULL);
  start_time=tv.tv_sec+tv.tv_usec*1e-6;
}

int main(int argc,char *argv[]) {
  const unsigned int length_of_array=51200000;
  int *array=calloc(length_of_array,sizeof(int)),i;

  set_timer();
  for (i=0;i<atoi(argv[1]);i++) {
    int j;

    scanf("%d",&j);
    array[j]=1;
  }
  print_time("input"); // 入力にかかった時間
  for (i=0;i<length_of_array;i++) {
    if (array[i]!=0) {
      printf("%d\n",i);
    }
  }
  print_time("print"); // 出力にかかった時間
  return 0;
}

ユーザ空間での実行時間

入力要素数 黒魔術 単純探索
10000 0.037s 0.166s
100000 0.201s 0.268s
1000000 1.128s 1.044s
10000000 10.125s 8.737s

入力にかかった時間

入力要素数 黒魔術 単純探索
10000 0.088s 0.073s
100000 0.411s 0.381s
1000000 1.103s 0.942s
10000000 7.546s 5.981s

出力にかかった時間

入力要素数 黒魔術 単純探索
10000 0.007s 0.321s
100000 0.037s 0.152s(減ってる???バグ???)
1000000 0.323s 0.393s
10000000 3.064s 3.210s

要素が多くなると全体でかかった時間は黒魔術の方が長くなります。しかし、出力にかかった時間はどれも黒魔術の方が短いので、要素が多くなるとindexesに格納する所が脚を引っ張ることがわかります。
使えば速くなる、って訳でもないですね・・・。