我想很快解决许多小型DAGS(8-12个节点,20-60个边缘)的最小切割问题.看起来最好的解决方案是解决最大流量并从中推断.有很多最大流算法,可用理论和经验时序比较,但这些都假设有趣的是性能随着图形变得越来越大.还经常提到使用的复杂数据结构的设置时间可能非常大.因此,考虑到一个仔细的,优化的实现(可能在C++中),哪种算法最适合在小图上初始化和运行？(我天真的假设是Edmonds-Karp在数据结构方面可能很简单,因此会击败更复杂的算法,但这只是一个猜测.)
这是我在C++表达式模板编程中没有明确解决的一件事,以避免构建不必要的临时(通过创建仅在赋值运算符处折叠的"无限模板对象"的树).假设为了说明我们正在对1-D值序列进行建模,使用算术运算符(如+,*等)的元素应用.为完全创建的序列调用基本类Seq(其中包含固定长度的双精度列表)为了具体而考虑以下说明性伪C++ - 代码.
void f(Seq &a,Seq &b,Seq &c,Seq &d,Seq &e){
AType t=(a+2*b)/(a+b+c); // question is about what AType can be
Seq f=d*t;
Seq g=e*e*t;
//do something with f and g
}
其他地方有+等的表达式模板化重载.对于定义t的行:
如果我使AType成为Seq,我可以实现这个代码,但是当我不需要它时,我已经创建了这个完整的中间变量(除了它如何能够计算f和g).但至少它只计算一次.
我也可以实现这个,使AType成为适当的模板化表达式类型,这样就不会在注释行创建一个完整的Seq,而是在f和g中使用chunk-by-chunk.但是,在f和g中将重复创建每个特定块所涉及的相同计算.(我认为理论上一个非常聪明的编译器可能会意识到相同的计算正在进行两次和CSE-it,但我认为没有做到,我不想依赖于优化器始终能够发现机会. )
我的理解是,没有聪明的代码重写和/或模板的使用,只允许每一块t计算一次,并且 t可以计算chunkwise而不是一次计算？
(我可以模糊地想象AType可能是某种对象,它包含表达式模板类型和第一次计算后写入的缓存值,但这似乎没有帮助同步两个隐式循环的需要在f和g的赋值中.)
在谷歌搜索中,我遇到了一篇关于另一个主题的硕士论文,其中提到通过表达模板应该避免使用手册"共同的子表达式消除",但我想找到一个更权威的"它是不可能的"或"这里的"怎么做".
最接近的stackoverflow问题是使用表达式模板的中间结果 ,这似乎与类型命名问题有关,而不是创建完整中间体的效率问题.