c++ - 稀疏插入的数据结构

Question

我问这个问题主要是为了确认，因为我不是数据结构方面的专家，但我认为适合我需要的结构是hashmap。

这是我的问题(我想这很典型？):

• 我们正在研究大量对象(比如 N=90k)之间的成对交互，因此将存储视为稀疏矩阵；
• 有一个过程，比如 (P)，它随机从一个对象开始，并计算出可能导致另一个对象的模型:我无法提前预测这些对，所以我需要能够动态地“创建”条目(可以说这里的性能不是很关键)；
• 过程 (P) 可能会“重新访问”现有对并更新矩阵中的相应元素:这种情况经常发生，因此我需要能够尽快找到并更新。
• 最后，进程 (P) 重复了数百万次，但只需要对数据结构的写入权限，它不需要知道最新的“该存储的状态”。这在直觉上感觉像是一个可以被用来提高性能的细节，但我不认为 hashmaps 可以。

最后一点实际上是我在这里提出问题的主要原因:是否存在满足前三点的数据结构(我在想散列映射，对吗？)，并且还可以利用最后一个特征来实现提高性能(我在想像缓冲操作和异步批量执行它们这样的东西)？

编辑:我正在使用 C++，如果有实现该数据结构的现有库，我会更喜欢它。另外，我受限于系统要求；我无法使用 C++11 功能。

Answer 1

我会使用类似的东西:

#include <boost/unordered_map.hpp>

class Data
{
    boost::unordered_map<std::pair<int,int>,double> map;

public:
    void update(int i, int j, double v)
    {
        map[std::pair<int,int>(i,j)] += v;
    }
    void output();  // Prints data somewhere.
};

这会让你继续下去(你可能需要声明一个合适的散列函数)。您可以通过将 key 类型设置为 64 位整数并使用 ((int64_t)i << 32) | j 来加快速度。做索引。

如果几乎​​所有更新都针对对中的一小部分，您可以有两个映射(small 和 large)，并直接更新 small map 。每次的大小small通过了阈值，您可以更新 large清除small .您需要做一些仔细的测试，看看这是否有帮助。我认为它可能有帮助的唯一原因是改进缓存位置。

即使你最终使用不同的数据结构，你也可以保留这个类的接口(interface)，其余的代码将不受干扰。特别是，将 sparsehash 放入相同的结构中将非常容易。