boost::multi_arrayのランダムアクセスに注意

※下記の内容はVisual Studio2010でコンパイルしました。gcc 4.8.2でコンパイルすると結果が異なります。詳しくはコメント欄をご確認下さい。

便利なboost::multi_array

多次元配列を実装するときに便利なboost::multi_arrayですが、ランダムアクセスが遅いので注意が必要です。 この件について意外と情報が少なかったのでまとめてみました。

サンプルプログラム

#include "stdafx.h"
#include <iostream>
#include <boost/timer.hpp>
#include <boost/multi_array.hpp>

int _tmain(int argc, _TCHAR* argv[])
{
  boost::multi_array<int, 3> multiArray( boost::extents[500][500][500] );

  boost::timer t;

  t.restart();
  for ( int i = 0 ; i < multiArray.shape()[0] ; ++i ) {
    for ( int j = 0 ; j < multiArray.shape()[1] ; ++j ) {
      for ( int k = 0 ; k < multiArray.shape()[2] ; ++k ) {
        multiArray[i][j][k] = i + j + k;
      }
    }
  }
  std::cout << "ijk time = " << t.elapsed() << std::endl;

  t.restart();
  for ( int k = 0 ; k < multiArray.shape()[2] ; ++k ) {
    for ( int j = 0 ; j < multiArray.shape()[1] ; ++j ) {
      for ( int i = 0 ; i < multiArray.shape()[0] ; ++i ) {
        multiArray[i][j][k] = i + j + k;
      }
    }
  }
  std::cout << "kji time = " << t.elapsed() << std::endl;

  t.restart();
  int* it = multiArray.origin();
  for ( int i = 0 ; i < multiArray.shape()[0] ; ++i ) {
    for ( int j = 0 ; j < multiArray.shape()[1] ; ++j ) {
      for ( int k = 0 ; k < multiArray.shape()[2] ; ++k, ++it ) {
        *it = i + j + k;
      }
    }
  }
  std::cout << "iterator time = " << t.elapsed() << std::endl;
  
  return 0;
}

実行結果

ijk time = 2.293
kji time = 3.883
iterator time = 0.074

iteratorを使用することによって、ランダムアクセスより10倍以上速くなっています。

Boost C++ Librariesプログラミング第2版