-3

設計上の課題に直面しています。サイズが 10000 の say とstd::vector<int>呼ばれる巨大なものがあります。それぞれにのサブオーダーである内部があります。例えば：OFoof_1f_nFoostd::vector<int>O

O = 1, 2, ..., 100000
f_1.order = 1, 2, 3
f_2.order = 1, 4, 16
f_3.order = 100, 101, 102
// ...

主な要件は、が値を変更しOたときに の対応する値を更新することです。f_nすべてのオブジェクトの長さと内容はFoo構築時に認識され、存続期間中に変更されることは想定されていません。たとえば、 のf_11 番目、2 番目、3 番目の要素を保持することが知られていますO。

明らかな解決策は、もちろんポインターを使用することです。各要素が元の順序 ( ) の基になるデータを指す をFoo保持する場合があります。std::vector<int*>O

一方、私のプログラムは、Fooオブジェクトを使用していくつかの重い計算を行います。そのため、ポインターの逆参照のオーバーヘッドを取り除く方法を探しています。設計で何らかの使用が許可されていればいいのですstd::vector<int&>が、それは不可能です (のvector<T>存在が必要なためだと思いますT*)。

同僚が の使用を提案しましたboost::ptr_vector。別の提案されたインデックスをvector<size_t>...

4

3 に答える 3

5

これはいくら強調してもしすぎることはありません。問題があることに気付く前に、コードを最適化しないでください。ポインターの逆参照はコストがかからず、通常、プログラムの主なボトルネックにはなりません。

参照はポインター逆参照を使用して実装されるため、できたとしてもstd::vector<int&>役に立たないことに注意してください。

何かをしなければならないと本気で感じているなら、それが意味のある意味であなたのパフォーマンスを助けることはできないと私は本当に完全に確信していますが、メモリを重ねてみることができます. つまり、次のように定義できます (私は決してこれを支持しているわけではありません。もっと悪いことをしないように指摘しているだけです)。

std::vector<int> O;

struct Foo {
   int *myData;
   int &operator[](int offset) { return myData[offset]; }
};

O.resize(1000000, 0);
Foo f_1, f_2, ...;
f_1.myData = &(O[0]);
f_2.myData = &(O[3]);

O[0] = 5;
cout << f_1[0]; // prints 5

Oまた、ところで - 名前を変数として使用しないでください。お願いします。それはゼロのように見えます。

于 2013-07-19T16:52:04.367 に答える
2

時期尚早の最適化のように聞こえます。ポインターの逆参照は、途方もなく安価です。

明らかな解決策は、もちろんポインターを使用することです。Foo は、各要素が元の順序 (O) の基になるデータを指す std::vector を保持する場合があります。

ここで、std::reference_wrapper と std::ref を使用して、ポインターを使用せずに必要なものを差し引く解決策を示します。

struct Foo
{
    Foo(std::vector<int>& _data) : dataFull(_data)
    { ; }

    void add(int index)
    {
        assert(index < dataFull.size());

        if(index < references.size())
        {
            // replace
            references[index] = std::ref(dataFull[index]);
        }
        else
        {
            // add n times, need sync with index
            while(index >= references.size())
            {
                references.push_back(std::ref(dataFull[index]));
            }
        }

        // mark as valid index
        indexes.push_back(index);
        // sort for can find with binary_search
        std::sort(indexes.begin(), indexes.end());
    }

    int* get(int index)
    {
        if(std::binary_search(indexes.begin(), indexes.end(), index))
        {
            return &references[index].get();
        }
        else
        {
            return NULL;
        }
    }

protected:
    std::vector<int>& dataFull;
    std::vector<std::reference_wrapper<int> > references;
    std::vector<int> indexes;
};

int main()
{
    const int size = 1000000;
    std::vector<int> O;
    O.resize(1000000, 0);

    Foo f_1(O);
    f_1.add(1);
    f_1.add(2);
    f_1.add(3);

    Foo f_2(O);
    f_2.add(1);
    f_2.add(4);
    f_2.add(16);

    Foo f_3(O);
    f_3.add(100);
    f_3.add(101);
    f_3.add(102);

    // index 1 is changed, it must affect to all "Foo" that use this index (f_1 and f_2)
    O[1] = 666;

    // checking if it changed
    assert( *f_1.get(1) == 666 );
    assert( *f_2.get(1) == 666 );
    assert(  f_3.get(1) == NULL );

    return 0;
}

編集: ポインターを使用する場合とパフォーマンスは同じですが、T& があり、T* と T& のコードを必要としないため、std::reference_wrapper はテンプレート化されたコードに最適に統合できます。

他のベクトルにインデックスを持ちます。構造体が複数の基準で順序付けされている場合にのみ役立ちます。

ベクトルの例を示します。ここで、T は 2 つのフィールドを持つ構造体複合体です。オリジナルに手を加えることなく、2 つの基準でこのベクトルを並べ替えることができます。

template <typename T>
struct Index
{
    typedef typename bool(*Comparator)(const T&, const T&);

    Index(std::vector<T>& _data, Comparator _comp)
        : dataFull(_data)
        , comp(_comp)
    {
        for(unsigned int i = 0; i < dataFull.size(); ++i)
        {
            add(i);
        }
        commit();
    }

    void commit()
    {
        std::sort(references.begin(), references.end(), comp);
    }

    std::vector<std::reference_wrapper<T> >& getReference() {return references;}

protected:

    void add(int index)
    {
        assert(index < dataFull.size());
        references.push_back(std::ref(dataFull[index]));
    }

protected:
    std::vector<T>& dataFull;
    std::vector<std::reference_wrapper<T> > references;
    Comparator comp;
};

int main()
{
    struct ComplexData
    {
        int field1;
        int field2;
    };

    // Generate vector
    const int size = 10;
    std::vector<ComplexData> data;
    data.resize(size);
    for(unsigned int i = 0; i < size; ++i)
    {
        ComplexData& c = data[i];
        c.field1 = i;
        c.field2 = size - i;
    }

    // Vector reordered without touch original
    std::cout << "Vector data, ordered by field1" << std::endl;
    {
        Index<ComplexData> f_1(data, 
            [](const ComplexData& a, const ComplexData& b){return a.field1 < b.field1;});
        auto it = f_1.getReference().begin();
        auto ite = f_1.getReference().end();
        for(; it != ite; ++it)
        {
            std::cout << "-> " << it->get().field1 << " - " << it->get().field2 << std::endl;
        }
    }

    // Vector reordered without touch original
    std::cout << "Vector data, ordered by field2" << std::endl;
    {
        Index<ComplexData> f_2(data, 
            [](const ComplexData& a, const ComplexData& b){return a.field2 < b.field2;});
        auto it = f_2.getReference().begin();
        auto ite = f_2.getReference().end();
        for(; it != ite; ++it)
        {
            std::cout << "-> " << it->get().field1 << " - " << it->get().field2 << std::endl;
        }
    }

    return 0;
}
于 2013-07-21T14:00:01.897 に答える