3

我正在寻找加速基于代理的模型的策略，该模型基于 class 的对象Host，指向这些对象的指针存储在 Boost 多索引容器中。我使用 Shark 来确定绝大多数时间都被一个函数消耗calcSI()：

在此处输入图像描述

函数calcSI()必须为类的每个实例计算Host某些概率，这些概率取决于类的其他实例的属性Host。（大约有 10,000-50,000 个实例Host，并且这些计算为每个主机运行大约 25,600 次。）

如果我正确解释了配置文件，则花费的大部分时间都calcSI()转到Host::isInfectedZ(int)，它只是计算类型为 Boost unordered_multimap 中的某些内容的实例InfectionMap：

struct Infection {
public:
  explicit Infection( double it, double rt ) : infT( it ), recT( rt ) {}
  double infT;
  double recT;
};
typedef boost::unordered_multimap< int, Infection > InfectionMap;

Hostcontains的所有成员InfectionMap carriage，并简单地计算与特定键关联Host::isInfectedZ(int)的数量：Infectionsint

int Host::isInfectedZ( int z ) const {
  return carriage.count( z );
}

  1. 我无法找到有关countBoost 的无序多图的功能成本有多大的信息。我是否应该通过添加到Host单独的二维数组来跟踪每个键的实例数（即与每个键Infections关联的数量int）来增加开销？

  2. 我想知道对 Boost 多索引进行更大规模的结构性改革，比如消除一两个不需要的复合键索引，是否会更有帮助。多索引的后台维护没有出现在分析器中，这（可能是愚蠢的）让我担心它可能会很大。我在多索引中有 8 个索引，其中大部分是ordered_non_unique。

  3. 还有其他我应该关注的可能不会出现在分析器中的事情，还是我错过了分析器的主要结果？

不幸的是，并行化和多线程calcSI()不是选项。

更新：知道InfectionMap carriage很少有超过 10 对并且通常有 <5 对可能会有所帮助。

更新 2：我尝试了上面 #1 中提出的策略，给每个Host数组一个数组int carriageSummary[ INIT_NUM_STYPES ]，它由 的可能值索引z（对于大多数模拟，有 <10 个可能的值）。每个条目的值跟踪对 所做的更改carriage。该Host::isInfectedZ( int z )函数现在显示为： 

int Host::isInfectedZ( int z ) const {
  //return carriage.count( z );
  return carriageSummary[ z ];
}
专用于这个函数的时间似乎已经大大减少了——我现在不能做一个精确的比较： 在此处输入图像描述 显然，使用数组有点笨重，但对于小范围的z. 其他一些容器（即不是 unordered_map）对于更大的范围会更有效吗？

也希望获得有关更改多索引的任何反馈。

4

1 回答 1

1

就像您在 #1 中建议的那样，尝试在 Host::carriage unordered_multimap 旁边维护一个托架计数数组，并使它们都“同步”。然后您的 Host::isInfectedZ 将使用（希望）更快的车厢计数数组：

int Host::isInfectedZ( int z ) const {
  return carriageCount[ z ];
}

如果可以传递给 isInfected 的整数范围很大，则使用关联数组作为您的回车计数。

您可以将 std::map 或 boost::unordered 用于关联数组。对于查找，前者具有对数时间复杂度，后者具有恒定时间复杂度。但由于这个关联数组通常非常小，std::map 实际上可能更快。std::map 也可能占用更少的空间开销。尝试两者并运行您的分析器以查看。我的赌注是 std::map。:-)

编辑：

在看到您对我的评论的回答后，我建议使用常规的固定大小数组来计算车厢数。忘记关联数组的东西。

编辑2：

你可能想报废

typedef boost::unordered_multimap< int, Infection > InfectionMap;

并汇总您自己的手写 InfectionMap 类，因为您正在处理如此小的索引。

对更新 #2 的回应：

很高兴看到你取得了进步。我怀疑你会找到一个比固定数组（例如 16 个整数）“更小”的容器。STL 和 boost 容器以块的形式分配内存，最终将与您的固定大小数组一样大，即使它们的元素很少。

您可能对 boost::array 感兴趣，它在 C 风格的固定数组周围包装了一个类似 STL 的接口。这将使您更容易将固定大小的数组“换出”为 std::vector 或 std::map。

于 2011-01-26T20:36:30.750 回答