2

これが良い質問かどうかわかりませんが、そうでない場合は閉じてください。

ベクトルに似たインターフェイスを効率的に実装するテンプレート クラスを(boost::coordinate_vector出発点として使用して) 書き始めましたが、スパースです。sparse_vector通常のすべてのベクトル操作と、セット要素を反復処理する高速スパース反復子を実装します。の高速バージョンもありrotateます。このクラスが必要なのは、write-once-read-many のユース ケースがあり、これらの多くを使用しているためsparse_vectorsです。

私はテンプレート クラスを書いた経験がないので、改善できる点があることはわかっています。このクラスを改善するにはどうすればよいですか?

// sparse_vector is a sparse version of std::vector.  It stores index-value pairs, and a size, which
// represents the size of the sparse_vector.

#include <algorithm>
#include <ostream>
#include <iostream>
#include <vector>
#include <boost/iterator.hpp>
#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/iterator/reverse_iterator.hpp>
#include <boost/optional.hpp>
#include <glog/logging.h>

template<typename T>
class sparse_vector {
public:
    typedef T value_type;
    typedef T* pointer;
    typedef T& reference;
    typedef const T& const_reference;
    typedef size_t size_type;
private:
    struct ElementType {
        ElementType(size_type i, T const& t): index(i), value(t) {}
        ElementType(size_type i, T&& t): index(i), value(move(t)) {}
        ElementType(size_type i): index(i) {}  // allows lower_bound to work
        ElementType(ElementType const&) = default;
        size_type index;
        value_type value;
    };
    typedef std::vector<ElementType> array_type;
public:
    typedef typename array_type::difference_type difference_type;

private:
    typedef const T* const_pointer;
    typedef sparse_vector<T> self_type;
    typedef typename array_type::const_iterator const_subiterator_type;
    typedef typename array_type::iterator subiterator_type;

    struct IndexCompare {
        bool operator()(ElementType const& a, ElementType const& b) { return a.index < b.index; }
    };

public:
    // Construction and destruction
    inline sparse_vector(): size_(0), sorted_filled_(0), data_() {
            storage_invariants(); }
    explicit inline sparse_vector(size_type size): size_(size), sorted_filled_(0), data_() {
            storage_invariants(); }
    inline sparse_vector(const sparse_vector<T> &v):
        size_(v.size_), sorted_filled_(v.sorted_filled_), data_(v.data_) {
            storage_invariants(); }
    inline sparse_vector(sparse_vector<T>&& v):
        size_(v.size_), sorted_filled_(v.sorted_filled_), data_(move(v.data_)) {
            storage_invariants(); }
    sparse_vector(const optional<T> &o): size_(1), sorted_filled_(0) {
            if (o) {
                append_element(0, *o);
                sorted_filled_ = 1;
            }
            storage_invariants();
        }
    sparse_vector(const std::vector<T> &v):
        size_(v.size()), sorted_filled_(0) {
            data_.reserve(v.size());
            for (auto it = v.begin(); it != v.end(); ++it)
                append_element(it - v.begin(), *it);
            sorted_filled_ = v.size();
            storage_invariants();
        }
    sparse_vector(const sparse_vector<optional<T>> &sv):
        size_(sv.size()), sorted_filled_(0) {
            for (auto it = sv.sparse_begin(); it != sv.sparse_end(); ++it)
                if (*it)
                    append_element(it.index(), **it);
            sorted_filled_ = data_.size();
            storage_invariants();
        }
    sparse_vector(size_type size, vector<pair<size_type, T>> init_list):
        size_(size), sorted_filled_(0) {
            for (auto it = init_list.begin(); it != init_list.end(); ++it)
                append_element(it->first, it->second);
            // require that the list be sorted?
            // sorted_filled_ = data_.size();
            storage_invariants();
        }
    /*template<class AE>
        inline sparse_vector(const sparse_vector<AE> &ae):
            size_(ae().size()), sorted_filled_(ae.nnz()), data_() {
                storage_invariants();
                for (auto it = ae.sparse_begin(); it != ae.sparse_end(); ++it) {
                    (*this)[it.index()] = static_cast<T>(*it);
                }
            }*/

    // Conversion operators
    // Copy sparse_vector to a vector filling in uninitialized elements with T()
    operator std::vector<T>() {
        std::vector<T> retval(size_);
        for (auto it = data_.begin(); it != data_.end(); ++it)
            retval[it.index()] = *it;
        return retval; 
    }
    // Copy sparse_vector to a vector filling in uninitialized elements with a default value.
    void CopyToVector(std::vector<T>* v, T const& default_value = T()) {
        size_type last_index = 0;
        for (auto it = sparse_begin(); it != sparse_end(); ++it) {
            for (size_type i = last_index; i < it.index(); ++i) {
                (*v)[i] = default_value;
            }
            (*v)[it.index()] = *it;
            last_index = it.index() + 1;
        }
    }

    // Accessors
    inline size_type size() const {
        return size_;
    }
    inline size_type nnz_capacity() const {
        return data_.capacity();
    }
    inline size_type nnz() const {
        return data_.size();
    }

    // Resizing
    inline void resize(size_type size, bool preserve = true) {
        if (preserve) {
            sort();    // remove duplicate elements.
            subiterator_type it(lower_bound(data_.begin(), data_.end(), size, IndexCompare()));
            data_.erase(it, data_.end());
        } else {
            data_.clear();
        }
        size_ = size;
        sorted_filled_ = nnz();
        storage_invariants();
    }

    // Reserving
    inline void reserve(size_type non_zeros, bool preserve = true) {
        if (preserve)
            sort();    // remove duplicate elements.
        else
            data_.clear();
        data_.reserve(non_zeros);
        sorted_filled_ = nnz();
        storage_invariants();
    }

    // Element support
    // find_element returns a pointer to element i or NULL -- it never creates an element
    inline pointer find_element(size_type i) {
        return const_cast<pointer> (const_cast<const self_type&>(*this).find_element(i)); }
    inline const_pointer find_element(size_type i) const {
        sort();
        const_subiterator_type it(lower_bound(data_.begin(), data_.end(), i, IndexCompare()));
        if (it == data_.end() || it->index != i)
            return NULL;
        return &it->value;
    }
    // find_element_optional returns a boost::optional<T>
    inline boost::optional<value_type> find_element_optional(size_type i) const {
        CHECK_LT(i, size_);
        sort();
        const_subiterator_type it(lower_bound(data_.begin(), data_.end(), i, IndexCompare()));
        if (it == data_.end() || it->index != i)
            return boost::optional<value_type>();
        return boost::optional<value_type>(it->value);
    }

    // Element access
    // operator[] returns a reference to element i -- the const version returns a reference to
    // a zero_ element if it doesn't exist; the non-const version creates it in that case.
    inline const_reference operator[] (size_type i) const {
        CHECK_LT(i, size_);
        sort();
        const_subiterator_type it(lower_bound(data_.begin(), data_.end(), i, IndexCompare()));
        if (it == data_.end() || it->index != i)
            return zero_;
        return it->value;
    }
    inline reference operator[] (size_type i) {
        CHECK_LT(i, size_);
        sort();
        subiterator_type it(lower_bound(data_.begin(), data_.end(), i, IndexCompare()));
        if (it == data_.end() || it->index != i)
            return insert_element(i, value_type/*zero*/());
        else
            return it->value;
    }

    // Element assignment
    inline void append_element(size_type i, const_reference t) {
        data_.emplace_back(i, t);
        storage_invariants();
    }
    inline void append_element(size_type i, T&& t) {
        data_.emplace_back(i, move(t));
        storage_invariants();
    }
    inline void sorted_append_element(size_type i, const_reference t) {
        // must maintain sort order
        CHECK(sorted());
        if (data_.size() > 0)
            CHECK_LT(data_.back().index, i);
        data_.emplace_back(i, t);
        sorted_filled_ = data_.size();
        storage_invariants();
    }
    /* This function is probably not useful.
     * inline void sparse_pop_back() {
        // ISSUE invariants could be simpilfied if sorted required as precondition
        CHECK_GT(data_.size(), 0);
        data_.pop_back();
        sorted_filled_ = (std::min)(sorted_filled_, data_.size());
        storage_invariants();
    }*/
    inline reference insert_element(size_type i, const_reference t) {
        DCHECK(find_element(i) == NULL);  // duplicate element
        append_element(i, t);
        return data_.back().value;
    }

    // Element clearing
    // TODO(neil): consider replacing size_type functions with iterator functions
    // replaces elements in the range [i, i] with "zero" (by erasing them from the map)
    inline void clear_element(size_type i) {
        sort();
        subiterator_type it(lower_bound(data_.begin(), data_.end(), i, IndexCompare()));
        if (it == data_.end() || it->index != i)
            return;
        data_.erase(it);
        --sorted_filled_;
        storage_invariants();
    }
    // replaces elements in the range [first, last) with "zero" (by erasing them from the map)
    inline void clear_elements(size_type first, size_type last) {
        CHECK_LE(first, last);
        sort();
        subiterator_type it_first(lower_bound(data_.begin(), data_.end(), first, IndexCompare()));
        subiterator_type it_last(lower_bound(data_.begin(), data_.end(), last, IndexCompare()));
        sorted_filled_ -= it_last - it_first;
        data_.erase(it_first, it_last);
        storage_invariants();
    }

    // Zeroing
    inline void clear() { data_.clear(); sorted_filled_ = 0; storage_invariants(); }

    // Comparison
    inline bool operator==(const sparse_vector &v) const {
        if (this == &v)
            return true;
        if (size_ != v.size_)
            return false;
        auto it_this = sparse_begin();
        for (auto it = v.sparse_begin(); it != v.sparse_end(); ++it) {
            if (it_this == sparse_end()
                || it_this.index() != it.index()
                || *it_this != *it)
                return false;
            ++it_this;
        }
        return true;
    }

    // Assignment
    inline sparse_vector& operator=(const sparse_vector &v) {
        if (this != &v) {
            size_ = v.size_;
            sorted_filled_ = v.sorted_filled_;
            data_ = v.data_;
        }
        storage_invariants();
        return *this;
    }
    inline sparse_vector &assign_temporary(sparse_vector &v) {
        swap(v);
        return *this;
    }
    template<class AE>
        inline sparse_vector& operator=(const sparse_vector<AE> &ae) {
            self_type temporary(ae);
            return assign_temporary(temporary);
        }

    // Swapping
    inline void swap(sparse_vector &v) {
        if (this != &v) {
            std::swap(size_, v.size_);
            std::swap(sorted_filled_, v.sorted_filled_);
            data_.swap(v.data_);
        }
        storage_invariants();
    }
    inline friend void swap(sparse_vector &v1, sparse_vector &v2) { v1.swap(v2); }

    // Sorting and summation of duplicates
    inline bool sorted() const { return sorted_filled_ == data_.size(); }
    inline void sort() const {
        if (!sorted() && data_.size() > 0) {
            // sort new elements and merge
            std::sort(data_.begin() + sorted_filled_, data_.end(), IndexCompare());
            std::inplace_merge(data_.begin(), data_.begin() + sorted_filled_, data_.end(),
                               IndexCompare());

            // check for duplicates
            size_type filled = 0;
            for(size_type i = 1; i < data_.size(); ++i) {
                if (data_[filled].index != data_[i].index) {
                    ++filled;
                    if (filled != i) {
                        data_[filled] = data_[i];
                    }
                } else {
                    CHECK(false);  // duplicates
                    // value_data_[filled] += value_data_[i];
                }
            }
            ++filled;
            sorted_filled_ = filled;
            data_.erase(data_.begin() + filled, data_.end());
            storage_invariants();
        }
    }

    // Back element insertion and erasure
    inline void push_back(const_reference t) {
        CHECK(sorted());
        data_.emplace_back(size(), t);
        if (sorted_filled_ == data_.size())
            ++sorted_filled_;
        ++size_;
        storage_invariants();
    }
    inline void pop_back() {
        CHECK_GT(size_, 0);
        clear_element(size_ - 1);
        if (sorted_filled_ == size_)
            --sorted_filled_;
        --size_;
        storage_invariants();
    }

    // Iterator types
private:
    template<typename base_type, typename iterator_value_type>
        class sparse_iterator_private
            : public boost::iterator_adaptor<
              sparse_iterator_private<base_type, iterator_value_type>,  // Derived
              base_type,                                                // Base
              iterator_value_type,                                      // Value
              boost::random_access_traversal_tag                        // CategoryOrTraversal
              > {
        private:
            struct enabler {};  // a private type avoids misuse

        public:
            sparse_iterator_private()
                : sparse_iterator_private<base_type, iterator_value_type>::iterator_adaptor_() {}

            explicit sparse_iterator_private(base_type&& p)
                : sparse_iterator_private<base_type, iterator_value_type>::iterator_adaptor_(p) {}

            size_type index() const { return this->base()->index; }
            iterator_value_type& value() const { return this->base()->value; }

        private:
            friend class boost::iterator_core_access;

            iterator_value_type& dereference() const { return this->base()->value; }
        };

    template<typename container_type, typename iterator_value_type>
        class iterator_private
        : public boost::iterator_facade<
          iterator_private<container_type, iterator_value_type>,    // Derived
          iterator_value_type,                                      // Value
          boost::random_access_traversal_tag,                       // CategoryOrTraversal
          iterator_value_type&,                                     // Reference
          difference_type                                           // Difference
          > {
          private:
              struct enabler {};  // a private type avoids misuse

          public:
              iterator_private(): container_(NULL), index_(0) {}

              iterator_private(container_type* container, size_type index)
                  : container_(container), index_(index) {}

              iterator_private(iterator_private const& other)
                  : container_(other.container_), index_(other.index_) {}

              iterator_private& operator=(iterator_private const& other) {
                  container_ = other.container_;
                  index_ = other.index_;
              }

              container_type& container() const { return *container_; }
              size_type index() const { return index_; }
              iterator_value_type& value() const { return dereference(); }
              /* TODO(neil): how do you make this work?
                 template<typename U>
                 sparse_iterator_private<U> subsequent_sparse_iterator() {
                 return sparse_iterator_private<T>(lower_bound(container_.data_.begin(),
                 container_.data_.end(),
                 index_, IndexCompare()));
                 }
                 */

          private:
              friend class boost::iterator_core_access;
              iterator_value_type& dereference() const { return (*container_)[index_]; }
              bool equal(iterator_private<container_type, iterator_value_type> const& other) const {
                  return index_ == other.index_ && container_ == other.container_; }
              void increment() { ++index_; }
              void decrement() { --index_; }
              void advance(int n) { index_ += n; }
              difference_type distance_to(iterator_private<container_type,
                                          iterator_value_type> const& other) {
                  return index_ - other.index_; }

              container_type*       container_;
              size_type             index_;
          };

public:
    typedef sparse_iterator_private<typename array_type::iterator, value_type> sparse_iterator;
    typedef sparse_iterator_private<
        typename array_type::const_iterator, const value_type> const_sparse_iterator;
    typedef iterator_private<sparse_vector, value_type> iterator;
    typedef iterator_private<const sparse_vector, const value_type> const_iterator;
    typedef boost::reverse_iterator<sparse_iterator> reverse_sparse_iterator;
    typedef boost::reverse_iterator<const_sparse_iterator> const_reverse_sparse_iterator;
    typedef boost::reverse_iterator<iterator> reverse_iterator;
    typedef boost::reverse_iterator<const_iterator> const_reverse_iterator;

    // Element lookup
    // inline This function seems to be big. So we do not let the compiler inline it.    
    sparse_iterator sparse_find(size_type i) {
        sort();
        return sparse_iterator(lower_bound(data_.begin(), data_.end(), i, IndexCompare()));
    }
    // inline This function seems to be big. So we do not let the compiler inline it.    
    const_sparse_iterator sparse_find(size_type i) const {
        sort();
        return const_sparse_iterator(lower_bound(data_.begin(), data_.end(), i, IndexCompare()));
    }
    // the nth non-zero element
    const_sparse_iterator nth_nonzero(size_type i) const {
        CHECK_LE(data_.size(), i);
        sort();
        return const_sparse_iterator(data_.begin() + i);
    }

    // Forward iterators
    inline sparse_iterator sparse_begin() { return sparse_find(0); }
    inline sparse_iterator sparse_end() { return sparse_find(size_); }
    inline const_sparse_iterator sparse_begin() const { return sparse_find(0); }
    inline const_sparse_iterator sparse_end() const { return sparse_find(size_); }
    inline iterator begin() { return iterator(this, 0); }
    inline iterator end() { return iterator(this, size()); }
    inline const_iterator begin() const { return const_iterator(this, 0); }
    inline const_iterator end() const { return const_iterator(this, size()); }

    // Reverse iterators
    inline reverse_sparse_iterator sparse_rbegin() {
        return reverse_sparse_iterator(sparse_end()); }
    inline reverse_sparse_iterator sparse_rend() {
        return reverse_sparse_iterator(sparse_begin()); }
    inline const_reverse_sparse_iterator sparse_rbegin() const {
        return const_reverse_sparse_iterator(sparse_end()); }
    inline const_reverse_sparse_iterator sparse_rend() const {
        return const_reverse_sparse_iterator(sparse_begin()); }
    inline reverse_iterator rbegin() {
        return reverse_iterator(end()); }
    inline reverse_iterator rend() {
        return reverse_iterator(begin()); }
    inline const_reverse_iterator rbegin() const {
        return const_reverse_iterator(end()); }
    inline const_reverse_iterator rend() const {
        return const_reverse_iterator(begin()); }

    // Mutating algorithms
    // like vector::erase (erases the elements from the container and shrinks the container)
    inline void erase(iterator const& first, iterator const& last) {
        clear_elements(first.index(), last.index());
        CHECK(sorted());
        subiterator_type it_first(lower_bound(data_.begin(), data_.end(),
                                              first.index(), IndexCompare()));
        size_t n = last.index() - first.index();
        for (auto it = it_first; it != data_.end(); ++it)
            it->index -= n;
        size_ -= n;
    }

    // like vector::insert (insert elements into the container and causes the container to grow)
    inline void insert(iterator const& index, size_type n) {
        sort();
        subiterator_type it_first(lower_bound(data_.begin(), data_.end(),
                                              index.index(), IndexCompare()));
        for (auto it = it_first; it != data_.end(); ++it)
            it->index += n;
        size_ += n;
    }

    // Removes all "zero" elements
    void remove_zeros() {
        size_type filled = 0;
        for(size_type i = 0; i < data_.size(); ++i) {
            if (i == sorted_filled_) {
                // Once we've processed sorted_filled_ items, we know that whatever we've filled so
                // far is sorted.
                CHECK_LE(filled, sorted_filled_);
                // Since sorted_filled_ only shrinks here, and i only grows, we won't enter this
                // condition twice.
                sorted_filled_ = filled;
            }
            if (data_[i].value != value_type/*zero*/()) {
                if (filled != i) {
                    data_[filled] = data_[i];
                }
                ++filled;
            }
        }
        data_.erase(data_.begin() + filled, data_.end());
        storage_invariants();
    }

    void rotate(size_type first, size_type middle, size_type last) {
        CHECK_LT(first, middle);
        CHECK_LT(middle, last);
        sort();
        subiterator_type it_first(lower_bound(data_.begin(), data_.end(),
                                              first, IndexCompare()));
        subiterator_type it_middle(lower_bound(data_.begin(), data_.end(),
                                               middle, IndexCompare()));
        subiterator_type it_last(lower_bound(data_.begin(), data_.end(),
                                             last, IndexCompare()));

        for (auto it = it_first; it != it_middle; ++it)
            it->index += last - middle;
        for (auto it = it_middle; it != it_last; ++it)
            it->index -= middle - first;
        std::rotate(it_first, it_middle, it_last);
        // array remains sorted
    }

    sparse_vector<value_type> concatenate(sparse_vector<value_type> const& other) const {
        sparse_vector<value_type> retval(size() + other.size());
        for (auto it = sparse_begin(); it != sparse_end(); ++it) {
            retval[it.index()] = *it;
        }
        for (auto it = other.sparse_begin(); it != other.sparse_end(); ++it) {
            retval[it.index() + size()] = *it;
        }
        return retval;
    }

private:
    void storage_invariants() const {
        CHECK_LE(sorted_filled_, data_.size());
        if (sorted())
            CHECK_EQ(sorted_filled_, data_.size());
        else
            CHECK_LT(sorted_filled_, data_.size());
        if (!data_.empty())
            CHECK_LT(data_.back().index, size_);
        for (size_type i = 1; i < sorted_filled_; ++i)
            CHECK_GT(data_[i].index, data_[i - 1].index);
    }

    size_type                                   size_;
    mutable typename array_type::size_type      sorted_filled_; 
    mutable array_type                          data_;

    static const value_type                     zero_;
};

template<typename T>
const typename sparse_vector<T>::value_type sparse_vector<T>::zero_ = T();

template<typename T>
ostream& operator<<(ostream& os, const sparse_vector<T>& v) {
    os << "[" << v.size() << ": ";
    for (auto it = v.sparse_begin(); it != v.sparse_end(); ++it) {
        os << "(" << it.index() << ": " << it.value() << ") ";
    }
    return os << "]";
}
4

1 に答える 1

4

クラス テンプレートを書いた経験がほとんどない人にとっては、かなり洗練されたものを作成したことになります。残念ながら、現時点では詳細な分析を行うことはできません。表示されるコードの量と質問の一般性を考えると、時間がかかりすぎます。概要について簡単にしかお答えできません。

まず、operator[] const メソッドと begin/end メソッドで変更可能なデータをソートするのはちょっと怖いです。このクラスは、同時読み取りアクセスの場合でもスレッドセーフではありません。複数のスレッドを処理することは、おそらくこのクラスの範囲を超えていますが、この動作は非常に特殊であるため、クラスが非常に汎用的な使用を意図している場合は、おそらく十分に文書化する必要があります.

もう 1 つの方法は、クライアントがベクトルを明示的にソートすることを要求し、これが完了するまで線形アクセス メソッドを使用してデータをフェッチすることです。これはソリューションほど自動化されたものではありませんが、スレッド間で読み取り目的でクラスを安全に使用できるようになります。

また、プロファイラーを使用してこのコードをインライン化していないことも明らかです。プロファイラーの助けなしにこれをしないでください。私はここで一般論を吐き出しているだけではありません。私は仕事の一環として vtune とパラレル スタジオでレイトレーサーとプロファイル コードを日常的に使用しており、このようなインライン コードはパフォーマンスに悪影響を及ぼします。最も明白なケースはコードの肥大化によるものですが、ほとんどの人が見落としているように見える、あまり目立たない 2 つ目のケースがあります。

単一行のアクセサーのようなものでも、それらをすべてインライン化すると、レジスターやその他の最適化を最大限に活用するオプティマイザーの機能が妨げられます。最適化コンパイラは、小さく適切に作成された関数を使用して、関数ごとに最適に機能します。それらは通常、関数間レベルではうまく機能しません。すべてをインライン化し始めると、結果は、ICC (Intel の最適化コンパイラ) でさえ行わない、あらゆる種類のデータにアクセスする 1 つの大きなフラットな関数に似ています。対処する素晴らしい仕事。まず、コンパイラはあなたの心を読むことができないため、すべてをインライン化すると、実行頻度の低いブランチと実行頻度の高いブランチが等しく最適化されます (基本的に、一般的なブランチを最適化するコンパイラの機能が損なわれます)。

プロファイラーを使用すると、これらのより一般的に実行されるブランチを確認し、それらを選択的にインライン化できますが、インライン化から始めることはありません。実際、開始時にほとんどすべてをインライン化することで、コードをプロファイリングする能力に大混乱をもたらすでしょう。

パブリック インターフェイスに関しては、これの全体的なポイントは、連続性を実装し、メモリとアクセス時間を短縮することであることがわかります (バックエンドに std::vector を使用)。ただし、その性質を考えると、インターフェイスを提供する方がよいと思います。に似ていmap<int, T>ます。たとえば、push_back と pop_back の動作はやや混乱します。挿入メソッドと消去メソッドのみと、新しいインデックス (キー) を作成できる非 const operator[] を使用する代替案を検討するか、少なくとも最初のステップとしてこれを実行します。割り当てられる利用可能なインデックスを選択してそれを返す const_reference のみを取る挿入メソッドを提供できます（ギャップを気にしない場合は size() - 1 にすることができます）。

実装の観点からは、コードは単純に見えます。コードを「インライン展開」する以外に提案することはあまりありません。

速度がこれを作成する動機の 1 つであるように思われるため、ここに小さなヒントを示します。それ以外の：

inline void sort() const {
    if (!sorted() && data_.size() > 0) {
        ...
}

その最初の「if」を取り除くことを検討し、この関数をインライン化しないでください。クラス定義の外に置きます。あらゆる種類の読み取り専用アクセスの場合にソートを使用しますが、これは例外的なケースです。ほとんどの読み取りアクセスは、既にソートされたデータに対して操作する必要があります。このような例外的なケースがある場合、関数がインライン化されておらず、チェックを外部に置くと、最適化コンパイラは通常、はるかに優れた仕事をします。

inline const_reference operator[] (size_type i) const {
    CHECK_LT(i, size_);
    if (need_sort() )
        sort();
    ...
}

プロファイラーを使用して日常的にマイクロ最適化を行った結果、GCC、ICC、および MSVC の最新バージョンを含むほとんどの最適化コンパイラーで一般的に高速になることを保証できます。大まかに言えば、その理由は、あなたの operator[] 関数がより少ないことを行い、結果としてより少ないメモリにアクセスするためです (例外的な状況でのみ実行されるべきである処理するインラインソートはありません)。

最も重要なことは、プロファイラーを入手していくつかのテストを行い、ボトルネックがどこにあるかを確認することをお勧めします.

于 2010-06-27T04:39:43.503 に答える