私は範囲ライブラリを具体化し、範囲サポートを標準に組み込むための提案を書くことに懸命に取り組んできました。その提案は、基本的な範囲の概念である Iterable を説明しています。 Iterable std::begin()
に渡すことができるもの そして std::end()
Iterator/Sentinel ペアを取得します。センチネルは、今年初めにここで説明したように、Iterable の概念が反復子ペア以外の他の種類の範囲を効率的に記述することを可能にします。
Iterable の概念で効率的にモデル化できるようにしたい 3 つのタイプの範囲は次のとおりです。
<オール>Iterator/Sentinel の抽象化により、アルゴリズムはこれら 3 つのケースを統一された構文で処理できるようになります。ただし、Sean Parent がここで指摘したように、3 番目のオプションは、いくつかのアルゴリズムを最適に効率化しようとするときに課題を提示します。 2 月に Sean が批判を申し出たとき、私はそのデザインを正当化するブログ投稿でフォローアップすることを約束しました。これがその投稿です。
注 1: 2 月の投稿以降、用語を変更しました。これらの投稿では、Iterable begin
の範囲を表します と end
さまざまなタイプがあり、Range それらが同じである Iterable です。私の現在の提案では、Iterable ほぼ以前と同じですが、範囲 要素を所有しない Iterable になりました。
注 2: この投稿では、まだ採用されていない Concepts Lite の構文を使用しています。この投稿のすべては、ここで説明する Concepts Lite エミュレーション用のライブラリを使用して C++11 で実装できます。
カウントされた範囲
位置と要素の数を指定することによって形成されるカウントされた範囲には、反復子があります — すべての Iterable がそうであるように。カウントされた範囲の反復子は、範囲の範囲と、範囲に到達するまでの距離を認識している必要があります。したがって、カウントされた範囲のイテレータは、基になるシーケンスへのイテレータとカウント (最後までのカウントまたは先頭からのカウント) の両方を格納する必要があります。考えられるデザインの 1 つを次に示します。
class counted_sentinel {}; template<WeakIterator I> class counted_iterator { I it_; DistanceType<I> n_; // distance to end public: // ... constructors... using iterator_category = typename iterator_traits<I>::iterator_category; decltype(auto) operator*() const { return *it_; } counted_iterator & operator++() { ++it_; --n_; return *this; } friend bool operator==(counted_iterator const & it, counted_sentinel) { return it.n_ == 0; } // ... other operators... }; template<WeakIterator I> class counted_range { I begin_; DistanceType<I> count_; public: // ... constructors ... counted_iterator<I> begin() const { return {begin_, count_}; } counted_sentinel end() const { return {}; } };
上記のコードには注目すべき点がいくつかあります。まず、counted_iterator
イテレータとカウントをバンドルします。すぐに、カウントされたイテレータをコピーするとコストが高くなり、イテレータが頻繁にコピーされることがわかります。緩和要因は、センチネルが空であることです。 counted_iterator
を渡す そして counted_sentinel
イテレータとカウントを渡すのと同じ量のデータをアルゴリズムにコピーします。別々に渡された場合、コンパイラーはおそらくそれらをレジスターに適合させるのがより簡単になりますが、一部の最新のコンパイラーは構造体のメンバーをレジスターに渡すことができます。このコンパイラの最適化は、集計のスカラー置換と呼ばれることもあります
1、2
gcc と LLVM で実装されていることが知られています (たとえば、この最近の LLVM コミットを参照してください)。
また、カウントされたイテレータをインクリメントするのはコストがかかります。基礎となるイテレータをインクリメントし、内部カウントをデクリメントする必要があります。これが潜在的にコストがかかる理由を理解するには、counted_iterator<list<int>::iterator>
を渡す簡単なケースを考えてみてください。 advance
へ .カウントされた反復子の型は双方向で、advance
n インクリメントする必要があります 回:
template<BidirectionalIterator I> void advance(I & i, DistanceType<I> n) { if(n >= 0) for(; n != 0; --n) ++i; else for(; n != 0; ++n) --i; }
++i
ごとに または --i
こちら、2 I
のときに増分または減分が発生しています counted_iterator
です .これは準最適です。 counted_iterator
のより良い実装 です:
template<BidirectionalIterator I> void advance(counted_iterator<I> & i, DistanceType<I> n) { i.n_ -= n; advance(i.it_, n); }
これは、生成されたコードに顕著な影響を与えます。結局のところ、advance
counted_iterator
の特別な処理が行われている標準ライブラリの比較的数少ない場所の 1 つです。 有利です。アルゴリズムをいくつか調べて、その理由を見てみましょう。
カウントされた反復子を使用したシングルパス アルゴリズム
まず、for_each
のような単純なアルゴリズムを見てみましょう 入力シーケンスを 1 回だけ通過する:
template<InputIterator I, Regular S, Function<ValueType<I>> F> requires EqualityComparable<I, S> I for_each(I first, S last, F f) { for(; first != last; ++first) f(*first); return first; }
カウントされた反復子が渡されると、ループの反復ごとに、インクリメント、デクリメント (基になるイテレータとカウント)、および比較が行われます。これを架空の for_each_n
と比較してみましょう 基礎となる反復子とカウントを別々に取るアルゴリズム。次のようになります:
template<InputIterator I, Function<ValueType<I>> F> I for_each_n(I first, DifferenceType<I> n, F f) { for(; n != 0; ++first, --n) f(*first); return first; }
架空の for_each_n
の場合 、各ループ反復で、インクリメント、デクリメント、および比較を行います。それはちょうど for_each
と同じ数の操作です カウントされたイテレータが渡されたときに行います。別の for_each_n
センチネルと counted_iterator
がある場合、アルゴリズムはおそらく不要です 秒。これは、入力範囲を 1 回だけ通過するアルゴリズムに当てはまります。それは多くのアルゴリズムであることが判明しました.
カウントされたイテレータを使用したマルチパス アルゴリズム
入力シーケンスを複数回通過させるアルゴリズムは他にもあります。ただし、それらのほとんどは advance
を使用します イテレータを複数のホップで移動する必要がある場合。 advance
を特化したら counted_iterator
の場合 、advance
を使用するアルゴリズム 余分な作業なしで高速化。
partition_point
を検討してください .以下は、libc++ から取得され、Concepts Lite およびセンチネルに移植された 1 つの実装例です:
template<ForwardIterator I, Regular S, Predicate<ValueType<I>> P> requires EqualityComparable<I, S> I partition_point(I first, S last, P pred) { DifferenceType<I> len = distance(first, last); while (len != 0) { DifferenceType<I> l2 = len / 2; I m = first; advance(m, l2); if (pred(*m)) { first = ++m; len -= l2 + 1; } else len = l2; } return first; }
I
を想像してみてください フォワード counted_iterator
です と S
counted_sentinel
です .ライブラリが advance
に特化していない場合 、これは確かに非効率的です。毎回 advance
と呼ばれ、無駄な作業が行われています。架空の partition_point_n
と比較してください :
template<ForwardIterator I, Predicate<ValueType<I>> P> I partition_point_n(I first, DifferenceType<I> len, P pred) { while (len != 0) { DifferenceType<I> l2 = len / 2; I m = first; advance(m, l2); if (pred(*m)) { first = ++m; len -= l2 + 1; } else len = l2; } return first; }
最初に気付くのは、partition_point_n
です。 distance
を呼び出す必要はありません !注意すべきより微妙なことは、 partition_point_n
を呼び出すことです 生の反復子とカウントを使用すると、partition_point
への同等の呼び出しよりも約 O(N) の整数デクリメントを節約できます counted_iterator
で s … もちろん、advance
を特殊化している場合を除きます 上記のアルゴリズム。取得したら、O(N) 整数減分を O(log N) 整数減算と交換します。これは大きな改善です。
しかし、distance
への O(N) 呼び出しはどうでしょうか。 ?実際、それは簡単です。それが SizedIteratorRange という概念を導入した理由です。 . counted_iterator
最後までの距離を保存します。 counted_iterator
間の距離は そして counted_sentinel
(または 2 つの counted_iterators
の間) ) は O(1) イテレータのカテゴリに関係なく . SizedIteratorRange の概念は、反復子 I
かどうかをテストします そして歩哨 S
距離を得るために減算することができます。この概念は、その性質上、ランダムアクセス反復子によってモデル化されていますが、カウントされた反復子とそのセンチネルによってもモデル化されています。 distance
アルゴリズムは SizedIteratorRange に特化しているため、カウントされたイテレータの場合は O(1) です。
これらの変更により、partition_point
が表示されます。 カウントされたイテレータを使用すると、仮想の partition_point_n
とほぼ同じくらい効率的です 特別な配慮をする必要はありませんでした。 partition_point
を作成できない理由 正確に partition_point_n
と同じくらい効率的 ? partition_point
の場合 カウントされたイテレータで呼び出された場合、も返されます カウントされたイテレータ。カウントされた反復子には、位置と最後までの距離の 2 つのデータムが含まれます。しかし partition_point_n
の場合 位置のみを返しますが、実際には計算して返す情報は少なくなります。ユーザーが追加情報を必要としない場合もあります。しかし、時々 partition_point_n
を呼び出した後 、ユーザーは結果の反復子を別のアルゴリズムに渡したい場合があります。 もし アルゴリズムは distance
を呼び出します (partition_point
のように および他のアルゴリズムが行う)、O(N) になります。ただし、カウントされたイテレータでは O(1) です。 partition_point
の場合 、カウントされた反復子により、アルゴリズムは O(log N) 余分な作業を行いますが、後で O(N) 作業を節約できる場合があります。
例を見るには、些細な insertion_sort
を想像してください アルゴリズム:
template<ForwardIterator I, Regular S> requires EqualityComparable<I, S> && Sortable<I> // from N3351 void insertion_sort(I begin, S end) { for(auto it = begin; it != end; ++it) { auto insertion = upper_bound(begin, it, *it); rotate(insertion, it, next(it)); } }
I
を想像してみてください counted_iterator
です .まず upper_bound
distance
を呼び出します . distance
を作る counted_iterator
の場合は O(1) ■ O(N) アルゴリズムの N 回の呼び出しを保存します。現在の STL で同等の手順で同等のパフォーマンスを得るには、ユーザーは別の insertion_sort_n
を記述する必要があります。 upper_bound_n
にディスパッチするアルゴリズム アルゴリズム — 彼らも自分で書く必要があります.
カウント イテレータを使用したカウント アルゴリズム
カウントされたイテレータを使用した通常のアルゴリズムは、専用のカウントされたアルゴリズムとほぼ同じくらい効率的であり、わずかなパフォーマンスの低下を補う以上の効果があることがわかりました。ただし、すべてがバラではありません。多くの カウント アルゴリズム があります 標準 (名前が _n
で終わるアルゴリズム) )。 copy_n
を検討してください :
template<WeakInputIterator I, WeakOutputIterator<ValueType<I>> O> pair<I, O> copy_n(I in, DifferenceType<I> n, O out) { for(; n != 0; ++in, ++out, --n) *out = *in; return {in, out}; }
(copy_n
の戻り値の型を変更しました 情報を失わないように。) If I
++in
ごとに数えられる反復子です。 、インクリメントとデクリメントが発生しています。この場合、余分なデクリメントはまったく不要です。 すべての カウント (つまり、_n
) アルゴリズムでは、カウントされた反復子を渡したときにパフォーマンスが低下しないようにするために、何か特別なことを行う必要があります。
ここでアルゴリズムの作成者には 2 つのオプションがあり、どちらも理想的ではありません。
オプション 1:アルゴリズムをオーバーロードする
以下は copy_n
の最適化バージョンです カウントされた反復子:
template<WeakInputIterator I, WeakOutputIterator<ValueType<I>> O> pair<I, O> copy_n(counted_iterator<I> in, DifferenceType<I> n, O out) { for(auto m = in.n_ - n; in.n_ != m; ++in.i_, --in.n_, ++out) *out = *in; return {in, out}; }
明らかに、カウントされた反復子のオーバーロードを作成することは満足のいくものではありません。
オプション 2:イテレータをカウントから分離する
このオプションは、ライブラリの実装者が copy_n
の 1 つのバージョンだけを作成する方法を示しています。 カウントされたイテレータ用に自動的に最適化されます。まず、カウントされたイテレータをアンパックおよびリパックするための 2 つのユーティリティ関数を提供する必要があります:
template<WeakIterator I> I uncounted(I i) { return i; } template<WeakIterator I> I uncounted(counted_iterator<I> i) { return i.it_; } template<WeakIterator I> I recounted(I const &, I i, DifferenceType<I>) { return i; } template<WeakIterator I> counted_iterator<I> recounted(counted_iterator<I> const &j, I i, DifferenceType<I> n) { return {i, j.n_ - n}; }
uncounted
の助けを借りて と recounted
、最適化された copy_n
を書くことができます 一度だけ:
template<WeakInputIterator I, WeakOutputIterator<ValueType<I>> O> pair<I, O> copy_n(I in_, DifferenceType<I> n_, O out) { auto in = uncounted(in_); for(auto n = n_; n != 0; ++in, --n, ++out) *out = *in; return {recounted(in_, in, n_), out}; }
このバージョンは、カウントされるイテレータとカウントされないイテレータの両方で最適に機能します。しかし、それは美しいものではありません。 uncounted
しなければならないのは少し面倒です。 /recounted
しかし、それは主にカウントされたアルゴリズムでのみ必要です.
最後の注意として、advance
のオーバーロード カウントされたイテレータは uncounted
の助けを借りて排除できます と recounted
.結局、advance
カウントアルゴリズムです。
ベンチマーク:挿入ソート
カウント範囲とカウント イテレータのコストをテストするために、ベンチマークを作成しました。ベンチマーク ピットは、専用の _n
に対して範囲をカウントしました 挿入ソートのアルゴリズム。プログラムはこの要旨に記載されています。
プログラムは insertion_sort_n
の両方を実装しています 、専用のカウント アルゴリズム、および insertion_sort
は、カウントされた範囲を渡す任意の Iterable を受け入れる一般的なアルゴリズムです。後者は、汎用 upper_bound
の観点から実装されています Range v3 ライブラリによって提供されるように、前者には専用の upper_bound_n
が必要です アルゴリズムも提供されています。
このテストは、生のポインター (したがって、ランダム アクセス) と、ForwardIterator のみをモデル化するイテレーター ラッパーの両方を使用して実行されます。各テストは 3 回実行され、結果の時間は平均されます。テストは g++
でコンパイルされました -O3 -std=gnu++11 -DNDEBUG
のバージョン 4.9.0 Linux マシンで実行します。 N ==30,000 の場合の結果を以下に報告します:
insertion_sort_n | insertion_sort | |
---|---|---|
ランダムアクセス | 2.692 秒 | 2.703 秒 |
フォワード | 23.853 秒 | 23.817 秒 |
パフォーマンスの違いがあったとしても、ノイズの中で失われます。少なくともこの場合、このコンパイラ、このハードウェアでは、専用の _n
のパフォーマンスを正当化する理由はありません。
まとめ
要するに、カウントされたイテレータは完璧ではありません 抽象化。ここには前例があります。 deque
の反復子 、およびセグメント化されたデータ構造に対しては、非効率的であることが知られています (Segmented Iterators and Hierarchical Algorithms、Austern 1998 を参照)。その問題の修正、新しい反復子の抽象化と個別の階層アルゴリズムの実装は侵襲的であり、私が知っている STL 実装では試みられていません。それに比べて、カウントされた反復子に伴う追加の複雑さは非常に小さいように見えます。セグメント化された反復子の利点は、反復子の抽象化の単純さと統一性です。カウントされた範囲と反復子の場合、利点は反復可能な概念の単純さと統一性です。アルゴリズムに必要な形式は 1 つだけであり、境界付き、カウント済み、およびセンチネル形式を分離する必要はありません。ベンチマークは、統一的な抽象化のためにパフォーマンスを犠牲にしすぎていないという合理的な保証を与えてくれます.
"\e"
"\e"