巨大ビット配列

 BASICでは0または1の値のみをとる変数にも普通の変数を割り当てます。 これは,大きな配列を使いたい場合には非効率です。
 BitArray.zipをダウンロードし,展開して得られるBitArray.DLLを利用すると,次の例のようにして巨大ビット配列が使えます。
(BitArray.DLLをBASIC.EXEがあるフォルダに置くか,または,プログラムとBitArray.DLLを同じフォルダに保存して実行してください)

REM エラトステネスの篩 
DECLARE EXTERNAL FUNCTION GetArray, Test
DECLARE EXTERNAL SUB FreeArray, setbit
LET Nmax=10000
LET p=GetArray(Nmax)
IF p<>0 THEN 
   FOR i=2 TO Nmax-1
      IF Test(p,i)=0 THEN
         PRINT i
         FOR  j=i^2 TO Nmax-1 STEP i
            CALL SetBit(p,j)
         NEXT j 
      END IF
   NEXT i
   CALL FreeArray(p)
END IF
END
 
EXTERNAL FUNCTION GetArray(s)
! (s+1)ビットのメモリを確保し,ゼロで埋める。
! 結果は,メモリのアドレス。0のときは失敗。
FUNCTION GetArray_sub(s)
   ASSIGN "BitArray.DLL","GetArray"
END FUNCTION
IF 0<=s AND s<2^32 THEN
   LET GetArray=getArray_sub(s)
ELSE 
   LET GetArray=0
END if
END FUNCTION
 
EXTERNAL SUB FreeArray(p)
! メモリを返却する。pはGetArrayで得た値
ASSIGN "BitArray.DLL","FreeArray"
END SUB 
 
EXTERNAL FUNCTION Test(p,i)
! i番目のビットを取得する。pはGetArrayで得た値
ASSIGN "BitArray.DLL", "Test"
END FUNCTION

EXTERNAL SUB SetBit(p,i)
! i番目のビットを1にする。pはGetArrayで得た値
ASSIGN "BitArray.DLL", "SetBit"
END SUB
 
EXTERNAL SUB ResetBit(p,i)
! i番目のビットを0にする。pはGetArrayで得た値
ASSIGN "BitArray.DLL", "ResetBit"
END SUB

Test,SetBit,ResetBitで指定できるiの値は,GetArrayに指定した数をsとして,0〜sです。
また,実際にGetArrayに指定できるsの値の上限は,Windows XPでの実験結果では,1983381248です。

<注意>Test,SetBit,resetBitは範囲外の数を指定したときの安全策を講じていません。範囲外を指定しないように注意してプログラムを作る必要があります。


戻る inserted by FC2 system