No.1
- 回答日時:
データの内容によって色々変わってくると思うのですが・・・
キーの重複の有無、
キーのデータとの完全一致か、一部との一致か
などありますので、もう少し具体的な補足をお願いします
この回答への補足
ありがとうございます。
そういう条件もあるのですね。
データは基本的に、「ありとあらゆるデータ」が来る可能性があります。テキスト形式で記述されたCSVファイルの中身を検索するためのものだからです。
よって、キーが重複することもありえます。また、1回の検索で複数のデータが取得できてしまうこともありえます。
完全一致とかそういうのは、正規表現でなんとでも対処できるので、部分一致は考えなくていい、というところです。
よろしくお願いします。
No.2
- 回答日時:
1回しか探索しないのだとすると、木を作る間に探せてしまうでしょ
うから、何度も探索するのを木で高速化したいということでよろし
いでしょうか?
そういう目的なら2分探索木かB木ということになると思います。前
者はバランスが悪い木になってしまうと、リニアサーチと変わらな
くなります。順序がバラバラといっても、もし部分的にソートされ
てたりする可能性があるなら、後者を使うべきでしょうね。
どちらも、
「C言語による最新アルゴリズム事典」奥村晴彦・技術評論社
で解説されています。
この回答への補足
ありがとうございます。
検索回数に関しては……。
まず俺が作っているのは、他のプログラムから呼び出されるモジュールです。
アプリケーションからの要求に応じてCSVファイルの中身を読み込み、サーチします。よって、1回しか検索しないかどうかについては何とも言えないのです(^_^;
ちなみに、データそのものもアプリケーションが用意した物を使うので、部分的にソートされている可能性があるとも言えるし、ないとも言えます。
どっちにしろご指定の本は便利そうですね。
本屋で探してみようと思います。
No.3
- 回答日時:
順次検索や大小比較が必要無いならハッシュで行けますね。
ハッシュ表を使わずにデータをほおりこめばインデックスもツリーも不要です(容量的には不利ですが)。
検索の“直前”であろうと“事前”であろうと「ツリーやインデックスを作る」のならB木で良いような気もしますが…。
この回答への補足
ありがとうございます。
「ハッシュ表を使わずにデータを放り込む」とはどういうロジックなんでしょう? データそのものをハッシュ値として使うのでしょうか。
それから、ツリー(インデックス)を直前に作るのは、検索条件が複数であるためです。
B木検索ではいけない理由は、それを作るためにソートを行うと、条件1、条件2……条件nというように条件の個数分だけソートを行わなければならないことになり、結果として処理速度が落ちるのです(^_^;
なぜそういうことをするのかというと、1つのデータは複数の項目を持っており、条件1では項目Aをキーとして検索を行い、条件2では項目Bをキーとして検索を行う、ということをやるからなわけです。
データの内容もこちらが予測したものってわけにもいかないので、データの種類に前提を作ることもできませんし……。
No.4
- 回答日時:
#3を書いた後で#1への補足を読んだのですが、線形文字列検索ではダメですか?
CSVファイル内の任意の文字列を高速検索するならBM法で何とかなるかでしょう。
アルゴリズム辞典で確認してください。
ありがとうございます。
駄目ってことはないんですが、言語が Perl なので、できれば高速化したいんです。あと、文字列検索ではなく、厳密にはデータ抽出ですね(^_^;
今のところ、処理能力が秒間600件(セルロン300)ですが、これだとちょっと弱いので……。
でも、各アルゴリズムの処理速度を見ていると、何だか線形検索が最速のような気がしてきました(笑)
線形検索なら速度が最善だろうが最悪だろうが O(n) にできますし。
とりあえず、条件文の解析の高速化とか、そういう方面でやってみます(^_^;
No.5
- 回答日時:
条件としては一般にどんなものが与えられるんでしょう?
項目A =~ /regexp/ && !(項目B =~ /regexp/ && 項目C =~ /regexp/)
ぐらい一般的なんでしょうか?
あと、検索の回数に関してですが、アプリケーションから1回呼ば
れるごとに1回検索するだけなんですね?
で、2回目の検索というのがあったとしたとき、CSVのデータに変更
がある可能性もあって、そのことを知るすべがないのでしょうか?
そうだとすると、前から順に探すくらいしか思いつきません。
ありがとうございます。
条件文はだいたいおっしゃるとおりです。
入力されたSQL文に対して条件にマッチするデータを抽出します。
で、検索回数は、1回の呼び出しに対して1回のみです。1回目の呼び出しでインデックスを作って2回目からはそれを使うという手もアリですが、そのインデックスは「ありとあらゆる条件」において流用できなければ実用できません(^_^;
……こんなところです。
はっきりいって、現状を保つ(線形検索する)か袋小路で迷うかといったような瀬戸際ですね(笑)
今のところ前者に心が動いておりますけれども(笑)
No.6
- 回答日時:
なんかDatabaseのようなものを作ろうとしてらっしゃるみたいですね・・・
であれば一番手っ取り早いのはDatabaseに突っ込んでSQLでQueryするってのが一番早いですが(笑)
結局自分で実装するにしてもDBと同じ手法を使う事になるでしょう
データを一意に識別出来るindexを付けてやり
それぞれの項目毎にB木やバランスツリー、ハッシュなどで一意識別できるindexとキーを関連付けてやります
それで検索条件毎にそれぞれの項目毎のツリーなどからindexを限定してやって、最後にindexから実体を出力してやる、という方法が使えると思います
また、検索条件の最適化を行うと言う事も(条件によっては)出来るでしょう
・・・以上の事は実際のdatabaseがやってる事です(^^;
MS SQL Serverなどの内部動作解説本などがあるのでそういう物を読むか、OpenSourceなDatabaseのSourceCodeを調べるのもいいかもしれません
そぉです(^_^; Perl からSQLが呼べないかなぁと思って、今作ってるんです(笑)(←PasageSQLやMySQLだと一般プロバイダのCGI環境では使えないから、といったようなコンセプト)
つっても、ver.1 はすでにヴェクターに登録申請しましたけど。
MS SQL Server の解説書はめちゃくちゃ欲しいです(笑) 本屋にありますか?
オープンソースのデータベースソフトがあるのなら、それもご紹介いただきたいんですが……(^_^;
No.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 …
ありがとうございます。
まあ、「手軽に使える」ことを売りにしてますからね。少なくともそれだけは誰にも負けないはずです(笑)
解説書は、財布と相談したうえで、ヒモが緩んでくれれば買いたいと思います(笑)
URLの方はさっそくソースを落としに行きたいと思います。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
Web初心者です。 簡易的なWebペ...
-
pythonでAmazonのほしいものリ...
-
Google ColaboでGUI作成
-
AIの登場でプログラマーたちが...
-
プログラマーと学歴の関係性に...
-
プログラマーは誘惑にさらされ...
-
python エラー
-
プログラミング言語について
-
Processingについて
-
プログラマーに向いている人の...
-
16x16のスプライトフォント
-
vba クリップボードクリアにつ...
-
python の 連鎖代入の文法
-
Pythonでの文字列からfloatへの...
-
・オブジェクト指向のメリット...
-
プログラミングの雑談がしたい...
-
最新のプログラム言語を学ぶに...
-
フォルダを自動作成・移動を複...
-
このURLで広告を出しているのは...
-
Google Colabでimport soxが出...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
麻雀ソフトのソースコード
-
アルゴリズムC
-
課題研究で3Dゲーム製作
-
SEOの本, 一冊読むなら?
-
文字列探索アルゴリズム(Aho Co...
-
将棋AIを作りたい
-
C言語を学ぶには・・・
-
下記のアルゴリズムの問題がよ...
-
プログラミングVBAについてです...
-
【C言語】行列のランク(階数)...
-
大学生です。 画像のC言語の課...
-
アルゴリズムとデータ構造の本...
-
東芝新製品に採用されている
-
VC++でジャンケンゲームを学びたい
-
delphi:文章の暗号化
-
Rijndael2
-
C言語の上級者を目指したい。
-
Excelで乱数発生のアルゴリズム
-
Windows Media Playerを開くと...
-
Google ColaboでGUI作成
おすすめ情報