問題タブ [lower-bound]

std::algorithm単純な配列でできる限りいつでも使用するのが好きです。今、私には 2 つの疑問があります。std::lower_bound引数として指定した値が見つからない場合に何が起こるかを使用したいとしますか?

*f を印刷したときの結果は 20 です。

を使用しても同じことが起こりますstd::find。

*f を印刷したときの結果は 20 です。

1. これが見つからない場合、戻り値は常に元の引数であるということですか?
2. バイナリ検索アルゴリズムを実装しているため、パフォーマンスの面では のstd::lower_bound方が優れています。std::find配列が大きい場合、たとえば最大 10 要素の場合、std::find のパフォーマンスは向上しますか? 舞台裏で std::lower_bound が std::advance と std::distance を呼び出します。これらの呼び出しも節約できるかもしれません。

どうもありがとう

AFG

Thrustを使用して、配列の各要素が別の配列で見つかるかどうか、およびどこにあるかを検出しようとしています(両方の配列がソートされています)。ベクトル化された検索ルーチン (lower_bound および binary_search) に出会いました。

lower_bound は、各値に対して、その順序に従ってリストに挿入できるインデックスを返します。

また、その位置だけでなく、値が見つかったかどうか (binary_search で実行できる) も知る必要があります。

2 つの検索 (binary_search を呼び出してから lower_bound を呼び出す) を行わずに両方を効率的に達成することは可能ですか?

スカラーの場合、値が見つからない場合、lower_bound は配列の末尾へのポインターを返しますが、これはベクトル化されたバージョンでは発生しません。

ありがとう！

Scalasホームページから取得したListNodeの例は、次のようになります。

このクラスを使用すると、次のようなオブジェクトを作成できます。

ご覧のとおり、ノードの前に整数値を追加できStringます。メソッドに整数が与えられると、typeパラメーターUが自動的にに設定されるため（のスーパータイプではないため） 、これは機能すると思います。AnyprependIntString

独自の下限の例でこれを試すと、エラーが発生します。

ここのタイプが例のようにInt自動的にタイプとして表示されないのはなぜですか？AnyListNode

更新1：これも機能します（新しいListNodeタイプはタイプである必要があると明示的に言わずにAny）

lower_boundで呼び出す方法がわかりませんzip_iterator。

これはコンパイルされません:

VS2010 は、「パラメーター 1 を 'int' から 'const std::_Vector_iterator<_Myvec> &' に変換できません」(さらに、同じエラーのために数十個の他のもの) と言っていますが、あいまいな boost::tuple コンストラクターと関係があります。 、指定されたラムダではありません。

私は何を間違っていますか？

行列の並べ替えの問題を考えてみましょうn x n（つまり、行と列が昇順です）。この問題の下限と上限を見つけたいと思います。

要素を並べ替えてから、最初の要素を最初の行としてO(n^2 log n)出力し、次の要素を2番目の行として出力するというようになっていることがわかりました。しかし、私はそれもであることを証明したいと思います。nnOmega(n^2 log n)

小さな例を試した後、より少ない比較を使用してこの問題を解決できれば、要素の並べ替えに必要な比較の下限にn^2 log(n/e)違反することを証明する必要があると思います。log(m!)m

それを証明する方法について何かアイデアはありますか？

次のJavaコードについて考えてみます。

しかし、なぜそうなのですか？内部的には、型消去はオブジェクトを保持するリストを作成するので、オブジェクト（すべてのクラスのスーパークラスであり、したがって下限ワイルドカードを満たす必要がある）をリストに追加できないのはなぜですか？

Animal次のクラス、Fish、およびがあるとしましょうCatFish。

CatFish拡張FishしてFish拡張しAnimalます。

と呼ばれるジェネリック クラスがありMyPets、これには と呼ばれる型パラメーター (ジェネリック)Tがあり、上記のクラスのオブジェクトでパラメーター化されます。

D私の質問は、クラスの PARENT クラスであるオブジェクトを取得する下限メソッドを作成するにはどうすればよいかということCatFishです。

ソートされたオブジェクトのリストがあり、オブジェクトの最初の出現と最後の出現を見つけたいです。C ++では、std :: equal_range（または1つのlower_boundと1つのupper_bound）を簡単に使用できます。

例えば：

Javaでは、単純な同等性はないようですか？と同じ範囲でどのようにすればよいですか

ちなみに、私は標準のインポートjava.util.Listを使用しています。

まず、私は知っています

1. 下限は O(nlogn)
2. そしてそれを証明する方法

また、下限は O(nlogn) であることに同意します。

私がよく理解していないのは次のとおりです。

一部の特殊なケースでは、比較の数が実際には下限よりもさらに低くなる場合があります。たとえば、バブル ソートを使用して、既に並べ替えられた配列を並べ替えます。比較回数は O(n) です。

では、下限の考え方を実際に理解するにはどうすればよいでしょうか。

Wikipediaal の古典的な定義: http://en.wikipedia.org/wiki/Upper_and_lower_boundsはあまり役に立ちません。

これについての私の現在の理解は次のとおりです。

比較ベースの並べ替えの下限は、実際には最悪の場合の上限です。

つまり、最悪の場合に最善を尽くすことができます。

これは正しいです？ありがとう。

C++ の(または) にC#似た機能を持つ組み込みのデータ構造が必要です。私にとって重要なことは、構造をソートする必要があり（したがって、ここでは実行しません）、次のようなメソッドを持っていることです（つまり、少なくとも値を持つ最初の要素を返します）。また、構造から要素を挿入および削除する必要があります。可能であれば、これらの操作が複雑になる必要があります。の適切なデータ構造を教えてください。std::setstd::mapDictionarylower_boundvO(log(n))C#