問題タブ [sortedcollection]

私はSortedCollectionのこの実装を使用します。

アイテムのインデックスを見つけるための構文は何でしょう'A'か？これは私が選択したソートキーではないことに
注意してください。'A'

これを行うための失敗した方法は次のとおりです。

Cincom VisualWorksでコレクションを2つの基準で並べ替えるにはどうすればよいですか？

例：人物を含むOrderedCollectionがあり、最初に人物を年齢で並べ替え、次に年齢が同じ場合は名前で人物を並べ替える新しいコレクションが必要です。

あなたが私の英語を理解できることを願っています！ありがとう..

一度に 1 つの項目を追加する並べ替えられたリストを作成する必要があります。挿入操作LinkedList<T>が効率的であるため、を使用することにしました。しかし、適切な場所を見つけるときは、はるかに時間がかかるようです。線形検索を使用して場所を取得しています。メソッドを使用して適切な場所を取得するために二分探索を使用すると、パフォーマンスが向上しますか? thisによると、それでも O(n) 操作です。どう思いますか？もしそうなら、作品のための他のより良いデータ構造はありますか? 別のデータ構造を使用すると、新しい値を途中に挿入するときに、その位置の後のすべてのデータを 1 つの位置だけシフトする必要があるため、これは明らかに望ましくありません。ElementAt

リスト/配列の最小要素を効率的に削除する必要があるこの問題に遭遇しました。それを解決するのはかなり簡単です - ヒープで十分です。

ただし、現在の問題は、最小の要素を削除すると、データ構造内の他の要素が変更され、順序が変更される可能性があることです。例はこれです：

私は要素の配列を持っています:

配列から「1」を削除すると、「5」と「12」がそれぞれ「4」と「17」に変更されます。

したがって、順序は維持されません。

ただし、削除される要素には、変更されるすべての要素へのポインターがありますが、変更される要素の数と量はわかりません。

だから私の質問は：

並べ替えを維持しながらデータ構造から最小の要素を削除するときに、これらの要素を格納してパフォーマンスを最大化する最良の方法は何ですか? それとも、ソートせずにそのままにしておくべきですか？

私の現在の実装では、それらをソートせずにベクトルに格納するだけなので、時間の複雑さは O(N^2)、最小要素を見つけるための O(N)、および N 個の削除です。

スイープ ライン (SL) に次のプロパティを持つデータ構造を必要とするBentley-Ottman アルゴリズムを実装しています。

• のソートされたコレクションをT維持するTIComparable<T>
• 要素の挿入は である必要がありO(log count)、要素が既に挿入されているかどうかを返す必要があります。
• 要素の削除はO(log count)、
• 特定の要素e(既にコレクションに含まれているかどうかにかかわらず) について、コレクションの前後の要素がe並べ替え順序で必要です。

SortedList<TKey, TValue>リスト内のすべての連続する要素を移動する必要があるO(count)ため、挿入と削除があります。O(1)ただし、インデックスを付けることができるため、 のインデックスがわかれば、 の前後の要素を取得できますe。

SortedDictionary<TKey, TValue>挿入と削除SortedSet<T>がO(log count)ありますが、次の要素と前の要素を提供するイテレータが見つかりません。

完全な機能を提供する実装はありますか?

そうでない場合、それを実装するための最速の方法は何ですか? LinkedList<T>バイナリ検索を許可しません。List<T>まだO(count)挿入/削除があります。独自のバランスの取れたツリーを実装する必要はありますか?

こんにちは、私は学んでおり、smalltalk は初めてで、SortedCollection を画面に出力して keysAndValueDo を使用しようとしていますが、どのように行われたかわかりません。

次のコードを検討してください。

この「便利な」メソッドが Smalltalk コードで数回使用されているのを見たことがありますが、そこには直接 Obj-C に相当するものがない SortedCollection があります。Objective-C に相当するものは何ですか?