需要加快涉及助推多指数和查找的c ++代码加快unordered_multimap

StackOverflow https://stackoverflow.com/questions/4808957

题

我正在寻找策略来加快基于代理的模型，该模型基于类的对象 Host, ，将其存储在Boost多指数容器中的指针。我使用鲨鱼来确定绝大多数时间都被功能所消耗 calcSI():

enter image description here

功能 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;

所有成员 Host 包含 InfectionMap carriage, ， 和 Host::isInfectedZ(int) 只是计算数量 Infections 与特定的 int 钥匙：

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

  1. 我很难找到有关昂贵的信息 count 功能用于Boost的无序多图。我应该通过添加到 Host 一个单独的二维数组来跟踪每个键的实例数（即 Infections 与每个相关联 int)?

  2. 我想知道对增强多指数的更大结构大修是否会更有帮助。多指数的背景维护并未出现在Profiler中，这（也许是愚蠢的）使我担心它可能很大。我在多指数中有8个索引，其中大多数为orded_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 ];
}
以及专门用于此功能的时间 出现 要大量删除 - 我现在无法进行确切的比较：enter image description here 显然，使用阵列有点笨重，但可以很小的范围 z. 。对于较大的范围，其他一些容器（即，不是unordered_map）会更有效吗？

也会喜欢关于更改多指数的任何反馈。

有帮助吗？

解决方案

就像您在＃1中的建议一样，尝试保持主机旁边的马车数组:: carriagar unordered_multimap，并将它们都保持在“同步”。您的主机:: isInfectedZ然后将使用（希望）更快的马车计数数组：

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

如果可以传递到Isefected的整数范围很大，则使用关联阵列进行运输计数。

您可以使用STD :: MAP或BOOST ::无序用于关联阵列。对于查找，前者具有对数时间复杂性，后者具有恒定的时间复杂性。但是，由于这个关联数组通常很小，因此STD :: MAP实际上可能更快。 STD ::地图也可能占用开销的较少空间。尝试一下，然后运行您的剖面店来查看。我的赌注是在STD :: Map上。 :-)

编辑：

看到您对我的评论的回答后，我建议使用常规的固定尺寸阵列进行马车数。忘记关联阵列的东西。

edit2：

你可能想报废

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

并滚动自己的手写IncodectionMap课程，因为您正在处理如此小的索引。

对更新＃2的响应：

很高兴看到您取得了进步。我怀疑您会发现一个比固定的16个整数“笨重”的容器。 STL和Boost容器在块中分配内存，即使它们的元素很少，最终也会像固定尺寸的数组一样大。

您可能对boost ::数组感兴趣，该数组将类似于STL的接口包裹在C型固定数组周围。这将使“交换”您的固定尺寸数组为std :: vector或std :: map变得更加容易。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top