0

多数の文字列（> 10 ^ 9）に適した文字列コンテナを探しています。文字列の長さは可変です。挿入とルックアップが高速で、メモリの使用量が少ない必要があります。コンテナがいっぱいになると、文字列は順序付けられません。文字列の平均の長さは約10バイトです。正確な文字列値でルックアップが実行されます。消去可能性-オプション。Nは事前に不明です。64ビットアーキテクチャの場合。ユースケース-AWKの連想配列について考えてみましょう。

map<string>文字列ごとに約20〜40バイトのオーバーヘッドがあり、挿入ごとに1つのmalloc（または2つ）が呼び出されます。したがって、それは速くなく、質素でもありません。

誰かが私にC/C ++ライブラリ、データ構造、または論文を教えてもらえますか？

Relavant-ハッシュテーブルライブラリの比較

編集 私は「ビッグデータ」を削除し、Nをより大きな値に上げ、要件を明確にしました。

4

4 に答える 4

6

特効薬はありませんが、基数木は、より良いスペース消費で、トライの利点を提供します（少なくとも漸近的に高速ルックアップと挿入）。

ただし、どちらも「キャッシュ効率が悪い」とは見なされません。これは、ある時点でデータの反復が必要な場合に特に重要になる可能性があります。

于 2012-08-15T06:51:49.430 に答える
2

問題の場合、64ビットマシン上のポインタはデータの長さとほぼ一致します。したがって、問題で文字列ごとに複数のポインタを使用すると（平均長が10バイト未満）、データ構造のサイズが入力のサイズを支配することになります。

これに対処する一般的な方法の1つは、文字列を表すためにポインタを使用しないことです。すべての文字列が格納される大きなページへの32ビットオフセットを使用する特殊な表現では、文字列を取得するためにポインタを追加する必要がありますが、ポインタのメモリ要件が半分になります。

編集：以下は、そのような表現のサンプル（テストされていない）実装です（struct簡単にするために、実際の実装はもちろんユーザーインターフェイスを公開するだけです）。この表現はハッシュテーブルの挿入を想定しているため、の余地がありnext_ます。hash_nodeオフセットは、32ビットオフセットで表現できるように、のサイズでスケーリングされることに注意してください。

struct hash_node {
    uint32_t next_;
    char * str () { return (const char *)(&next+1); }
    const char * str () const { return (const char *)(&next+1); }
};

struct hash_node_store {
    std::vector<hash_node> page_; /* holds the allocated memory for nodes */
    uint32_t free_;

    hash_node * ptr (uint32_t offset) {
        if (offset == 0) return 0;
        return &page_[offset-1];
    }

    uint32_t allocate (const char *str) {
        hash_node *hn = ptr(free_);
        uint32_t len = strlen(str) + 1;
        uint32_t node_size =
            1 + (len / sizeof(hash_node)) + !!(len % sizeof(hash_node));
        strcpy(hn->str(), str);
        free_ += node_size;
        return 1 + (hn - &page_[0]);
    }
};

ハッシュテーブルには、ノードストアとハッシュバケットベクトルが含まれます。

struct hash_table {
    hash_node_store store_;
    std::vector<uint32_t> table_; /* holds allocated memory for buckets */

    uint32_t hash_func (const char *s) { /* ... */ }

    uint32_t find_at (uint32_t node_offset, const char *str);
    bool insert_at (uint32_t &node_offset, const char *str);

    bool insert (const char *str) {
        uint32_t bucket = hash_func(s) % table_.size();
        return insert_at(table_[bucket], str);
    }

    bool find (const char *str) {
        uint32_t bucket = hash_func(s) % table_.size();
        return find_at(table_[bucket], str);
    }
};

ここfind_atで、およびinsert_atは、期待される方法で実装された単純な関数です。

uint32_t hash_table::find_at (uint32_t node_offset, const char *str) {
    hash_node *hn = store_.ptr(node_offset);
    while (hn) {
        if (strcmp(hn->str(), str) == 0) break;
        node_offset = hn->next_;
        hn = store_.ptr(node_offset);
    }
    return node_offset;
}

bool hash_table::insert_at (uint32_t &node_offset, const char *str) {
    if (! find_at(node_offset, str)) {
        uint32_t new_node = store_.allocate(str);
        store_.ptr(new_node)->next_ = node_offset;
        node_offset = new_node;
        return true;
    }
    return false;
}
于 2012-08-15T09:00:40.227 に答える
1

値を挿入するだけなので、文字列データ自体を挿入時に連結できます。それぞれにNULなどの区切り文字を使用します。その単一のバッファへの文字オフセットは、文字列を一意に識別します。これは、共通の部分文字列を共有する文字列のセットがそれぞれ完全に冗長に個別に指定されることを意味しますが、そのような因数分解を見つけたりエンコードしたりするために労力が費やされることはありません。

文字列を見つけるために、ハッシュテーブルを使用できます。頻繁な動的メモリ割り当てを回避するという目的を考えると、衝突を効率的に処理するには、変位リストを使用する必要があります。つまり、すでに使用されているバケットにハッシュする文字列を挿入するときに、オフセットを追加します（必要に応じてテーブルをラップします）。 ）そして、他のバケットを試して、空のバケットが見つかるまで続けます。つまり、試すには変位のリストが必要です。有限のリストを手動でコーディングして開始することも、「小さな変位」の値に値が追加された「大きな変位」リストにループをネストすることもできます。 "空のバケットが見つかるまでリストします。たとえば、10個の変位の2つの手書きリストは、100個の組み合わせを生成します。（代替ハッシュアルゴリズムは、変位リストの代わりに、または変位リストと組み合わせて使用​​できます。

したがって、必要なスペースは次のとおりです。

total_bytes_of_string_data + N delimiters + total_buckets * sizeof(string_offset)

ここで、sizeof（string_offset）はおそらく8バイトを必要とします。これは、10 ^ 9*10がすでに2^32を超えているためです。

〜10文字の10^9文字列と1.2*10 ^ 9バケットの場合、これは約10 ^ 9 *（10 + 1）+ 1.2 * 10 ^ 9*8バイト=20.6^ 10^9バイトまたは19.1GBです。

64ビットの仮想アドレス空間は、連結された文字列データとハッシュテーブルに実際に必要なスペースよりもはるかに多くのスペースを安全に割り当てることができることを意味し、実際にアクセスされるページのみが仮想メモリ（最初は物理メモリですが、後で可能になる可能性があります）を必要とすることに注意してください。通常の仮想メモリメカニズムを介してディスクにスワップされます）。

討論

使用される文字列データまたは文字セットの繰り返しに関する仮定/洞察がなければ、文字列メモリ使用量の削減を保証する方法はありません。

すべての挿入の後に膨大な数の検索が続く場合は、文字列データを並べ替えてバイナリ検索を使用するのが理想的なソリューションです。ただし、検索が散在する迅速な挿入には、上記が妥当です。

バランスの取れた二分木に基づいたインデックスを作成することもできますが、挿入ごとのメモリ割り当てを回避するには、多数のノードを1つのメモリページにグループ化し、その順序と分割をより詳細なレベルで手動で管理する必要があります。埋め込む。すでにそれを行っている図書館があるかもしれませんが、私はそれを聞いたことがありません。

これを使用できる例として、「AWKの連想配列」を追加しました。連結されたデータの文字列キーの直後に、マップされた各値を簡単に埋め込むことができます。

于 2012-08-15T10:45:50.537 に答える
1

（低い）偽陽性率は許容されますか？もしそうなら、ブルームフィルターはオプションになります。誤検出率が100万分の1、つまり2 ^（-20）で満足している場合は、予想される文字列数の約30倍、つまり3*のビット単位のバッファーサイズを使用することをお勧めします。 10^10ビット。それは4GB未満です。また、約20の独立したハッシュ関数が必要です。

誤検知を受け入れることができない場合は、構築する他のソリューションの前にブルームフィルターを配置して、ほとんどのネガティブをすばやく取り除くことを検討する必要があります。

于 2012-08-15T16:27:24.627 に答える