問題タブ [lower-bound]

C++ドラフトはstd::lower_boundについて述べています：

これにより、（含意によって）*ForwardIterator返されるものとは異なる（しかし比較可能な）タイプを比較できますが、イテレーターの進歩の数に複雑さの制限はありません。（ノードベースのコンテナの場合、これはO（最後-最初）のイテレータの進歩になります。）

標準ではこれらの関数について詳しく説明していませんが、これらはO（log2（last − first））の比較と進歩のためのものであることが暗示されていますが、検索キーは含まれているタイプと同じである必要があります。

だから私の質問は次のとおりです：
（1）検索タイプの速度std::set::lower_boundと柔軟性を取得する方法はありstd::lower_boundますか？
（2）なぜstd::lower_bound専門化する必要がないのですstd::set::iteratorか？
（3）に特化した実装std::lower_bound はstd::set::iteratorありますか、それとも理由はありますか？

私は次のようなものを見つけたいと思っていました：

また：

しかし、私はそれが存在することを疑っています。明らかに、これらすべてを他のツリーベースのコンテナや他のアルゴリズムに拡張できます。自分でコーディングしますが、実装固有のコードを使用する必要があります。このアイデアは、この質問から生まれました。非キータイプのセットでの効果的な検索

scala の継承と下限に問題があります。例を挙げて説明します: 次のような署名を持つクラス Person があります。

子クラス Worker も作成しました。そのメソッド doSomething は次のようになります。

ただし、これはエラーを発生させ、Worker.doSomething() は何もオーバーライドしないことを示していますか?

Scott Meyersによる効果的なSTL（195ページ）には、次の行があります。

「lower_boundの結果は、探している値を指しているかどうかを確認するためにテストする必要があります。findとは異なり、終了イテレータに対してlower_boundの戻り値をテストすることはできません。」

なぜあなたがこれを行うことができないのか誰かが説明できますか？私にとってはうまくいくようです。

比較モデルに基づくソートアルゴリズムには、nlogn、つまり Omega(nlogn) の下限があることがわかっています。数学的に証明できること。

しかし、ご存知のように、オランダの旗の問題は 3 つの異なる要素 (繰り返し使用される) を O(n) 時間でソートできます。これも比較モデルに基づいていますが、O(n) 時間でソートできます。では、比較モデルに基づいてソートの下限を正当化するにはどうすればよいでしょうか。

違いを理解するのを手伝ってください.....

ありがとう

誰かがこの問題の解決策を私に説明できますか？

ソートするn個の要素のシーケンスが与えられたとします。入力シーケンスは、それぞれがk個の要素を含むn=k個のサブシーケンスで構成されます。特定のサブシーケンスの要素はすべて、後続のサブシーケンスの要素よりも小さく、前のサブシーケンスの要素よりも大きくなります。したがって、長さnのシーケンス全体をソートするために必要なのは、 n=k個のサブシーケンスのそれぞれでk個の要素をソートすることだけ です。ソート問題のこの変形を解決するために必要な比較の数のnlgk下限を示します。

解決：

Sを、それぞれ長さkのn / k個のサブシーケンスに分割されたn個の要素のシーケンスとし ます。ここで、任意のサブシーケンスのすべての要素は、先行するサブシーケンスのすべての要素よりも大きく、後続のサブシーケンスのすべての要素よりも小さくなります。

請求

Sをソートするための比較ベースのソートアルゴリズムは、最悪の場合（n lg k）の時間がかかる必要があります。

証拠

ヒントで指摘されているように、各サブシーケンスをソートするための下限を乗算しても下限を証明できないことに最初に注意してください。これは、サブシーケンスを独立してソートするより高速なアルゴリズムがないことを証明するだけです。これは私たちが証明するように求められたものではありませんでした。追加の仮定を導入することはできません。

ここで、Sの比較ソートの高さhの決定木を検討します。各サブシーケンスの要素は任意の順序である可能性があるため、k！順列は、サブシーケンスの最終的なソート順に対応します。また、そのようなサブシーケンスはn / k個あり、それぞれの順序は任意であるため、入力順序の並べ替えに対応できるSの（k！）^ n/k順列があります。したがって、Sをソートするための決定木には、少なくとも（k！）^ n/kの葉が必要です。高さhの二分木は2^hの葉 しか持たないため、 2 ^ h≥（k！）^（n / k）またはh≥lg（（k！）^ n / k）でなければなりません。したがって、

3行目はkから来ています！k/2の最大項はそれぞれ少なくともk/2です。（ここでは、kが偶数であると暗黙的に想定しています。kが奇数の場合は、床と天井で調整できます。）

少なくとも（n / 2）lg（k / 2）の長さのSをソートするための決定木には少なくとも1つのパスが存在するため、Sの比較ベースのソートアルゴリズムの最悪の場合の実行時間は（n lg k）。

誰かがコードブロックの手順を教えてもらえますか？特にlgkのときのステップ！lg（（k / 2）^ k / 2）になります。

私はC++で次のコードスニペットに出くわしました（私はまだC ++ 11を使用していません）：

特に、最後の使用やと--itrの比較は好きではありません。どちらも私には違和感を覚えます。itrbegin()

valueSTLを使用して、見つからない場合はend（）（またはrend（））を返すようなルックアップを実行し、そうでない場合はコード以下の最後の要素を返す方法があるかどうか疑問に思っています。このようになります：

valueある意味で、またはが見つからない場合はrend（）以下の最後の要素に逆イテレータを返すreverse_lower_bound（）が必要です。

二分探索を使用する関数はありますが、特定の述語に従って最後の項目以下lower_boundを返しますか?

lower_boundは次のように定義されています。

順序付けられた範囲内で、指定された値以上の値を持つ最初の要素の位置を検索します。順序付け基準はバイナリ述語で指定できます。

とupper_bound:

順序付けられた範囲内で、指定された値より大きい値を持つ最初の要素の位置を検索します。順序付け基準はバイナリ述語で指定できます。

具体的には、時間順のイベントのコンテナーがあり、特定の時間について、その時点またはその前に発生した最後のアイテムを見つけたいと考えています。上限/下限、逆反復子、および or を使用してこれを実現できますstd::greaterかstd::greater_equal?

編集:配列の開始前にポイントを要求する場合に対処するために、user763305 の提案に微調整が必​​要でした:

このページhttp://www.scala-lang.org/node/137を読んでいますが、共分散とは何か、下限も理解していますが、明確ではないのは次の行です。

残念ながら、このプログラムはコンパイルされません。共分散アノテーションは、型変数が共分散位置でのみ使用されている場合にのみ可能であるためです。型変数Tはメソッドprependのパラメーター型として表示されるため、このルールは破られます。

なぜelemスーパータイプのインスタンスである必要があるのか​​、すでに共変Tである場合は、なぜ現在のリストの前に追加できないのか。ListNodeelem

私は次のことをしたいと思います：

つまり、 の不変リストが与えられたT場合、 リストに anyUを追加して の不変リストを生成でき、 のスーパータイプでなければならないUという制約があります。例えばUT

• サルのリストにサルを追加すると、新しいサルのリストが生成されます。
• サルのリストに人間を追加して、ヒト科の新しいリストを作成できます (おそらく、サルと人間の上限が最小です)。
• 人類のリストに岩を追加して、新しいリストを生成できますObject(岩と人類は他の共通の祖先を共有していないと仮定します)。

これは理論的には素晴らしいように思えますが、JLS では下限Uは合法ではありません。代わりに次のように書くこともできます:

Uこのようにして、コンパイラは、リストの要素型と追加したい要素型との間の最小上限を正しく推測します。これは合法です。それはまた吸う。比較：

私は関数型プログラミングの大ファンですが、Java コードを Lisp 方言のように見せたくありません。だから私は3つの質問があります：

1. なんてこと？<U super T>バウンドが合法でないのはなぜですか？この質問は実際に以前にここで尋ねられました ( 「Java 型パラメーターに下限を設定できないのはなぜですか?」 ) 。 、」私は実際には購入しません。

2. JLS セクション 4.5.1は次のように述べています。上記の代替staticメソッド シグネチャを考えると、コンパイラは明らかに必要な上限を推測できるため、引数が壊れているように見えます。そうではないと誰かが主張できますか？

3. 最も重要なこと:下限を持つメソッド署名の合法的な代替案を考えられる人はいますか? list.add(monkey)簡単に言えば、目標は、 Lisp ( ) ではなくJava ( ) のように見える呼び出しコードを持つことですadd(list, monkey)。