.net - LinkedList で二分探索するかソートされた値リストの途中に値を挿入するとパフォーマンスが向上しますか?

Question

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

Answer 1

あなたの目的のために、おそらくSortedDictionaryクラス（またはおそらくSortedList）を使用したほうがよいでしょう

SortedDictionary は、O(log n) の挿入および取得時間を提供します。