std::map with std::vector as key -- 查找函数的复杂性
std::map with std::vector as key -- complexity of lookup function
我有一组 N 个客户，索引为 0,...,N-1。定期地，对于某些 S 的客户子集，我需要评估一个函数 f(S)。计算 f(S) 在 |S| 中具有线性复杂度。客户集 S 表示为类型 std::vector<int> 的对象。用于评估的子集每次都可以具有不同的大小。 [由于 S 中客户的顺序无关紧要，因此集合也可以表示为 std::set<int> 或 std::unordered_set<int> 类型的对象。]
在底层应用程序中，我可能有相同的 S 客户子集多次出现以评估 f(S)。我不是每次都招致不必要的线性复杂性，而是想看看它是否会从某种计算量较小的查找中受益。
我正在考虑拥有一个键值对映射，其中键直接是客户向量 std::vector<int> S，映射到该键的值是 f(S)。这样，我希望我可以首先检查地图中是否已经存在一个键，如果存在，我可以查找它而不必再次计算 f(.)。
以 std::vector 作为键的 std::map 是明确定义的。参见，例如，here.
CPPReference表示地图查找时间是对数的。但我认为这是 key 的对数，其中每个键的长度都是恒定的——例如 int 或 double 等。复杂性如何受到影响密钥本身不需要是恒定长度，可以是任意长度，最大为 N?
由于密钥本身可以有不同的大小（每次评估的客户子集可能不同），这是否会在计算哈希函数或 [=28 的比较操作时引入任何额外的复杂性？ =]？将密钥作为固定长度的二进制数组维护 N 有什么好处吗？如果第 i 个客户在集合 S 中，则此二进制数组为 B_S[i]=1，否则为 0。这会使查找更容易吗？
我知道最终在每次重新评估 f(S) 与使用 std::map 之间的设计选择必须根据我的应用程序的实际分析来完成。但是，在实现这两个想法之前（std::map 路线在我的底层应用程序中更难编码），我想知道是否有任何已知的预先存在的最佳实践/基准。
映射中查找的复杂度为O(log N) 也就是说，当映射中有N个元素时，大约需要log N次比较。比较本身的成本会线性增加。例如，当您将 M 向量与 K 元素进行比较时，则大致有 log N 次比较，每次比较 M*K 向量元素，即总共 O(M*K*log N).
然而，渐近复杂性只是：渐近复杂性。当地图中只有少量元素时，低阶因子可能会超过仅在大 N 中占主导地位的 log N。因此，实际运行时间取决于您的特定应用程序，您需要进行测量才能确定。
此外，您一开始就不应该使用向量作为键。这是浪费内存。当S有n个元素时S的子集可以用n位整数枚举（当S的第i个元素在子集）。比较单个整数（或位集）肯定比比较整数向量更有效。
我有一组 N 个客户，索引为 0,...,N-1。定期地，对于某些 S 的客户子集，我需要评估一个函数 f(S)。计算 f(S) 在 |S| 中具有线性复杂度。客户集 S 表示为类型 std::vector<int> 的对象。用于评估的子集每次都可以具有不同的大小。 [由于 S 中客户的顺序无关紧要，因此集合也可以表示为 std::set<int> 或 std::unordered_set<int> 类型的对象。]
在底层应用程序中，我可能有相同的 S 客户子集多次出现以评估 f(S)。我不是每次都招致不必要的线性复杂性，而是想看看它是否会从某种计算量较小的查找中受益。
我正在考虑拥有一个键值对映射，其中键直接是客户向量 std::vector<int> S，映射到该键的值是 f(S)。这样，我希望我可以首先检查地图中是否已经存在一个键，如果存在，我可以查找它而不必再次计算 f(.)。
以 std::vector 作为键的 std::map 是明确定义的。参见，例如，here.
CPPReference表示地图查找时间是对数的。但我认为这是 key 的对数，其中每个键的长度都是恒定的——例如 int 或 double 等。复杂性如何受到影响密钥本身不需要是恒定长度，可以是任意长度，最大为 N?
由于密钥本身可以有不同的大小（每次评估的客户子集可能不同），这是否会在计算哈希函数或 [=28 的比较操作时引入任何额外的复杂性？ =]？将密钥作为固定长度的二进制数组维护 N 有什么好处吗？如果第 i 个客户在集合 S 中，则此二进制数组为 B_S[i]=1，否则为 0。这会使查找更容易吗？
我知道最终在每次重新评估 f(S) 与使用 std::map 之间的设计选择必须根据我的应用程序的实际分析来完成。但是，在实现这两个想法之前（std::map 路线在我的底层应用程序中更难编码），我想知道是否有任何已知的预先存在的最佳实践/基准。
映射中查找的复杂度为O(log N) 也就是说，当映射中有N个元素时，大约需要log N次比较。比较本身的成本会线性增加。例如，当您将 M 向量与 K 元素进行比较时，则大致有 log N 次比较，每次比较 M*K 向量元素，即总共 O(M*K*log N).
然而，渐近复杂性只是：渐近复杂性。当地图中只有少量元素时，低阶因子可能会超过仅在大 N 中占主导地位的 log N。因此，实际运行时间取决于您的特定应用程序，您需要进行测量才能确定。
此外，您一开始就不应该使用向量作为键。这是浪费内存。当S有n个元素时S的子集可以用n位整数枚举（当S的第i个元素在子集）。比较单个整数（或位集）肯定比比较整数向量更有效。