最新閲覧日:

 今、高速な検索アルゴリズムを探しています。
 下記の条件のときに使えるアルゴリズムが何かないか、ご存知の方おしえてください。

  1.データの順番は基本的にバラバラ
  2.トゥリーやインデックスは検索の直前に作る

 よろしくお願いします。

このQ&Aに関連する人気のQ&A

A 回答 (7件)

>Perl からSQLが呼べないかなぁと


>PasageSQLやMySQLだと一般プロバイダのCGI環境では使えないから

SQL自体はそれぞれのモジュールがあると思います
(少なくともPostgresはPg.pmがあります)
一般プロバイダでは使えませんが、海外などのFreeWebサービスではMySQLやPostgresを遣わせてくれる所もありますよ
また、DataBaseは通常Networkアクセスできるように作ってあるので設定まで出来る所であれば、webサーバ(Perlプログラムが動いてる所ですね)とDBサーバは別々に出来ます
またODBCドライバモジュールがあれば大体のDetabaseは使えるはずです(多分探せばODBC用perl moduleがあると思います・・・自信無いですが(^^;)

SQL Serverの内部解説書ですが、私が読んだのは
出版社: リックテレコム
書名: リファレンス WindowsNTによるSQL Server6.5チューニングガイド
著者: 飛鳥 亮
定価: 2800円(税別)
ISBN: 4-89797-211-6
です
ちょっと古い本ですが、まだ手に入るようです>参考URLを参照してください

>オープンソースのデータベースソフトがあるのなら、それもご紹介いただきたいんですが……(^_^;
オープンソースのデータベースソフトはPostgreSQLやMySQLがそうですよ(^^;
PostgreSQLは
http://www.sra.co.jp/people/t-ishii/PostgreSQL/
からダウンロードできるはずです

MySQLはこちら
http://www.softagency.co.jp/mysql/

参考URL:http://www.amazon.co.jp/exec/obidos/ASIN/4897972 …
    • good
    • 0
この回答へのお礼

 ありがとうございます。

 まあ、「手軽に使える」ことを売りにしてますからね。少なくともそれだけは誰にも負けないはずです(笑)

 解説書は、財布と相談したうえで、ヒモが緩んでくれれば買いたいと思います(笑)
 URLの方はさっそくソースを落としに行きたいと思います。

お礼日時:2001/03/02 23:39

なんかDatabaseのようなものを作ろうとしてらっしゃるみたいですね・・・


であれば一番手っ取り早いのはDatabaseに突っ込んでSQLでQueryするってのが一番早いですが(笑)

結局自分で実装するにしてもDBと同じ手法を使う事になるでしょう
データを一意に識別出来るindexを付けてやり
それぞれの項目毎にB木やバランスツリー、ハッシュなどで一意識別できるindexとキーを関連付けてやります
それで検索条件毎にそれぞれの項目毎のツリーなどからindexを限定してやって、最後にindexから実体を出力してやる、という方法が使えると思います

また、検索条件の最適化を行うと言う事も(条件によっては)出来るでしょう

・・・以上の事は実際のdatabaseがやってる事です(^^;
MS SQL Serverなどの内部動作解説本などがあるのでそういう物を読むか、OpenSourceなDatabaseのSourceCodeを調べるのもいいかもしれません
    • good
    • 0
この回答へのお礼

 そぉです(^_^; Perl からSQLが呼べないかなぁと思って、今作ってるんです(笑)(←PasageSQLやMySQLだと一般プロバイダのCGI環境では使えないから、といったようなコンセプト)
 つっても、ver.1 はすでにヴェクターに登録申請しましたけど。

 MS SQL Server の解説書はめちゃくちゃ欲しいです(笑) 本屋にありますか?
 オープンソースのデータベースソフトがあるのなら、それもご紹介いただきたいんですが……(^_^;

お礼日時:2001/03/02 18:07

条件としては一般にどんなものが与えられるんでしょう?


項目A =~ /regexp/ && !(項目B =~ /regexp/ && 項目C =~ /regexp/)
ぐらい一般的なんでしょうか?

あと、検索の回数に関してですが、アプリケーションから1回呼ば
れるごとに1回検索するだけなんですね?

で、2回目の検索というのがあったとしたとき、CSVのデータに変更
がある可能性もあって、そのことを知るすべがないのでしょうか?

そうだとすると、前から順に探すくらいしか思いつきません。
    • good
    • 0
この回答へのお礼

 ありがとうございます。

 条件文はだいたいおっしゃるとおりです。
 入力されたSQL文に対して条件にマッチするデータを抽出します。
 で、検索回数は、1回の呼び出しに対して1回のみです。1回目の呼び出しでインデックスを作って2回目からはそれを使うという手もアリですが、そのインデックスは「ありとあらゆる条件」において流用できなければ実用できません(^_^;
 ……こんなところです。

 はっきりいって、現状を保つ(線形検索する)か袋小路で迷うかといったような瀬戸際ですね(笑)
 今のところ前者に心が動いておりますけれども(笑)

お礼日時:2001/03/02 17:59

#3を書いた後で#1への補足を読んだのですが、線形文字列検索ではダメですか?



CSVファイル内の任意の文字列を高速検索するならBM法で何とかなるかでしょう。
アルゴリズム辞典で確認してください。
    • good
    • 0
この回答へのお礼

 ありがとうございます。

 駄目ってことはないんですが、言語が Perl なので、できれば高速化したいんです。あと、文字列検索ではなく、厳密にはデータ抽出ですね(^_^;
 今のところ、処理能力が秒間600件(セルロン300)ですが、これだとちょっと弱いので……。

 でも、各アルゴリズムの処理速度を見ていると、何だか線形検索が最速のような気がしてきました(笑)
 線形検索なら速度が最善だろうが最悪だろうが O(n) にできますし。
 とりあえず、条件文の解析の高速化とか、そういう方面でやってみます(^_^;

お礼日時:2001/03/02 17:55

順次検索や大小比較が必要無いならハッシュで行けますね。


ハッシュ表を使わずにデータをほおりこめばインデックスもツリーも不要です(容量的には不利ですが)。

検索の“直前”であろうと“事前”であろうと「ツリーやインデックスを作る」のならB木で良いような気もしますが…。

この回答への補足

 ありがとうございます。

 「ハッシュ表を使わずにデータを放り込む」とはどういうロジックなんでしょう? データそのものをハッシュ値として使うのでしょうか。

 それから、ツリー(インデックス)を直前に作るのは、検索条件が複数であるためです。
 B木検索ではいけない理由は、それを作るためにソートを行うと、条件1、条件2……条件nというように条件の個数分だけソートを行わなければならないことになり、結果として処理速度が落ちるのです(^_^;
 なぜそういうことをするのかというと、1つのデータは複数の項目を持っており、条件1では項目Aをキーとして検索を行い、条件2では項目Bをキーとして検索を行う、ということをやるからなわけです。

 データの内容もこちらが予測したものってわけにもいかないので、データの種類に前提を作ることもできませんし……。

補足日時:2001/03/02 16:40
    • good
    • 0

1回しか探索しないのだとすると、木を作る間に探せてしまうでしょ


うから、何度も探索するのを木で高速化したいということでよろし
いでしょうか?

そういう目的なら2分探索木かB木ということになると思います。前
者はバランスが悪い木になってしまうと、リニアサーチと変わらな
くなります。順序がバラバラといっても、もし部分的にソートされ
てたりする可能性があるなら、後者を使うべきでしょうね。

どちらも、
「C言語による最新アルゴリズム事典」奥村晴彦・技術評論社
で解説されています。

この回答への補足

 ありがとうございます。

 検索回数に関しては……。
 まず俺が作っているのは、他のプログラムから呼び出されるモジュールです。
 アプリケーションからの要求に応じてCSVファイルの中身を読み込み、サーチします。よって、1回しか検索しないかどうかについては何とも言えないのです(^_^;

 ちなみに、データそのものもアプリケーションが用意した物を使うので、部分的にソートされている可能性があるとも言えるし、ないとも言えます。

 どっちにしろご指定の本は便利そうですね。
 本屋で探してみようと思います。

補足日時:2001/03/02 16:27
    • good
    • 0

データの内容によって色々変わってくると思うのですが・・・


キーの重複の有無、
キーのデータとの完全一致か、一部との一致か
などありますので、もう少し具体的な補足をお願いします

この回答への補足

 ありがとうございます。

 そういう条件もあるのですね。
 データは基本的に、「ありとあらゆるデータ」が来る可能性があります。テキスト形式で記述されたCSVファイルの中身を検索するためのものだからです。
 よって、キーが重複することもありえます。また、1回の検索で複数のデータが取得できてしまうこともありえます。
 完全一致とかそういうのは、正規表現でなんとでも対処できるので、部分一致は考えなくていい、というところです。

 よろしくお願いします。

補足日時:2001/03/02 16:19
    • good
    • 0

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

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

このQ&Aを見た人が検索しているワード


このカテゴリの人気Q&Aランキング

おすすめ情報

カテゴリ