私はCでバイナリ検索アルゴリズムを作成して、.txtファイルの文字列を検索しています。各行は株式ティッカーを表す文字列です。 Cに慣れていないので、これははるかに長いです。Cのアルファベット順の.txtファイルのバイナリ検索を作成
1）私がfopenを使用してファイルを開いた後は、ファイルをスキャンするためにCライブラリに用意されているいくつかの関数を使用してアルゴリズムを効率よく実行することが理にかなっていますファイルから直接比較を行うか、各行を配列にコピーしてアルゴリズムで配列を検索する必要がありますか？
2.）ファイルから直接比較する必要がある場合は、どのような手順を実行するのが最適ですか？ファイルに行数があると仮定し、真ん中の行に直接移動し、文字列をスキャンして比較を行う方法がいくつかありますか？
これがあまりにも曖昧であれば、ごめんなさい。あまりにもよく説明する方法はわかりません。お時間をいただきありがとうございます
ファイルが非常に大きい（2GB以上）場合を除き、それを検索する前にメモリにファイルをロードするのは方法です。あなたがメモリにファイルをロードできない場合は、int[]の各行のオフセットを保持するか（ファイルに余りにも多くの行が含まれていると...）別のバイナリファイルを作成し、各行のオフセットを整数として書き込みます。
メモリ内のすべてを持つことは、はるかに好ましいことです。
各行の長さを事前に知らなくても、テキストファイルの行をバイナリで検索することはできません。したがって、ファイルが非常に大きい場合を除き、各行を最初にメモリに読み込むことをお勧めします。
しかし、目的ができるだけ早く1つの特定の行を検索するだけであれば、ファイルに対して直接線形検索を行うこともできます。検索が1回しか行われない場合は、O（n）セットアップコストを払ってO（log n）を得ることに意味がありません。
これも良い点です。 OPは彼の必要性について曖昧でした。 – chrisaycock
ええ、私はその中の論理を見ますが、それは学校の課題です。それは、それについて私を混乱させていたもののようなものです。私は、ファイルを線形にスキャンしてセットアップして配列するのであれば、それが効率的であるというアルゴリズムを実装する上でのポイントを見ません。 – meburbo
meburbo：OK。しかし宿題に関する宿題タグを入れるのは良いスタイルだと考えられます。今回はあなたのために追加しました。 – kusma
一括読み込みでそれをすべて読み込み、ポインタ（メモリ）への読み込みは非常に高速です。できるだけ複数のI/Oコールを行うことは避けてください。
私はまた、メモリマップされたファイルは、このようなものに非常に適していることに言及する必要があります。 Unixの場合はmmap()を参照してください。これは間違いなく、本当に大きなファイルのための最良の賭けです。
+1のmmapのために、私は並行して書きました。 –
私は 'mmap（）'についても考えていましたが、ユーザは宿題に応じてバイナリ検索を要求しました。文字列は長さが変わる可能性があるため、ランダムアクセスを行う方法はありません。 – chrisaycock
@chrisaycock：あなたの意見が分かりません。ランダムアクセスは 'mmap（）'と何が関係していますか？ – Oystein
ファイルから直接比較する方法はわかりません。ディスクから読み込んだデータを格納し、そのバッファを使用するには、バッファを用意する必要があります。それは意味をなさない、それはただ不可能です。
ファイル内の特定の行にジャンプすることはできません。ファイルの先頭を基準にした、その行の先頭のオフセットをバイト単位で認識している場合を除きます。
mmapを使用してこのファイルを直接メモリにマップし、文字配列と同様に使用することをお勧めします。オペレーティングシステムは、（seeking、read、writeのような）ファイルをあなたに透過的に扱い、あなたはメモリ内のバッファのように動作します。 mmapは、32ビットシステムでは4 GBに制限されています。しかし、もしそのファイルが大きければ、あなたはたぶんこの質問をする必要があります。
これは大きな質問です。
バイナリ検索の課題は、バイナリ検索の利点は、O（1）の各ステップで要素の半分をスキップできることにあります。これにより、O（lg n）個のプローブしか実行しないため、ランタイムはO（lg n）であることが保証されます。これは、たとえば、リンクリストではなく、配列に対して高速バイナリ検索を実行できる理由です。リンクされたリストでは、要素の途中点が線形時間をとり、検索の時間を支配します。
ファイルに対してバイナリ検索を実行すると、同じ位置にあります。ファイル内のすべての行の長さが同じでない可能性があるため、ファイル内のn行目にジャンプすることはできません。その結果、ファイルに対して良い、高速のバイナリ検索を実装するのはちょっと難しいでしょう。どういうわけか、効率的にファイル内をジャンプできるように、各行の開始と終了を知る必要があります。
これを行う方法はたくさんあります。まず、提案したように、ファイルから配列にすべての文字列をロードできます。これは線形時間を要しますが、メモリ内に文字列が配列されると、それ以降のバイナリ検索は非常に高速になります。あなたが非常に大きなファイルを持っているならば、これは大量のメモリを消費する可能性があり、非常に広大である可能性があるということです。その結果、配列に実際の刺し傷を格納するのではなく、各文字列が出現するファイルにオフセットを格納することもできます。これにより、バイナリ検索を素早く行うことができます。ファイルを比較するときに適切なオフセットを求めることができます。また、大きなスティングは、上記よりもはるかにスペース効率が良いことがあります。また、すべての文字列がほぼ同じ長さである場合は、各行の開始位置を直接計算できるように、すべての行を一定のサイズにパディングすることができます。
さらに複雑なソリューションを実装するのに少し時間を費やしたい場合は、ファイルの前処理を検討して、1行に1つの文字列を使用する代わりに、ファイルの先頭に固定長文字列ファイル内の各文字列のオフセットを含む幅の整数。これは本質的に上記の作業を行いますが、その後の結果をファイルに保存して、将来のバイナリ検索を高速化します。私はこの種のファイル構造についていくつかの経験があり、それはかなり速くなる可能性があります。
本当に挑戦している場合は、Bツリーを使用してファイルに文字列を格納することもできます。これにより、必要なディスク読み取り回数を最小限に抑えて各文字列を非常に高速に検索できますする。
希望すると便利です。
+1私はあなたがここで言及したもののほとんどが現時点でのOPの理解を超えているのではないかと懸念しています。方法を超えて。 – chrisaycock
Cool。ありがとう男 – meburbo
正しい。メモリに読み込み、 'bsearch（）'を使います。 – chrisaycock
ラインのオフセットを格納する必要はありません。 'O '（m log n）'の時刻に '' \ n ''に同期するバイナリ検索を単純に行うことができます。ここで' n'は行数、 'm'は任意の行の最大長です。これはメモリにファイルをロードできず、 'fseek' /' fseeko'を使用しなければならない場合でも動作します。 –