0

我正在寻找适合大量字符串 (> 10^9) 的字符串容器。字符串具有可变长度。它必须是快速的插入和查找，并且具有节俭的内存使用。填充容器时，字符串是无序的。平均字符串长度约为 10 个字节。对确切的字符串值进行查找。可擦除性 - 可选。N 事先是未知的。对于 64 位架构。用例 - 考虑 AWK 的关联数组。

map<string>每个字符串大约有 20-40 位开销，每次插入调用一个 malloc（或两个）。所以它不快也不节俭。

有人可以给我指点 C/C++ 库、数据结构或论文吗？

Relavant——哈希表库的比较

编辑 我已经删除了“大数据”，将 N 提高到更大的值，明确了要求。

4

4 回答 4

6

没有灵丹妙药，但基数树具有trie的优点（快速查找和插入，至少渐近） - 具有更好的空间消耗。

但是 - 两者都被认为不是“缓存效率” - 这可能很重要，特别是如果在某些时候需要对数据进行迭代。

于 2012-08-15T06:51:49.430 回答
2

对于您的问题，64 位机器上的指针几乎与您的数据长度匹配。因此，在您的问题中使用每个字符串的多个指针（平均长度小于 10 个字节）将使数据结构的大小支配您的输入大小。

处理该问题的一种通用方法是不使用指针来表示您的字符串。使用 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);
    }
};

Wherefind_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

（低）误报率是否可以接受？如果是这样，那么布隆过滤器将是一种选择。如果您对百万分之一或 2^(-20) 的误报率感到满意，您会希望使用大约是您期望的字符串数量的 30 倍或 3* 的缓冲区大小10^10 位。那小于4GB。您还需要大约 20 个独立的哈希函数。

如果你不能接受误报，你应该考虑在你构建的任何其他解决方案之前放置一个 Bloom 过滤器，以快速清除大多数否定。

于 2012-08-15T16:27:24.627 回答
1

由于您只插入值，因此字符串数据本身可以在插入时连接 - 每个都带有分隔符，例如 NUL。该单个缓冲区中的字符偏移量唯一地标识了该字符串。这意味着共享公共子字符串的字符串集将分别完全冗余地单独指定，但要反驳的是，不会花费任何精力来尝试查找或编码此类因式分解：对于高度不相关的字符串值（例如随机文本），这可能会适得其反。

要查找字符串，可以使用哈希表。鉴于您的目标是避免频繁的动态内存分配，为了有效地处理冲突，您需要使用置换列表：这个想法是，在将散列到已使用的存储桶的字符串插入时，您添加一个偏移量（必要时环绕表) 并尝试另一个存储桶，继续直到找到一个空存储桶。这意味着您需要一个位移列表来尝试：您可以手动编写一个有限列表来帮助您开始，甚至可能在“大位移”列表上嵌套循环，该列表的值被添加到来自“小位移”的列表中" 列表，直到找到一个空桶，例如，两个 10 个位移的手动编码列表产生 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.1 GB。

值得注意的是，64 位虚拟地址空间意味着您可以安全地为连接的字符串数据和哈希表分配比实际需要更多的空间，并且只有那些实际访问的页面才需要虚拟内存（最初是物理内存，但以后可能通过正常的虚拟内存机制交换到磁盘）。

讨论

如果没有关于所使用的字符串数据或字符集中重复的假设/见解，就无法保证减少字符串内存使用量。

如果所有插入之后都进行大量搜索，那么对字符串数据进行排序并使用二进制搜索将是一个理想的解决方案。但是，对于穿插搜索的快速插入，上述方法是合理的。

您也可以有一个基于平衡二叉树的索引，但是为了避免每次插入的内存分配，您需要将大量节点分组到一个内存页面中，并在较小的粒度级别上手动管理其排序和拆分：痛苦实施。可能已经有一个图书馆在做，但我还没有听说过。

您已经添加了“AWK 中的关联数组”作为可用于此用途的示例。您可以简单地将每个映射到的值直接嵌入到连接数据中的字符串键之后。

于 2012-08-15T10:45:50.537 回答