プログラミングの作業に何の価値も見出せなくなってしまったd金魚による日記 このページをアンテナに追加 RSSフィード

 iTunes Music Store(Japan) なかのひと あわせて読みたいブログパーツ
|

0001 | 00 |
2004 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 |
2008 | 01 | 02 | 03 | 05 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 |
2010 | 03 | 04 | 06 | 07 | 09 | 10 | 11 |
2011 | 01 | 02 | 10 |
2012 | 04 |
2013 | 01 | 05 | 06 | 07 | 08 | 10 |
2014 | 02 | 03 | 05 | 09 |
2015 | 04 |
2016 | 09 | 11 | 12 |
はてな一覧
アンテナに追加
私のアンテナ
私のダイアリー
私のアーカイブ
私のアイデア
私のブックマーク
私のグループ
私のキーワード
ニュース系、今まで続いているシリーズモノの読み物
dKingyo Utility Toolkit Projectのリリース情報
やっぱり暗号化は大人の味(笑)
プログラムのパッキング方法を調べよ
ココが厳しいよMinGW
ライブラリアン通信
ゲームプログラミングどうしよう
CRCについて
ビット演算練習
d金魚の今更Ajax
Windows Tips
VC6 Tips
Win32 WTL Tips
Ruby for C++ User
Ruby Tips
今日のRubyで嵌った事
正規表現PIECE
書きかけ
続く・・・

私のダイアリーの人気記事
新しくブックマークされた記事


あまり、役に立たなそうな個人的に調べた情報や妄想に耽った事、今 勉強している事ヒソヒソと公開していたりします。 | 登録してくれている方々 | d金魚にメール | 当サイトは640x480の画面解像度に対応しています。
日記へのリンク、アンリンクはフリーですが、selfタグのついている部分のコンテンツの引用はご遠慮願います。ご協力よろしくお願いします。


 | 

2004-08-22 空いているメモリに効率的にデータを挿入する方法

[][][]空いている領域に効率的にデータを挿入する方法 空いている領域に効率的にデータを挿入する方法を含むブックマーク 空いている領域に効率的にデータを挿入する方法のブックマークコメント

ども、久々です。d金魚です。

今回は私の考えたコンテナについてのお話です。

ゲームを作るとき、必ず、メモリプールを作って、そこから各オブジェクトメモリを割り当てたりしますよね^^

メモリプールと言えば、

struct DATA{
  BOOL flag;
  int x,y;
  int data,id;
};

//グローバルな領域にでも宣言する。
DATA pool[100];
//検索するプログラムはこんな感じ
for(int i=0;i<100;i++){
  if(pool[i].flag==FALSE){
    pool[i].flag = TRUE;
    return i;
  }
  return -1;
}

こんな感じのプログラムしか当時は知りませんでした。

効率的な方法は無いものだろうか・・・。と、高校一年の時に考えた事があります。

そこで、条件を列挙して考える事にしました。

  • 先にメモリを確保しておく
  • フラグは使わない
  • 線形探索をしない
  • 速く空き領域を知る事が出来る。
  • どんな状態でも挿入、削除が簡単に出来る。

というルールを設け、考えた結果、

  • 空き領域を記憶しておく

という考えにたどり着きました。*1

もちろん、このようなライブラリは既にあるのでは?と思われるかもしれませんが、私が知る限りありませんでした。

例えば、

  • std::vector イテレータが無効になる。削除すると詰める処理が行われる。
  • std::list 双方向リストなのでポインタ2つ分*2無駄になる。
  • std::map std::set 二分木なんて要らない。
  • std::deque 挿入とかは結構イイ感じだが、要素の削除が遅そう。*3
  • boost::pool 直接ポインタをいじる事になり、コンテナとしては使いにくい。
  • glibのmemchunk まだ、触っていないが、これもboost::poolと同

と、まぁ、やっぱり何かとダメだったんですよ^^;

で、その試行錯誤で生まれたのがdKingyo_ArrayOneByOneというヘナチョコクラスでした。

それを改良してarray_onebyoneというテンプレートクラスも出来ました。*4

さらに、仕様をきめて組んでみる事にしました。

  • 配列の空き領域への配列の添え字(以下 参照ID)をStackに入れておく。
  • 挿入するときはStackから空き領域を得る、そして参照IDを返す。
  • 削除するときは参照IDを受け取り、そのIDをStackに返す。
  • 初期化フラグによって自動的に内部バッファが動的拡張されたりする。
  • バッファをいつでもリサイズする事が出来る。(しかし、内部にデータがある場合はバッファを小さくは出来ない。)

そして、今日、C言語版ArrayOneByOneを作ったのでアップしておきます。

BSD Licenceでご自由にお使いください。m(_ _)m

ではでは。

本体

http://cvs.sourceforge.jp/cgi-bin/viewcvs.cgi/dkingyoutility/dkutil/dkutil_c/dkcArrayOneByOne.c

http://cvs.sourceforge.jp/cgi-bin/viewcvs.cgi/dkingyoutility/dkutil/dkutil_c/dkcArrayOneByOne.h


サンプル


void Test_ArrayOneByOne(){
  const int num = 10;
  int i=0;
  int id[num];
  DKC_ARRAY_ONEBYONE *p = dkcAllocArrayOneByOneStatic(sizeof(int),num);
  
  {
    for(i=0;i<num;i++){
      id[i] = dkcArrayOneByOnePush(p,&i);
    }
    for(i=0;i<num;i++){
      int temp;
      dkcArrayOneByOneReference(p,id[i],(void *)&temp);
      printf("id[%d]==%d -> %d,\n",i,id[i],temp);
    }
    printf("\n");
  }

  {
    //開放
    for(i=0;i<num;i+=2){
      dkcArrayOneByOnePop(p,id[i]);
    }
    //挿入
    for(i=0;i<num/2;i++){
      id[i*2] = dkcArrayOneByOnePush(p,&i);
    }
    //次はもう入らないので-1を返すはず
    dkcmNOT_ASSERT(-1 != dkcArrayOneByOnePush(p,&i));
    for(i=0;i<num;i++){
      int temp;
      dkcArrayOneByOneReference(p,id[i],(void *)&temp);
      printf("id[%d]==%d -> %d,\n",i,id[i],temp);
    }
    printf("\n");
  }

  dkcFreeArrayOneByOne(&p);

}

*1:イヤ^^;普通は皆さん、そう考えるはずですが、当時の私はこれは画期的な方法だと思ったのです・・・。

*2:32bit機だと8バイトだよね?

*3:例えば中ほどの要素を削除するとか

*4:詳しくはdkutilにて http://www.vector.co.jp/soft/win95/prog/se309230.html

 | 
Program | Debug | dKingyo Utility Toolkit | library | D言語 | 御本とか | 備忘録 | テクニック | WayBack | 格言 | 英語 | 他力本願 | news | software |

デースケドガー