与std::sort
一样,C++标准库将数据结构与算法分开
template< class RandomAccessIterator >
void sort( RandomAccessIterator first, RandomAccessIterator last );
当算法需要中间暂存空间时,我希望保持算法和数据结构的分离。
考虑到这一目标,我想实现一个图像算法,该算法需要输入和输出图像之间的中间临时空间。人们可以在函数调用中分配必要的临时空间,但是由于这些调用的大小和频率具有相同大小的图像,这将严重降低性能。这使得将数据结构与算法分离变得更加困难。
实现这一目标的一种可能方法如下:
// Algorithm function
template<typename InputImageView, typename OutputImageView, typename ScratchView>
void algorithm(
InputImageView inputImageView,
OutputImageView outputImageView,
ScratchView scratchView
);
// Algorithm class with scratch space
template<typename DataStructure>
class Algorithm {
public:
template<typename InputImageView,typename OutputImageView>
void operator()(
InputImageView inputImageView,
OutputImageView outputImageView
){
m_scratch.resize(inputImageView.size());
algorithm(inputImageView,outputImageView,makeView(m_scratch));
}
private:
DataStructure m_scratch;
}
上面的是一种有效的算法+暂存空间设计可以遵循,还是有更好的方法?
附注:我使用的是库
发布于 2013-02-15 07:01:29
我想在这种情况下,我应该让算法允许你为临时空间传递一个结构(一个引用或指针),并给这个参数一个默认值。这样,当/如果分配结构的额外时间不是问题时,用户可以调用函数而不传递结构,但是如果(例如)构建可以从重复使用相同空间中受益的处理流水线,则可以传递一个。
发布于 2013-03-11 22:50:28
如果你使用一个函数对象,你可以携带任何你需要的状态。
两种有用的算法是transform
和accumulate
。
transform
可以接受一个函数对象来对序列中的每个对象执行转换:
class TransformerWithScratchSpace {
public:
Target operator()(const Source& source);
};
vector<Source> sources;
vector<Target> targets;
targets.reserve(sources.size());
transform(sources.begin(), sources.end(),
back_inserter<Target>(targets),
TransformerWithScratchSpace());
accumulate
可以接受一个函数对象,该对象将所有对象累加到自身中。结果是累积的对象。累加器本身不需要产生任何东西。
class Accumulator {
public:
Accumulator& operator+()(const Source& source);
};
vector<Source> sources;
Accumulator accumulated = accumulate(sources.begin(), sources.end(),
Accumulator());
发布于 2013-03-12 01:59:01
您最初提出的使用resize()
的设计效率不高,因为调整大小可能不仅需要分配,还会将现有内容从旧分配复制到新分配。它还需要在释放旧空间之前分配和填充新空间,从而增加最大峰值内存使用。
更可取的做法是,为客户端代码提供某种方法来计算必须提供多大的结构作为暂存空间,然后断言传递的暂存空间在入口处满足库例程的需要。计算可以是algorithm类的另一个方法,或者临时空间对象的分配/工厂可以采用适当的代表性参数(正确的大小/形状,或者大小本身),并返回合适的和可重用的临时空间对象。
worker算法不应该以任何方式“操作”临时空间,以使它在被要求使用它时适合它,因为这种操作往往代价很高。
https://stackoverflow.com/questions/14885361
复制相似问题