1

何百万もの符号なし long を保持する必要がある (ベクトルのように) 挿入されるようにデータを保持するデータ構造を探しています。重要なのは、同じサイズの同様のベクトルに対して検索されるため、O(logn) よりも優れたルックアップが必要であるということです。このように存在するものはありますか？

10、20、30 を挿入してセットを反復処理する場合、10、20、30 の順序を保証する必要があります。データは、メモリ使用量を減らすために unsigned long に変換した文字列であり、逆デコード可能です。

編集:人々が尋ねているので、違いを得るために2つのベクトル(両方ともサイズが非常に大きい)を比較しています。

小さな例:

vector 1: 10 20 30 40 50 60

vector 2: 11 24 30 40 55 70 90

result:   30 40
4

3 に答える 3

4

私自身は使用したことがなく、最近の C++ バージョンの機能 (最終更新は 2011 年のもの) に比べて古くなっている可能性がありますが、STXXLは非常に大量のデータ用に構築されたコンテナーとアルゴリズムのセットであることを意図しています。それはあなたのニーズに合うかもしれません。

STXXL のコアは、外部メモリ (コア外) 計算用の C++ 標準テンプレート ライブラリ STL の実装です。つまり、 STXXL は、ディスクにのみ収まる膨大な量のデータを処理できるコンテナーとアルゴリズムを実装します。STL に近いため、使いやすさと既存のアプリケーションとの互換性がサポートされますが、もう 1 つの設計上の優先事項は高性能です。

STXXL の主な機能は次のとおりです。

  • 並列ディスクの透過的なサポート。このライブラリは、基本的な並列ディスク アルゴリズムの実装を提供します。STXXL は、並列ディスクをサポートする唯一の外部メモリ アルゴリズム ライブラリです。
  • このライブラリは、非常に大きなサイズ (数十テラバイトまでテスト済み) の問題を処理できます。
  • コンピューター リソースの使用率の向上。外部メモリ アルゴリズムとデータ構造の STXXL 実装は、I/O と計算のオーバーラップの恩恵を受けます。
  • I/O ボリュームの小さな定数要因。「パイプライン化」と呼ばれる独自のライブラリ機能は、データを一時的にディスクに保存する代わりに、アルゴリズム コンポーネント間でデータをストリーミングすることにより、I/O の数を半分以上節約できます。開発ブランチは、アルゴリズム コンポーネントの非同期実行をサポートし、高度なタスクの並列処理を可能にします。
  • 外部メモリ アルゴリズムおよびデータ構造用の周知の STL 互換インターフェイスにより、開発時間が短縮されます。
  • STL アルゴリズムは、STXXL コンテナーに直接適用できます。さらに、ほとんどの場合、アルゴリズムの I/O の複雑さは最適のままです。

内部計算では、MCSTL または libstdc++ 並列モードの並列アルゴリズムがオプションで利用され、アルゴリズムは本質的にマルチコア並列処理の恩恵を受けます。

于 2013-06-17T22:56:29.923 に答える
0

使用する必要があるのは、 unordered_map と注文の二重リンクリストを組み合わせたものだと思います。

したがって、データベースに新しいアイテムを追加するたびに、最初にリンク リストの前 (または最後) に追加し、次にそれをキーが値 (unsigned int) であるハッシュマップに追加し、"value " (キーと値のペアから) は、リンクされたリスト内のオブジェクトへのポインターです。したがって、高速なルックアップが必要な場合はハッシュマップを参照し、順序で反復したい場合はリンク リストを使用します。もちろん、オブジェクトを削除したい場合は、両方から削除する必要がありますが、複雑さは同じです (O(1) はすべて償却されます)。

これにより、もちろん、ハッシュマップを使用する場合と比較して、メモリが 2 または 3 増加します。

于 2013-06-17T22:50:35.807 に答える