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

  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と関連する良く見られている質問

QPostgresの高速検索

Postgresを扱って1ヶ月のものです。
WEB上で、管理者IDにより自分の持っているユーザーデータを登録してもらう
システムを作っています。推定登録数は、ユーザーデータ10万件ぐらいで、
管理者100~1000人ぐらいを予定しています。
管理者IDにINDEXをはったのですが1万件ぐらいで遅くなります。
データを高速検索するには他に何が必要でしょうか?
また、システムのスペックはメモリ1GB/CPU1GBぐらいで大丈夫
でしょうか?
FreeBSD APACHE PHP Postgres で作っています。どれも最新バージョンです。

ユーザーのカラム数は28。INDEXキーはvarcahrです。
宜しくお願いします。

Aベストアンサー

ども。
私が分かる方法ですと、次のことではないかと思います。

検索の方式または、データベースの作成形式が高速に検索できるように、
作成されていない為ではないですか。

例えば、索引を作ってないとか・・・。

参考URLの
 Q索引ファイルって何のために必要なんですか。
をご参照ください。

スペックは問題ないはずですので、再考してみたらいかがですか?

参考URL:http://kangaroo.cc.tsukuba.ac.jp/jikken/question2000.html

Qピックアップシステムのアルゴリズム

Perlで日替わりのピックアップシステムを作っています。

60件(掲載期限が2週間)程度のデータベースの中から、ランダムに
3件のデータ(重複しない)を表示するピックアップシステムを作っ
ています。

なるべく同頻度でデータを表示させたいのですが、randを使うと
同じデータが複数回表示されてしまったりします。

これを防ぐにはどのようなプログラムを組めばいいでしょうか。

Aベストアンサー

データの数が60件しかないため、randをしても偏ってしまうのだと思います。
最近のPerlはsrandは関係ないはずなので、根本的な問題はサンプルの数が少ないことだと思います。

そこでですが、データベースに表示回数のフィールドを用意して、何回ピックしたか保存してみてはどうでしょう。
この値が低いデータを優先的に選択するようにします。

まずは最小値の取得

表示回数が最小値の行数を取得

行数が2以下 YES→ 最小値の行をすべてピック、表示回数が最小値+1の行数を取得 ↓
NO

その行数を最大値としてrandでランダムに行を選択してピック、表示回数を+1し、randの最大値の行数を-1する。 以降3つピックされるまで繰り返す。

これによって、20日で確実に同頻度でデータをピック出来ると思います。

Qアルゴリズムの参考書

情報関係は初心者なんですが、
アルゴリズム関連の参考書(Que,Stack等用いた)をさがしています。

できれば文系向きの、初心者レベルにも理解できる良書がいいです。

どなたか御存じの方、よろしければ御推薦お願いします。

Aベストアンサー

こんにちわ。
私も大して知識が無いのですが、参加させてください。
アルゴリズムと言うと、幅が広過ぎてこれと言う文献を紹介するのは
ちょっと難しいですが、そもそもアルゴリズムって何?とか、
どんな種類があるの?とかその辺から整理することをお勧めします。
私が手っ取り早く勉強した方法は、情報処理2種の資格用の参考書
(特に午前中)を読破しただけです。
情報処理2種の資格は、情報処理全般にわたる一般常識的な知識と
正しい理解を得る為にかなり有効だと思います。
資格をとる、とらないに関わらず、これに関する教本を1冊だけでも
読破するといろいろな知識が備わるので、電車の中ででも読んでみることを
お勧めします。

私は、新星出版社の【第2種 情報処理[午前] 完全合格教本】で
勉強し、資格をとった後もこの本を時々ぺらぺらとめくっています。
(用語辞書代わりとして。)

ちなみに、キューとスタックについて。
 スタックの定義・・・後入れ先出しリスト
           最後に格納されたデータが最初に取り出されるリスト
           (入り口が1つしかない箱に新聞紙をどんどん入れた
           場合、1つづつ取り出すには、最後に入れたものから
           取り出さなくてはならないような仕組み)
 キューの定義 ・・・先入れ先出しリスト
           最初に格納されたデータが最初に取り出されるリスト
           (バスの待ち行列で先に並んだ人から順にバスに
           乗れるような仕組み)
 
 です。参考にならなかったらごめんなさい。

こんにちわ。
私も大して知識が無いのですが、参加させてください。
アルゴリズムと言うと、幅が広過ぎてこれと言う文献を紹介するのは
ちょっと難しいですが、そもそもアルゴリズムって何?とか、
どんな種類があるの?とかその辺から整理することをお勧めします。
私が手っ取り早く勉強した方法は、情報処理2種の資格用の参考書
(特に午前中)を読破しただけです。
情報処理2種の資格は、情報処理全般にわたる一般常識的な知識と
正しい理解を得る為にかなり有効だと思います。
資格をとる、とらな...続きを読む

Qアルゴリズム

アルゴリズムの勉強をしていて、時間計算量に関する問題があり、解いたのですが、解答が載ってなく困ってます。正誤の判断と、もし間違っているなら、何が間違っているのかを教えて頂けると助かります。

ある問題において、大きさ(データ量)nに対して、アルゴリズムA、B、Cの時間計算量が、それぞれn、n^2(nの2乗)、2^n(2のn乗)であるとする。
(1)アルゴリズムAを用いて10秒間にn=100の問題が解けた。20秒かけるとき扱える問題の大きさnの値を求めよ。
解)
n=100*2
=200

(2)ある計算機を用いてアルゴリズムBで10秒間にn=100の問題が解けた。100倍早い計算機を用いたとき、10秒間に扱える問題の大きさを求めよ。
解)
求める問題の大きさをxとおくと
n=(100^2)*100
=10000*100
=1000000

(3)アルゴリズムCを用いて1時間にn=20の問題が解けた。n=40の問題を解くのに何時間かかるか。
解)
2^40=(2^20)*(2^20)
=1*(2^20)
=2^20[時間]

アルゴリズムの勉強をしていて、時間計算量に関する問題があり、解いたのですが、解答が載ってなく困ってます。正誤の判断と、もし間違っているなら、何が間違っているのかを教えて頂けると助かります。

ある問題において、大きさ(データ量)nに対して、アルゴリズムA、B、Cの時間計算量が、それぞれn、n^2(nの2乗)、2^n(2のn乗)であるとする。
(1)アルゴリズムAを用いて10秒間にn=100の問題が解けた。20秒かけるとき扱える問題の大きさnの値を求めよ。
解)
n=100*2
=200

(2)ある計算機を用いてアルゴリ...続きを読む

Aベストアンサー

(1) (3)は正しいと思います。

(2) は
計算量が n^2 なので
100倍速い処理能力の計算機では、nは10倍にしかなりません。
n=100*√100 となります。
100倍速い計算機を使うと言うことは、
同じ計算機で100倍時間を掛けるのと同じです。
100倍時間をかけたら、10000倍の仕事ができた!
こんなすばらしいことは、計算機ではありません。

Q組み合わせ問題のアルゴリズム

あらかじめ用意された整数を足して、その合計がある指定された整数と等しくなる組み合わせの数を調べるプログラムを書こうとしているのですが、苦労しています。

具体例がないと伝わりにくいかもしれないので例をあげると、
例えばあらかじめ用意された整数というのが
1・1・2・2・5・8 の4つで、
指定された整数が10である場合は、
8と2
8と1と1
5と2と2と1
という3通りの組み合わせがあるので、3を出力したいというわけです。

今まではもっと単純なアルゴリズムしか考えてこなかったので、こういった組み合わせのような問題が難しく感じられます。
こういう場合、アルゴリズムはどのようなものが考えられるでしょうか。
よろしくお願いします。

Aベストアンサー

何か上手い手を考え付かないんだったら、バックトラック法でしょうね。完全な総当りよりは、かなり計算量を減らせるはずです。
バックトラックは再帰で実装すると簡単です。(メモリ食うけど)


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

おすすめ情報