我正在尝试找到一种很好的方法来处理C ++中的以下情况。
当我们在服务器上启动服务时,将根据数据库中的数据初始化如下所示的参数表。
ID, filed_1, field_2, .... , field 50
100abc, ***, ***, ...., ***
120def, ***, ***, ...., ***
...
...
500xyz, ***, ***, ..., ***
字段/列:大约50。字段的数量和格式是固定的。所有字段的类型都是int,double或char *(不是很长的char *)。
记录/行:最多200。根据数据,每次的记录数都会不同。
ID是唯一的。
在计算过程中,参数表将被读取并每秒更新500次。 (我假设按ID和字段名称搜索)
低延迟在系统中很重要。
在这种情况下将使用的最佳数据结构是什么?
如果没有写(更新)操作,有可以大大提高效率的方法,请也共享信息。我认为有一些变通办法可以不对参数表进行更新。
非常感谢。
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";