带有C ++键的动态多维数组

问题描述 投票:0回答:1

我正在尝试找到一种很好的方法来处理C ++中的以下情况。

当我们在服务器上启动服务时,将根据数据库中的数据初始化如下所示的参数表。

ID, filed_1, field_2, .... , field 50
100abc, ***, ***, ...., ***
120def, ***, ***, ...., ***
...
...
500xyz, ***, ***, ..., ***

字段/列:大约50。字段的数量和格式是固定的。所有字段的类型都是int,double或char *(不是很长的char *)。

记录/行:最多200。根据数据,每次的记录数都会不同。

ID是唯一的。

在计算过程中,参数表将被读取并每秒更新500次。 (我假设按ID和字段名称搜索)

低延迟在系统中很重要。

在这种情况下将使用的最佳数据结构是什么?

如果没有写(更新)操作,有可以大大提高效率的方法,请也共享信息。我认为有一些变通办法可以不对参数表进行更新。

非常感谢。

c++ json dictionary vector hash
1个回答
0
投票

FYI,您问的是有关算法和数据结构的自以为是的问题,通常更适合此堆栈交换站点:https://softwareengineering.stackexchange.com/

无论如何,用所有适当的盐粒,这是我不知情的看法。考虑到这一点:

字段的数量和格式是固定的。

和此:

低延迟在系统中很重要。

考虑使用具有完美哈希功能的哈希图来按名称查找字段。以前,您将使用gperf作为生成步骤来在C中生成哈希函数,但是使用C ++ constexpr magic,您可以使用以下选项:

https://github.com/Kronuz/constexpr-phf

此处的文档非常有用,因此无济于事,因此,这里是您使用它的方式。首先输入您的字段以执行哈希函数:

fnv1ah32 fnv1a{};
constexpr auto fields_phf = phf::make_phf({
    fnv1a("field1"), 
    fnv1a("field2"), 
    fnv1a("field3"), 
    fnv1a("field4")
    /* , ... */
});

我对使用什么值没有什么特别的了解,但是由于您要存储3种类型之一,因此在此示例中,我将使用std::variant

// ...assuming your field values will fit in std::string's short string optimization
using Value = std::variant<int, double, std::string>;

然后您可以将O(1)查找表包装在连续的数据周围:

struct Row {
    std::array<Value, FIELD_COUNT> fields;

    template <typename T>
    Value& operator [](T&& t) { 
        auto pos = fields_phf.find(fnv1a(t));
        if (pos == phf::npos) {
            throw std::runtime_error("unknown field");
        }
        return fields[pos];
    }
};

然后使用常规哈希表查找行,如果您事先不知道值,这是一个很好的默认值。保留200行以最大程度地减少重新哈希,因为您认为这是您的上限:

std::unordered_map<std::string, Row> table;
table.reserve(200);

然后您可以进行查找:

int main() {
table["row1"]["field1"] = 42;
table["row2"]["field2"] = "hello";

演示:https://godbolt.org/z/z8euVY

© www.soinside.com 2019 - 2024. All rights reserved.