| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
|
//いわゆるビットマップは、ビットを使用して要素に対応する値をマークし、キーは要素です。データはBit単位で保存されるため、保存容量を大幅に節約できます。
/*
N =1 の場合、メモリ空間を int a[2]; として適用します。 並べ替えまたは検索する必要があるものの総数が N=10000000 であると仮定すると、適用する必要があるメモリ領域のサイズは int a[1 + N/32] です。ここで、a[0] は占有します。メモリ内の 32 は、10 進数 0 ～ 31 などに対応します:
1. 配列 a: n/32 の 10 進数の 0 ～ N に対応する添え字を見つけます。
2. 0 ～ 31 に対応する 0 ～ N の数字を見つけます: N%32=M
3. シフト 0 ～ 31 を使用して、対応する 32 ビット ビット 1: 1< 例: 3個保存したい場合 (1) 添え字 30/ 32 = 0; を a[0] に入れます。
a[0] に対応する 10 進数 0 ～ 31 は、まず 10 進数 n を 32 の余りに変換します。これは、配列 a に対応する添字に変換できます。たとえば、n=24、n/32=0 の場合、配列 a の 24 に対応する添え字は 0 になります。たとえば、n=60、n/32=1 の場合、配列 a の 60 の添字は 1 になります。同様に、配列 a の 0 ～ N の添字を計算できます。 2. 0 ～ 31 に対応する 0 ～ N の数字を見つけます。
0 ～ 31 に対応する数値を M として見つけ、M ビットだけ左にシフトします。つまり、2^M に設定します。 これから、10,000,000 ビットが占めるスペースを計算します。 1バイト = 8ビット 1kb = 1024バイト 1mb = 1024kb 占有スペースは: 10000000/8/1024/1024mbです。 おそらく 1mb を少し超える程度です。 */ クラスビッグマップ{ //保存するには 2 バイトを使用してください プライベート $マスク = 0x1f ; プライベート $bitsperword = 32; //シフトするビット数は 5 pow(2,5) = 32 です プライベート $shift = 5 ; //データを保存する配列 パブリック $bitArray = array(); /** $i に対応する数値はゼロにリセットされます */ 関数クリアビット($i){ ////すると、現在のバイトの指定されたビットは0に設定され、相手の配列の他のビットは&以降変更されません。これが1の素晴らしい使い方です // $i>>ここでの SHIFT は intval($i /32) と同等です ; // ここでの $i & $this->mask は $i % $this->mask と同等であり、剰余を取ります @$this->bitArray[$i >> $this->shift] &= ~(1<<($i & $this->mask)); } /** $i に対応する数値は 1 に等しいです */ 関数 setbit($i){ @$this->bitArray[$i >> $this->shift] |= (1<<($i & $this->mask)); } //test ビットが 1 かどうかをテストします 関数テストビット($i){ return $this->bitArray[$i >> $this->shift] & (1<<($i & $this->mask)); } } $oBig = 新しい bigMap() ; $oBig->setbit(30) ; var_dump($oBig->testbit(2)) ; var_dump($oBig->bitArray) ;
|