16

C++ 標準ライブラリは、次のようなアルゴリズムからデータ構造を分離しますstd::sort

template< class RandomAccessIterator >
void sort( RandomAccessIterator first, RandomAccessIterator last );

アルゴリズムが中間のスクラッチ スペースを必要とする場合、アルゴリズムとデータ構造の分離を維持したいと考えています。

この目標を念頭に置いて、入力画像と出力画像の間に中間のスクラッチ スペースを必要とする画像アルゴリズムを実装したいと考えました。関数呼び出しで必要なスクラッチ スペースを割り当てることもできますが、同じサイズのイメージを使用したこれらの呼び出しのサイズと頻度により、パフォーマンスが大幅に低下します。これにより、データ構造をアルゴリズムから分離することがはるかに困難になります。

これを実現する 1 つの方法は次のとおりです。

// 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;
}

上記は効果的なアルゴリズム + スクラッチ スペースの設計に従うべきですか、それともより良い方法はありますか?

補足: boost::gilライブラリを使用しています

4

4 に答える 4

3

そのような場合、スクラッチスペースの構造体(への参照またはポインター)を渡して、その引数にデフォルト値を与えることができるアルゴリズムがあると思います。このように、構造体を割り当てるための余分な時間が問題にならない場合、ユーザーは構造体を渡さずに関数を呼び出すことができますが、(たとえば)同じスペースを繰り返し再利用することで利益を得ることができる処理パイプラインを構築する場合は、関数を渡すことができます。

于 2013-02-14T23:01:28.747 に答える
2

関数オブジェクトを使用すると、必要な状態を運ぶことができます。

2 つの便利なアルゴリズムは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-11T14:50:27.653 に答える
1

resize()サイズ変更には割り当てだけでなく、既存のコンテンツを古い割り当てから新しい割り当てにコピーする必要があるため、最初の質問で使用するデザインは効率的ではありません。また、古いスペースの割り当てを解除する前に新しいスペースを割り当てて埋める必要があり、最大ピークメモリ使用量が増加します。

クライアントコードにスクラッチスペースとして提供する必要のある構造の大きさを計算する方法を提供し、渡されたスクラッチスペースがエントリ時にライブラリルーチンのニーズを満たしていることを表明することが望ましいです。計算はアルゴリズムクラスの別のメソッドである場合もあれば、スクラッチスペースオブジェクトの割り当て/ファクトリが適切に代表的な引数(正しいサイズ/形状、またはサイズ自体)を取り、適切で再利用可能なスクラッチスペースオブジェクトを返す場合もあります。

ワーカーアルゴリズムは、スクラッチスペースを使用するように求められた後、その操作にコストがかかる傾向があるため、スクラッチスペースを適切にするためにスクラッチスペースを「操作」する必要はありません。

于 2013-03-11T17:59:00.767 に答える
1

おっしゃったように、この質問は実際には、スクラッチ スペースの画像をはるかに超えていると考えることができます。私は実際にこれにさまざまな形で遭遇しました (メモリ セクション、型付き配列、スレッド、ネットワーク接続など)。

だから私がやったのは、一般的な " BufferPool" を自分で書くことでした。これは、バイト配列、他のメモリ、または(あなたの場合)割り当てられたイメージなど、あらゆる形式のバッファオブジェクトを管理するクラスです。このアイデアは からお借りしましたThreadPool

Bufferこれは、オブジェクトのプールを維持する非常に単純なクラスでacquireあり、必要なときにバッファリングreleaseし、使い終わったらプールに戻すことができます。このacquire関数は、プールに使用可能なバッファがあるかどうかを確認し、ない場合は新しいバッファを作成します。プールに 1 つある場合は、新しく作成されたものと同じように動作するように、それをクリアしますresetBuffer

次に、 this の静的インスタンスをいくつか用意します。使用するBufferPool型ごとに 1 つずつです。次に、私が書いているすべてのライブラリ関数でこれらの静的インスタンスを使用します。これにより、たとえば、暗号化関数がバイト配列をバイナリ フラット化関数やアプリケーション内の他のコードと共有できるようになります。このようにして、これらのオブジェクトを最大限に再利用できるようになり、多くの場合、パフォーマンスが大幅に向上しました。Bufferbytechar

C++ では、このプーリング手法に基づいて必要なデータ構造のカスタム アロケーターを作成することで、このどこでも使用できるスキームを非常にエレガントに実装できる場合があります(これを指摘してくれた Andrew に感謝します。コメントを参照してください)。

バイト配列バッファーに対して私が行ったことの 1 つは、必要なバッファーの最小サイズを指定acquireするパラメーターを関数が受け入れるようにすることです。minimumLength次に、プールから少なくともこの長さのバイト配列のみを返すか、プールが空であるか、プールに小さいイメージしかない場合は新しいバイト配列を作成します。画像バッファーでも同じアプローチを使用できます。関数にandパラメータをacquire受け入れさせ、プールから少なくともこれらの寸法の画像を返すか、正確にこれらの寸法の画像を作成します。その後、画像の (0, 0) から ( , ) セクションのみをクリアする必要がある場合でも、関数でクリアすることができます。minWidthminHeightresetminWidthminHeight

私のコードでは気にしないことにした機能の 1 つは、アプリケーションの実行時間と処理する画像サイズの数に応じて、何らかの方法でバッファー サイズを制限するかどうかを検討することをお勧めします。キャッシュされた画像を解放して、アプリケーションのメモリ使用量を減らします。

例として、ここに私が使用するコードを示しますByteArrayPool

public class ByteArrayPool {

    private static final Map<Integer, Stack<byte[]>> POOL = new HashMap<Integer, Stack<byte[]>>();

    /**
     * Returns a <code>byte[]</code> of the given length from the pool after clearing
     * it with 0's, if one is available. Otherwise returns a fresh <code>byte[]</code>
     * of the given length.
     * 
     * @param length the length of the <code>byte[]</code>
     * @return a fresh or zero'd buffer object
     */
    public static byte[] acquire(int length) {
        Stack<byte[]> stack = POOL.get(length);
        if (stack==null) {
            if (CompileFlags.DEBUG) System.out.println("Creating new byte[] pool of lenth "+length);
            return new byte[length];
        }
        if (stack.empty()) return new byte[length];
        byte[] result = stack.pop();
        Arrays.fill(result, (byte) 0);
        return result;
    }

    /**
     * Returns a <code>byte[]</code> of the given length from the pool after optionally clearing
     * it with 0's, if one is available. Otherwise returns a fresh <code>byte[]</code>
     * of the given length.<br/>
     * <br/>
     * If the initialized state of the needed <code>byte[]</code> is irrelevant, calling this
     * method with <code>zero</code> set to <code>false</code> leads to the best performance.
     * 
     * @param length the length of the <code>byte[]</code>
     * @param zero T - initialize a reused array to 0
     * @return a fresh or optionally zero'd buffer object
     */
    public static byte[] acquire(int length, boolean zero) {
        Stack<byte[]> stack = POOL.get(length);
        if (stack==null) {
            if (CompileFlags.DEBUG) System.out.println("Creating new byte[] pool of lenth "+length);
            return new byte[length];
        }
        if (stack.empty()) return new byte[length];
        byte[] result = stack.pop();
        if (zero) Arrays.fill(result, (byte) 0);
        return result;
    }

    /**
     * Returns a <code>byte[]</code> of the given length from the pool after setting all
     * of its entries to the given <code>initializationValue</code>, if one is available.
     * Otherwise returns a fresh <code>byte[]</code> of the given length, which is also
     * initialized to the given <code>initializationValue</code>.<br/>
     * <br/>
     * For performance reasons, do not use this method with <code>initializationValue</code>
     * set to <code>0</code>. Use <code>acquire(<i>length</i>)</code> instead.
     * 
     * @param length the length of the <code>byte[]</code>
     * @param initializationValue the
     * @return a fresh or zero'd buffer object
     */
    public static byte[] acquire(int length, byte initializationValue) {
        Stack<byte[]> stack = POOL.get(length);
        if (stack==null) {
            if (CompileFlags.DEBUG) System.out.println("Creating new byte[] pool of lenth "+length);
            byte[] result = new byte[length];
            Arrays.fill(result, initializationValue);
            return result;
        }
        if (stack.empty()) {
            byte[] result = new byte[length];
            Arrays.fill(result, initializationValue);
            return result;
        }
        byte[] result = stack.pop();
        Arrays.fill(result, initializationValue);
        return result;
    }

    /**
     * Puts the given <code>byte[]</code> back into the <code>ByteArrayPool</code>
     * for future reuse.
     * 
     * @param buffer the <code>byte[]</code> to return to the pool
     */
    public static byte[] release(byte[] buffer) {
        Stack<byte[]> stack = POOL.get(buffer.length);
        if (stack==null) {
            stack = new Stack<byte[]>();
            POOL.put(buffer.length, stack);
        }
        stack.push(buffer);
        return buffer;
    }
}

そして、 が必要な残りのすべてのコードではbyte[]、次のようなものを使用します。

byte[] buffer = ByteArrayPool.acquire(65536, false);
try {
    // Do something requiring a byte[] of length 65536 or longer
} finally {
    ByteArrayPool.release(buffer);
}

acquire要求しているバッファをどの程度「クリーン」にする必要があるかを指定できるようにする3 つの異なる関数をどのように追加したかに注意してください。たとえば、とにかくすべてを上書きする場合、最初にゼロにするために時間を無駄にする必要はありません。

于 2013-03-15T05:24:55.877 に答える