- ベストアンサー
検索アルゴリズム
punchan_jpの回答
- punchan_jp
- ベストアンサー率55% (155/280)
1回しか探索しないのだとすると、木を作る間に探せてしまうでしょ うから、何度も探索するのを木で高速化したいということでよろし いでしょうか？ そういう目的なら2分探索木かB木ということになると思います。前 者はバランスが悪い木になってしまうと、リニアサーチと変わらな くなります。順序がバラバラといっても、もし部分的にソートされ てたりする可能性があるなら、後者を使うべきでしょうね。 どちらも、 「C言語による最新アルゴリズム事典」奥村晴彦・技術評論社 で解説されています。
関連するQ&A
- 文字列の検索アルゴリズム
「私は世界一頭がいいので、数学なんか簡単すぎていいかげん飽きてきた。」 この文字列から「いいかげん」を検索するアルゴリズムにはどんなものがあるのでしょうか？ 条件 ・100KB（5万字）程度のデータから10文字程度指定文字列を検索する。 ・100KBと元データもそれほど大きくないので、プログラムが簡単なアルゴリズムが良い。 ・そのアルゴリズムの解説がインターネット上にあること。 単純に「い」を探して合致したら次の文字も「い」であることを確認。 さらに次の文字が「か」であることを確認。 さらに・・・「げ」・・「ん」 とやっていく方法でも良いとは思うのですが、もしかしたらもっとお手軽かつ高速にできる方法があるのかなと思い質問してみました。 なければないという回答でもかまいません。 また、参考までにテキストエディタ等がどのようなアルゴリズムを用いているのか知っている方（推測できる方）はその方法についても教えて頂ければと思います。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 高速検索アルゴリズムとデータの追加・削除
現在高速検索のアルゴリズムを考えておりますが、 そこにデータの追加・削除が絡むと、 どのようにデータをまとめればいいのでしょうか？ 例えば ------------ ------------ ------------- |data1|DATA1| |data2|DATA2| |data3|DATA3| ・・・ ------------ ------------ ------------- と要素を２つ持ったデータが複数存在した場合、 dataの昇順リスト ---------------------------- |Index|各データの先頭アドレス| ---------------------------- |・ |・ |・ DATAの昇順リスト ---------------------------- |Index|各データの先頭アドレス| ---------------------------- |・ |・ |・ というそれぞれのリストを持たせれば、 dataで検索したい場合、DATAで検索したい場合、 各リストのIndex値を用いて2分探索すれば高速だと考えました。 しかしデータの追加・削除があればそれぞれのリストを その度にソートし直さなければなりません。 もちろん追加・削除の度にデータ１つ分ずつずらしてやればいいだけですが、 基本的に使わない領域は解放したいですから、データ数の上限値が決まってない以上は 領域も確保されているとは限らないですから安易にデータをずらすことも出来ません。 データのずらしかたもどうでしょう？ リストに加えるor削除する箇所からその時の最大値までをコピーして データ１つ分のサイズをずらして貼り付けるといった動作は、 連続した処理や排他的処理を考えると好ましくないのでしょうか？ もし根本的に高速検索と追加・削除の相性が良い手法があればご教授願います。
- ベストアンサー
- C・C++・C#
- 学習のアルゴリズム
次のようなケースで、学習させるうまいアルゴリズムをご存知の方はいっらしゃらないでしょうか？ (1)基本のパターンは数万個あります。各パターンには番号が振ってあります。 (2)数百個のパターンの集合と、その中で「最も良い」パターンの番号のデータが数百万個あります。ただし、この「最も良い」の評価は人間の感性のような、結構いいかげんな物だと考えてください。 (3)このようなデータを学習させ、各パターンになんらかの方法で点数を与える。 このようにして出来た学習データを使い、(2)と同じデータを再度与え、「最も良い」パターンが最も点数の高いパターンに一致する確立をなるべく高くしたい。 (2)と同じデータではないが、同様のデータを与え、最も点数の高いパターンが、「同じ感性」で「最も良い」とされる確率ができるだけ高くなるようにしたい： このような学習を行うアルゴリズムについて、なにか良い論文、本などをご存知でしたら御教えください。
- 締切済み
- 数学・算数
- アルゴリズムのご相談2
度々すいません。 また考え方の課題なんですけど、 各配列のDataの中に順不同なバラバラなデータが入っているときに、 その中から最も0に近いIndexでDataが空白になっている箇所を探すには、 どういった検索方法が高速なのでしょうか？ この場合、頭から探すしかないのでしょうか？ ---------------- | Index | Data ---------------- | 0 | 123 ---------------- | 1 | abc ---------------- | 2 | xyz ---------------- | 3 | ← ---------------- | 4 | 456 ---------------- | 5 | ---------------- | 6 | ABC ---------------- | 7 | XYZ ---------------- | 8 | 789 ---------------- | 9 | ijk ---------------- | … | …
- ベストアンサー
- C・C++・C#
- アルゴリズムでわからない問題があります。（C言語）
問題１：探索アルゴリズムであるハッシュ法について正しいものを選べ。 (1)ハッシュ関数の出力によりデータを格納した配列の先頭から順番に調べる． (2) 入力データを，ハッシュ関数の出力により求めた格納場所に基づいて，あらかじめ木構造に格納しておく． (4) 入力データを格納した配列を繰り返し２つに分割し，それぞれを順番に調べていく． (3) 入力データから格納場所の位置に変換する関数（ハッシュ関数）の出力により，データの探索場所を決定する。 (5) 入力データを，ハッシュ関数の出力により求めた格納場所に基づいて，あらかじめヒープに格納しておく 問題２：探索アルゴリズムであるハッシュ法について正しくないものを選べ。 (1)入力データはハッシュ値で決められる場所に格納される． (2) ハッシュ関数には，異なる入力の値に対し異なる値を出力することが求められる． (3) ハッシュ関数の時間計算量は，入力データのサイズに比例する． (4) データの格納場所が大きい方が効率がよい． (5) 一般に２分探索法より高速に動作する． どなたかアルゴリズムに詳しい方回答お願いします
- 締切済み
- C・C++・C#
- なぜRDBの検索は遅い？
個人的な印象ですが、RDBベースの検索システム、データ抽出システムはグーグルやヤフーの検索サービスに比べて異様に遅い気がします。 検索条件(検索語句)や検索対象はグーグル、ヤフーの方が遥かに複雑で広大なように見えるのに、なぜこのような差があるのでしょうか？(グーグルがrobotで予めデータ集めてるとか、キャッシュサーバがあるとかこうりしても差が開きすぎな気がします) アルゴリズムレベルでRDBの方が検索に向いていない感じがするのですが、ご存知の方、教えてくださいますようお願いします。
- ベストアンサー
- その他(データベース)
- インデックスのアルゴリズムとBツリー
主キーじゃないカラムにインデックスを張るとき、 つまり、値が重複することがありうる場合に 利用されるBツリーは通常のBツリーと比較して、 どのように変更すればよいものでしょうか。 また、WHERE句内で * などを使用して検索するとき、 どのようにBツリー内を検索すれば効率的でしょうか。 データベースの実装に関する質問になりますが、 わかる方、よろしくお願いします。
- ベストアンサー
- その他(データベース)
- データを抽出して更新するアルゴリズムについて
基本情報の勉強をすこしかじっているのですが、ソートや検索といったものの基本的なアルゴリズムはならったのですが、いまいち応用が出来ません。例えば、エクセルなどで、値の書き換えの必要となるあるデータの集まりを抽出し、一度必要な更新(データの置換)を行ったものはもう更新の対象としない、あるいは、元のデータの群れに戻すというような場合、どのような処理手順を書くのが理想的でしょうか?
- ベストアンサー
- その他（プログラミング・開発）
- 大滝みや子先生の「アルゴリズム解法」で
大滝みや子先生の 基本情報技術者 「かんたんアルゴリズム解法」流れ図と擬似言語で ページ４９ 第２章 基本例題 第１部アルゴリズムと流れ図 ５ １次元配列へのデータ格納 の 表２で、 umaxnの要素"４"と"５" 及び statusの要素"空き"が ○（まる）で囲まれている理由が、解りません。 ご存知の方、教えて下さい。 宜しくお願いします。
- ベストアンサー
- その他（プログラミング・開発）
- アルゴリズムのご相談
はじめまして DHCPのような動作をするアルゴリズムを考えている最中なのですが… その案の中でどうしてもクリア出来ない課題があります。 「配列で作られたテーブルにユーザ名の一覧があり、 そのユーザ名をキーワードとして配列のインデックスを抽出したい」 というもので、これだけなら簡単なのですが、以下３つの条件の提示により、無理ではないかと思えて仕方がないです。 ・ユーザ名は何らかのルールに則って作られた文字列ではない。 ・キーワードを頭から順に比較して探していく方法を使ってはいけない。 ・ユーザの追加・削除がある度にソートし直さなければならないような構造にしてはいけない。 ２分探索法などの検索回数を減らす方法はソートされてることが前提条件ですし、 ユーザ名から配列のインデックスに使える数値に変換できるような都合のいい関数なんて存在しないように思えるのですが、いかがでしょう？ ちなみに開発言語はCです。
- ベストアンサー
- C・C++・C#
補足
ありがとうございます。 検索回数に関しては……。 まず俺が作っているのは、他のプログラムから呼び出されるモジュールです。 アプリケーションからの要求に応じてＣＳＶファイルの中身を読み込み、サーチします。よって、１回しか検索しないかどうかについては何とも言えないのです(^_^; ちなみに、データそのものもアプリケーションが用意した物を使うので、部分的にソートされている可能性があるとも言えるし、ないとも言えます。 どっちにしろご指定の本は便利そうですね。 本屋で探してみようと思います。