問題タブ [on-disk]

インデックスを作成したいファイル (具体的には fasta ファイル) があるので、ファイル内の部分文字列をすばやく見つけて、元の fasta ファイル内の場所を見つけることができます。

これは多くの場合、Trie または部分文字列配列を使用して簡単に実行できますが、残念ながら、インデックスを作成する必要がある文字列は 800 MB 以上であるため、メモリ内でそれらを実行することは受け入れられないため、これを作成する合理的な方法を探しています。メモリ使用量を最小限に抑えて、ディスク上にインデックスを作成します。

（明確にするために編集）

私が関心があるのはタンパク質のヘッダーだけなので、関心のある最大のデータベースの場合、これは約 800 MB のテキストになります。

入力文字列に基づいて、O(N) 時間以内に正確な部分文字列を見つけられるようにしたいと考えています。これは 32 ビット マシンで使用できる必要があります。これは、64 ビット マシンを使用することが想定されていないランダムな人々に出荷されるためです。

行内の任意の単語区切りに対して、行の最後までインデックスを作成できるようにしたいと考えています (ただし、行の長さは数 MB になる場合があります)。

これにより、何が必要であり、現在の解決策が明らかにされていない理由が明確になることを願っています。

また、これはJava内から実行する必要があり、さまざまなオペレーティングシステムのクライアントコンピューターで実行する必要があるため、OS固有のソリューションを使用できず、プログラムソリューションでなければならないことも付け加えておく必要があります.

私は STL を使用してアルゴリズムを開発することを楽しんでいますが、データ セットがヒープに対して大きすぎるという問題が繰り返し発生します。

私は、STL コンテナーと、ディスクに支えられたアルゴリズム、つまりヒープではなくディスクに格納されたデータ構造のドロップイン代替品を探していました。

最近、友人が私にstxxlを指摘しました。私がそれに関与する前に... 私が検討すべき他のディスクでバックアップされた STL の代替品はありますか?

注: 永続性や組み込みデータベースには興味がありません。boost::serialization、POST++、Relational Template Library、Berkeley DB、sqlite などについては言及しないでください。私はこれらのプロジェクトを認識しており、目的に適した場合に使用しています。

更新: 何人かの人々がメモリ マッピング ファイルとカスタム アロケータの使用について言及していますが、良い提案です。つまり、カスタム アロケーター アプローチは機能しない可能性があります。

多数の整数を格納する必要があります。整数の入力ストリームに重複がある可能性があります。それらの間で個別に格納する必要があります。最初はstlsetを使用していましたが、整数の入力数が多すぎるとOutOfMemになりました。私は、ファイルに裏打ちされた可能性のある上記の要件で番号を格納できるC ++コンテナライブラリを探しています。つまり、コンテナはすべての番号をメモリ内に保持しようとすべきではありません。このデータを永続的に保存する必要はありません。データの中から一意の値を見つける必要があります。

B+Tree のオンディスク実装がどこにあるか知っている人はいますか? 私はグーグルを前後に調べましたが、残念ながら賢明なものは見つかりませんでした。他のスレッドは、おそらく sqlite、sqljet、または bdb からツリーを取得することを提案していますが、これらのツリーはデータベース全体にネストされており、実際には B+Tree を「単に」除外することはできません。私は本当にディスク上の B+Tree だけを探しています...周りに派手なものはありません。

私は約 5 億の 128 ビット整数を持っており、年間約 1 億を追加しています。何も削除されません。数値は、スケールごとおよび時間ごとに均一に分布しています。

基本的に、必要なのは追加操作だけで、数値が DB に既に存在するかどうかも返します。また、このシステムに RAM を使いすぎたくないので、すべてをメモリに格納するだけでは探していません。

これまで、2 つの bigint を主キーとして使用して、MySQL で複数の MyISAM テーブルを使用してきました。これで十分なパフォーマンスが得られますが、この作業には適切なツールではないと思います。テーブルを分割する前にいくつかのパフォーマンスの問題が発生し、停電時に破損が発生しました。また、DB は必要のない多くの機能を提供してくれます。

Linux で Python を使用していますが、提案は受け付けています。

C++ での同様の質問。

更新: Marcelo のコメントはBloom Filterに言及しており、これは私にとって本当に有望なようです。私はハッシュを扱っているので、完全な正確さをあきらめているので、これは精度とパフォーマンスの大きなトレードオフになる可能性があります。

Javaでスパースファイルの正確な（つまり、ディスク上の実際のサイズであり、すべての0を含む通常のサイズではない）測定値を取得しようとしています。

Windows上のC++では、を使用しますGetCompressedFileSize。私はまだJavaでそれを行う方法に出くわしていませんか？

直接同等のものがない場合、すべてのゼロを含むサイズではなく、スパースファイル内のデータを測定するにはどうすればよいですか？

明確にするために、Linux OSとWindowsの両方でスパースファイル測定を実行するためにこれを探していますが、2つの別々のアプリケーションをコーディングしてもかまいません！

質問の簡略版

私は巨大なマトリックスのようなデータセットを持っています.今のところ、実際にはIEEE-754 doubleとしてディスク上に保存されているマトリックスnごとのふりをすることができます. ファイルはギガバイトのオーダーですが、特定の (純粋な) 関数では、ファイルに含まれる要素のオーダーのみが必要です。どの要素が必要になるかは複雑で、単純なスライスのようなものではありません。nn^2n

ディスクからのファイルの読み取りと計算を分離するためのオプションは何ですか? 何よりも、ディスク上のデータをメモリ内にあるかのように扱いたいと思います (もちろん、ディスク上のデータが変更されないことを参照透過性のすべての神々に誓う準備ができています)。私はmmapとfriendsを見てきましたが、いくつかの大雑把なテストでは、これらが積極的に十分な空きメモリを確保していないように見えることが示されています。

メモリに保持するファイルの量を細かく制御する必要がある場合、計算を IO に結合する必要がありますか?

ディスク上のデータのより正直な説明

ディスク上のデータは、実際には説明されているほど単純ではありません。真実に近いものは次のとおりです。ファイルは 32 ビット整数で始まりますn。次に、次のことが正確に発生しますn: 32 ビット整数m_i> 0 (1 ≤ i ≤ n) の後に、正確にm_iIEEE-754 の doubleが続きx_(i,1),…,x_(i, m_i)ます。(つまり、これはギザギザの 2 次元配列です)。

実際には、 と が必要な理由の決定iは、jにx_(i, j)大きく依存しm_iます。mmap の問題に近づくと、これらの多くの s を読み取る必要があるため、m_i基本的にファイル全体がメモリに読み込まれるようです。IO問題は、すべてがそこにとどまっているように見えることです。このメモリの解放をよりきめ細かく制御するには、計算を引き込む必要があるのではないかと心配しています。

さらに、「データ構造」は、実際には、ファイル名でパラメータ化された多数のこれらのファイルで構成されています。それらを合わせると、約 1 ギガバイトになります。

より手を振る試みですが、質問のバージョンを理解しやすい可能性があります

n^2要素で構成されるディスク上にいくつかのデータがあるとします。純粋な Haskell 関数nは要素の順序を必要としますが、それらのどれが複雑な方法で値に依存します。ファイルが巨大なので、ファイル全体をメモリにロードしたくありません。1 つの解決策は、関数をモナドに投入し、IO必要に応じて要素を読み取ることですが、私はこれを「あきらめる」と呼んでいます。mmapを使用すると、ディスク上のデータをメモリ内にあるかのように扱うことができ、基本的に OS の仮想メモリ システムの助けを借りて遅延 IO を実行できます。これは良いことですが、データのどの要素が必要かを判断するには大量のファイルにアクセスする必要があるため、mmap はメモリ内にあまりにも多くのファイルを保持しているようです。実際には、データを読み取る必要があることを発見しました。mmap を使用する場合、実際にはファイル全体をメモリにロードする必要があります。

どのようなオプションがありますか?

ストレージ レイアウトが論理設計と正確に一致する必要があることを考えると、ディスク上のデータ構造を操作する最善の方法を知りたいです。ストレージに特定のレイアウトが必要な場合、構造の配置とパッキングはあまり役に立たないことがわかりました.

この問題に対する私のアプローチは、プロセッサ ディレクティブを使用して構造の (幅) を定義し、論理構造モデルに従うデータを追加した後にディスクに書き込む文字 (バイト) 配列を割り当てるときに幅を使用することです。

例えば：

ディスク上で foo を永続化すると、「フラグ」値がデータの最後に来ます。&foo 型で fread を使用してデータを読み取るときに foo を簡単に使用できることを考えると、さらにバイトをいじることなく、通常どおり構造体を使用できます。

代わりに、私はこれを行うことを好みます

次に、fwrite と fread を使用してバイトをコミットして読み取りますが、後でそれらをアンパックして、さまざまな論理フィールドに格納されたデータを使用します。

ディスク上のストレージのレイアウトを論理レイアウトと一致させたい場合、どのアプローチを使用するのが最適なのだろうか...これは単なる例です...

バイトのデコード/アンパックとディスク上の表現から構造を直接コピーすることに関して、各方法がどれほど効率的かを誰かが知っている場合は、共有してください。このアプローチでは、データ内のさまざまな境界までバイトをアンパック/トラバースするために多くのループ ロジックが必要になるため、パフォーマンスを犠牲にする必要があります。

ありがとう。

現在、iOS オンディスク暗号化がどのように機能するかを理解しようとしています。iOS アプリ プログラミング ガイドのオンディスク暗号化を使用したデータの保護を読みました。ユーザーはデバイスにアクティブなパスコード ロックを設定する必要があると表示されます。

しかし、私にはまだ不明な点がいくつかあります。

次の場合、アプリケーションは以前に暗号化されたファイルを復号化できますか?

1. ユーザーはパスコードを無効にしますか?
2. ユーザーはパスコードを無効にしてから、同じ値で有効に戻しますか?
3. ユーザーはパスコードを変更しますか?

特定のノードの着信リレーションシップと発信リレーションシップを介してクエリを実行すると、パフォーマンスの違いに気付きました。この場合、発信ははるかに高速でした。

グラフを生成する入力ファイルは、各エッジの開始ノードでソートされます。

入力ファイルの順序は重要ですか? 外向的な関係の扱い方に違いはありますか?

内部の背景を少し読みましたが、パフォーマンスの違いに関する私の質問には答えていないようです。