人に聞けない痔の悩み、これでスッキリ >>

これまでの流れ
http://oshiete1.goo.ne.jp/qa3828256.html
http://oshiete1.goo.ne.jp/qa3829067.html

そして結局ランダムアクセスでやろうとゆうことになって問題が・・。

aaa
bcde
ddj
jk

これに cd を追加したいときランダムアクセスでは ddj と jk を
再配置しなければならない。(理由はゆうまでもなく2分検索を使うため)
これでは項目が増えると処理が重くなるのですがどうしたらいいですか?

このQ&Aに関連する最新のQ&A

A 回答 (2件)

こんにちは



先に解答を言いますと、
Q:これでは項目が増えると処理が重くなるのですがどうしたらいいですか?
A:宿命ですのであきらめてください。

速い、遅いは環境によって様々に言われるので一概に言えるものではありませんが、注意したいのは一般にデータベースソフトは直接ファイルアクセスした場合よりも遅いと言うことです。
また、キャッシュ付きの探索を行う場合、要素数が少なければ(~1万行ぐらいでしょうか)ランダムアクセスするよりもシーケンシャルにアクセスする方が速いのではないかと私は見積もります。
ですから、想定される要素数にもよりますが、まずはバカサーチするように実装して、プロファイリング時にボトルネックとなるようであればデータベースライブラリの導入を検討すればよいのではないでしょうか。

データベースの勉強をしていらっしゃって、実装を考えておられるのでしたら、ファイルベースのデータベースライブラリではBerkeleyDBやSQLiteのソースが公開されています。
    • good
    • 0

速く検索できる方法を考えるとき


   1. 検索対象をすでにソートされているものに限定するか。
   2. データの管理(追加・修正・削除)を含んだ検索をする。
の2通りがあります。

2.の場合、
どの程度頻繁にデータの更新が行われるのか、
その更新のために、データを実際にソートしなおすの、
インデックスを作成してそれを利用するのか、そのの更新をどのように効率的に管理するのか、
といった問題を処理していくことになると思います。

これらのデータの管理を行うのが、まさにデータベースアプリケーションの役割で、
1.に限定せずに2.のことを行なおうとするとこういった問題が発生してくると思います。

この回答への補足

問題が発生してるから聞いてるのです。
Bツリーを使おうとして
http://itpro.nikkeibp.co.jp/article/COLUMN/20060 …
を見ながら、
この方法だと
a~z,A~Zで52文字(8*52=416bytes)、0~9で10文字(8*10=80bytes)、
次のノードへのポインタがlong型で62文字分(62*8=496bytes)
合計で992bytes

つまりこの方法でやろうとするとmoonとゆう単語をデータとして入力すると
m に992bytes, o に992bytes, o に992bytes, n に992bytes
約4Kbytes
2回目以降はappleを登録すると
a に0bytes, pple に4Kbytes
つまりあとに追加すればするほど容量を食わなくてすむのですが
この例のように単語2個で8Kbytesも使うとあとあと苦しいかと。
特にpneumonoultramicroscopicsilicovolcanoconiosisのような
長い単語をいれるとすぐにウンMBくらいいきそうです。

それと分からないのがリンク先にある
>一般的なページ・サイズとレコード数では,Bツリーの階層はせいぜい3~4階層にしかならないと考えていいでしょう。
のところ。普通に考えれば最初の説明のように入力単語そのものの
長さになる。

補足日時:2008/03/26 15:00
    • good
    • 0
この回答へのお礼

char型1bytesなので正しくは
a~z,A~Zで52文字(52bytes)、0~9で10文字(10bytes)、
62bytes
long型のポインタとあわせても558bytes
それでも大きくなるような気がするのですがどうしたらいいですか?

お礼日時:2008/03/26 16:00

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング