1

次のようなインターフェースを定義するSDKに取り組んでいます

class FooIter
{
    // Move to the next foo, return false if there is none.
    virtual bool Move() = 0;

    // Return a pointer to the current foo.
    virtual const void* GetFoo() = 0;

    // Get the size of a 'foo', which is a fixed-size POD.
    virtual size_t GetFooSize() = 0;

    // Get a comparator for foos.
    virtual const FooComparator* GetComparator() = 0;
};

class FooComparator
{
    virtual int compare(const void* first, const void* second) const = 0;
};

基本的に、foo は不透明な型であり、固定長のバイナリ バッファー + および関連する順序付け関数として扱うことができます。

ここで、これらの foo をクライアント コードに戻す前に並べ替えたいと思います。多くのfooが存在する可能性があるため、外部ソートを実装する必要がありますが、std::sort を使用して最初の実行をソートしたいと考えています。

サイズ N * FooIter::GetFooSize() のバッファーを割り当て、FooIter を使用して foos で埋め、ディスクに書き込む前に std::sort で並べ替えると考えていました。

イテレータクラスを書くことから始めることができます

class FooBufferIter
{
public:
    FooBufferIter(const void* fooAddr, int fooSize) : m_fooAddr(fooAddr), m_fooSize(fooSize) {}

    FooWrapper operator*() {return FooWrapper(m_fooAddr, m_fooSize);}

    FooBufferIter operator++() {return FooBufferIter(m_fooAddr + m_fooSize, m_fooSize);}

    // All other needed iterator methods.
private:
    const void* m_fooAddr;
    int m_fooSize;
};

および foo メモリのラッパー クラス

class FooWrapper
{
public:
    FooWrapper(const void* fooAddr, int fooSize) : m_fooAddr(fooAddr), m_fooSize(fooSize) {}

private:
    const void* m_fooAddr;
    int m_fooSize;
};

私の理解では、 std::sort は std::swap を使用してシーケンス内の要素を再配置します。私の問題は、スワップを効率的に実行するために FooWrapper で std::swap を特殊化する方法がわからないことです (最も重要なのは、動的割り当てがないことです)。バイトごとにスワップすることもできますが、それも非効率的です。

これを行う別の方法は、ポインターの並列シーケンスを Foo 配列にソートすることですが、実際には foo は非常に小さい可能性が高いため、並列シーケンスは同じくらい多くを使用できるため、そうしたくありません。メモリを foo シーケンスとして、一度にソートできる数を最大にしたいと考えています。

おそらくこの種のものにより適した古き良きqsortもありますが、FooComparatorオブジェクトを関数ポインターに変換する方法がわかりません（FooComparatorの複数の実装がある可能性があります）。

または、これについてもっと良い方法がありますか？それほど難しくはないかもしれませんが、私は実際には独自のソートの実装を書きたくありません。

4

1 に答える 1

1

void *のバッファーを作成し、それらをソートしてから、出力バッファーを生成します。

最初のステップとして。簡単だから。次に、他のすべてを記述して、パフォーマンスのボトルネックを探します。

次のステップとして、完全なタイプ情報を使用した内部ソートが実行できるかどうかを確認します。最適だから。

これに失敗すると、特殊なスワップを備えたポッドブロック疑似参照イテレータ。パフォーマンステストがさらなる最適化を正当化する場合、small medおよびbigのtomfooleryを使用して、bigのポインターとsmallのデータをソートします。

しかし、KISSから始めて、最初に難しい部分を実行します。

于 2013-02-23T23:41:25.117 に答える