SAK 図書館
SAK 図書館
VB テクニック編30 - 索引ファイル、インデックスファイル、テーブルサーチ
■SAK 関数利用規程
・テクニック編で紹介する関数は、私こと Y.SAK の開発関数である。
・著作権明示部分の改編は認めない。
・個人、企業がこれらの関数を使用したり、一部を使用して新たなシステムや
プログラムを開発することは自由です。
・但し、これらの関数を一部でも使用しているソフトウェアをシェアウェア、
その他有償プロダクトとして配布・販売するには、私の許可が必要です。
(無償のフリーソフトウェアなら、自由に配布しても良い。)
・これらの関数を使用して発生した、いかなる形での損害も私こと Y.SAK は
賠償しません。
■索引ファイルによるシーケンシャルアクセス(インデックスファイル)
・次のコードは、約 3.5MB の 10 万件のテストデータを作成する。
この例では、データの先頭がユニークキーになっている。
また、データは昇順に並んでいる。
dim i as long
open "data.csv" for output as #1 len = 32000
for i = 1 to 100000
print #1, chr(&h22) & format(i, "000000") & chr(&h22) & ",";
print #1, chr(&h22) & int(rnd(1) * 10000) + 100000 & chr(&h22) & ",";
print #1, chr(&h22) & int(rnd(1) * 10000) + 200000 & chr(&h22) & ",";
print #1, chr(&h22) & int(rnd(1) * 10000) + 300000 & chr(&h22)
next
close #1
-- 作成内容
"000001","107055","205334","305795"
"000002","102895","203019","307747"
"000003","100140","207607","308144"
...
"100000","104969","206731","308063"
・次のコードは、作成した 10 万件 data.csv のインデックスファイルを作成
する。索引は「キー」と「シークアドレス」の単純なものである。
この例では、100 件単位に索引データを作成している。
また、引用句を省略している。
この索引は、索引件数をファイルの先頭に持たせることにしてある。
(最後に binary モードで先頭に件数をセットしている。)
こうすれば、サーチ用の配列を無駄なく作成できる。
尚、元のデータがキーがユニークで昇順のため、シンプルに索引が作成でき
るが、重複レコードや並びが昇順、降順のように一定していなと、もう少し
工夫が必要である。(キーテーブルのソートや親子関係など。)
dim i as long
dim k1 as string
dim d1 as string
dim ct as long
dim rec as string
open "data.csv" for input as #1 len = 32000
open "index.dat" for output as #2 len = 32000
print #2, "0000000000"
i = -1
ct = -1
do until eof(1)
input #1, k1, d1, d1, d1
i = i + 1
if i mod 100 = 0 then
print #2, k1 & "," & seek(1)
ct = ct + 1
end if
loop
close #2
close #1
open "index.dat" for binary as #2 len = 10
rec = format(ct, "0000000000")
put #2, , rec
close #2
-- 作成内容
0000000999
000001,38
000101,3738
000201,7438
...
099901,3696338
・例えば、索引ファイルを使用せずに "099999" のデータを読むとすると、
ほぼ、10 万件すべてを読み飛ばさなければならない。
また、レコードが昇順や降順に並んでいなければ、アンマッチ時に常に全件
リードとなる。
この手の単純検索で大量のレコードを扱う場合は、少なくともデータの並び
は一定していないとうまくない。
dim sch as string
dim k1 as string
dim d1 as string
dim d2 as string
dim d3 as string
dim fnd as boolean
dim shtm as double '** 不要
'** サーチキー指定
sch = "099999"
'** テーブルサーチ
shtm = timer '** 不要
open "data.csv" for input as #1 len = 32000
do until eof(1)
input #1, k1, d1, d2, d3
if k1 = sch then
fnd = true
exit do
end if
if k1 > sch then
fnd = false
exit do
end if
loop
close #1
shtm = timer - shtm '** 不要
'** サーチエラー
if fnd = false then
msgbox "見つからない。"
end
end if
'** サーチ結果
print shtm '** 不要
print k1
print d1
print d2
print d3
-- 結果
0.359 秒 sch = "099999" (うちの PC は、むちゃ高速なので注意!!)
0.000 秒 sch = "000009" (測定不能)
** ファイルの後半のデータほど、どんどん検索が遅くなる理屈である。
・次のコードは、作成したインデックスファイルを利用している。
従って、平均的に 100 倍の論理的速さになる。
この手のデータ要素であれば、SQL データベースより高速と思う。
しかし、データの並びがランダムであったり、親子関係を持つ必要のある時、
データの修正があるときには、非常に複雑な検索や更新ロジックが必要とな
る。昔は、マシンランゲージでその手の関数を自作していたものだが、
今は、SQL が楽で良い。
・本式のコードでは、毎回キーテーブル読み込みを行うようなことはしない。
初期化時に行うこと、関数化するとこ、エラー処理などが必要である。
dim sch as string
dim k1 as string
dim d1 as string
dim d2 as string
dim d3 as string
dim fnd as boolean
dim shtm as double '** 不要
dim rec as string
dim schmax as long
dim i as long
'** キーテーブル読み込み
open "index.dat" for input as #1 len = 32000
line input #1, rec
schmax = rec
redim schkey(schmax) as string
redim schadr(schmax) as string
i = -1
do until eof(1)
i = i + 1
input #1, schkey(i), schadr(i)
loop
close #1
'** サーチキー指定
sch = "099999"
'** キーテーブルサーチ
shtm = timer '** 不要
for i = 0 to schmax
if schkey(i) > sch then exit for
next
i = i - 1
if i < 0 then
msgbox "索引になし"
end
end if
'** テーブルサーチ
open "data.csv" for input as #1 len = 32000
seek #1, schadr(i)
do until eof(1)
input #1, k1, d1, d2, d3
if k1 = sch then
fnd = true
exit do
end if
if k1 > sch then
fnd = false
exit do
end if
loop
close #1
shtm = timer - shtm '** 不要
'** サーチエラー
if fnd = false then
msgbox "見つからない。"
end
end if
'** サーチ結果
print shtm '** 不要
print k1
print d1
print d2
print d3
-- 結果
0.000 秒 sch = "099999" (測定不能)
0.000 秒 sch = "000009" (測定不能)
** ファイルのどこのデータも平均的に高速検索できる。
■ISF インデックスシーケンシャルファイル
・その昔、CSP/F5 の ISF に惚れて、PC 用に自作したことがある。
通常のシーケンシャルアクセスとキーによる昇順、降順のリードが可能で
あった。逆読みは当時 RDM でしか不可能だっため、我ながら良く作ったと
思う。既にマシンコードを捨ててしまっていので細かなコードはないが、
理屈だけ公開しておく。
・キーファイルの持ち方が、多様なアクセスを実現する。
私は、
キー
レコードポインタ
ひとつ前のレコードポインタ
ひとつ後のレコードポインタ
排他プロック
と言う持ち方をした。
シーケンシャルによる逆読みでは、ひとつ前のレコードポインタをたどって
いけば良い。
ランダムアクセスは、いかに目的のキーを少ない手順で見つけるかにある。
先の例のようなキーテーブルをなめるように読み方ではダメである。
具体的には、乱数と親子関係を利用して、目的のレコードを探す。
当時 16bits 5MHz 30000 件でも非常に有効なレスポンスが得られた。
なんだが捨ててしまったのが惜しいと感じるこの頃である。
(なんたって、もう細部のアルゴリズムが思い出せない。) (^^;
・データファイルは、データプロックが可変長である場合、非常にキーファ
イルの更新がやっかいになる。
私は、固定長でデザインしていた。
データプロックが固定長であれば、追加、修正、削除のキーファイルに
対する更新手数が三つで済む。
・現在の PC の CPU パワーとメモリ搭載量を考えると、複雑なロジックより
も単純なもので、十分実用になることも多い。
10 万件なめ読み 0.359 秒の性能には正直驚いた。
昔から、人が待てるのは、2 〜 3 秒とよく聞く。
平均的な PC パワーで、その程度のレスポンスが得られるもっともシンプル
なコードが一番良いのかもしれない。
■VB テクニック編資料
■VB 入門編資料
■VB 基礎編資料
■VB ビジュアル編資料
Copyright (C) 1999-2024 Y.SAK