リストの要素の最適な位置を見つける

Question

リストコレクションには特定の順序でデータが格納されています（この順序は変更できません）。このリストにはエンティティタイプオブジェクトが含まれています。

リストの最初の作成後、別のデータソースからのオブジェクトを少し挿入する必要があります。これらのオブジェクトは、ソートが正しいように、特定の位置に挿入する必要があります。例えば

初期リストは要素を以下している場合

1. AAA
2. AAB
3. AAC
4. ACC
が
5. ADA

初期集団の後、私は「ABBを挿入したいです要素の場合、3〜4の間に挿入する必要があります。

私は新しい要素の正しい位置を見つける次の方法があります。

private static int FindPositionForArticle(string word)   
    { 
     string key = word.ToLower(); 
     for (int i = word.Length; i >= 0; i--) 
     { 
      if(i < word.Length) 
       key = key.Remove(i, 1); 

      int pos = 0; 
      int insertPos = 0; 
      foreach(ArticleEntity article in list) 
      { 
       if(article.Text.ToLower().StartsWith(key)) 
        insertPos = pos; 
       else if (!article.Text.ToLower().StartsWith(key) && insertPos > 0) 
        return insertPos++; 
       pos++; 
      } 
     } 
     return 0; 
    } 

この方法の背後にある目的のアイデア：挿入する必要が

1. テイク「言葉」と「言葉」

2. と同じ名前を持つ要素の位置を見つけようとした場合何も見つかりませんでした。最後の文字を「単語」から削除し、再度検索してください。

3. ベストポジションが見つかるまで、最後の文字の削除を繰り返します。

残念ながら私のメソッドにはバグがあります（間違って実装されています）。現在のところ、私の方法は、最良のポジションは0であることを示唆していますが、これは全く間違っています。

あなたは私のサンプルコードでプレイしたい場合はあなたがでそれをダウンロードすることがあります。

http://dl.getdropbox.com/u/204110/FindPosition.cs.txt

は、事前にありがとうございました。

Answer 1

int index = list.BinarySearch(word); 

インデックスが正またはゼロの場合、そのアイテムはリストに見つかりました。負の場合は、リスト内で次に高い項目のインデックスのビット補数が含まれます。

だから、このために：

List<string> list = new List<string>{"AAA","AAB","AAC","ACC","ADA"}; 
int index = list.BinarySearch("ABB"); // => -4 
int insertIndex = ~index; // => 3 
list.Insert(insertIndex, "ABB"); 

Answer 2

あなたはSortedListデータ構造を使用して考えられていますか？特定の方法でソートする必要のある複合データ型を保持する場合は、IComparerオブジェクトを指定して作成することができます。

IComparerが実行しなければならないことは、1つのアイテムが前のものか後のものかを判断できることだけです。それを考えると、SortedListは注文を正しく保持します。

この構造体を使用すると、内部で指定したとおりに順序が維持され、本質的にソートを実装するコードを管理する必要がなくなります。

Answer 3

文字列型のSortedListはうまく動作しませんか？

Answer 4

このコード：

private static System.Collections.SortedList list = new System.Collections.SortedList(); 

    static void Main(string[] args) 
    { 
     list.Add("AAA" , "AAA"); 
     list.Add("AAB", "AAB"); 
     list.Add("AAC", "AAC"); 
     list.Add("ACC", "ACC"); 
     list.Add("ADA", "ADA"); 
     Console.WriteLine("List before"); 
     for (int j = 0; j < list.Count ; j++) 
     { 
      Console.WriteLine(list.GetByIndex(j)); 
     } 
     list.Add("ABB","ABB"); 


     Console.WriteLine(list.IndexOfKey("ABB")); 

     for (int j = 0; j < list.Count; j++) 
     { 
      Console.WriteLine(list.GetByIndex(j)); 
     } 


     Console.ReadLine(); 

    } 

は、あなたがそれを必要とする項目を挿入ます。..

それとも何か他のものを必要としません？あなたは共通の文字列を並べ替える必要はありません。

Answer 5

インデックスを使用してアクセス可能なリストは、Chris Doggettのanwserに似たバイナリ検索を実装することができます。これにより、現在実行中のリストよりも実行時間が短縮されます。

ランタイムは現在リストの項目数に直線的で、nの項目を入力すると、実行時間は約nです。バイナリ検索を使用して

（SortedListを経由して内部的に行うように）あなたは、例えば、挿入あたりLOG2（N）のより良いランタイムとなってしまいます* n *** log2（n）* n個のアイテムを挿入するときの合計実行時間。

バイナリ検索の基本的な考え方は単純です：

1. リスト項目

2. まず、あなたは、リストの右=現在の数、0 =左（可能な位置として完全な範囲を取ります）

3. 左、右と等しい場合は、真ん中を選んで、

4. そうでない場合は、適切な位置を発見しました要素（左+右）/ 2を挿入し、挿入するキーと比較します。

   • 比較の結果は、あなたが結果が大きい場合にはそのためのリスト
   • の左半分に次の反復のための探索範囲をリセットし、右ミドルインデックス-1に設定し、< 0の場合0よりも左に設定すると、中位のインデックス+ 1に設定され、次の検索が右側の部分になります
   • それ以外の場合、比較は0になります。同じインデックス）、そしてループを壊す（5.を参照）。
5. ループ3で。検索範囲が小さくなりました...

Answer 6

私はこのようにしています。 ArticleEntityオブジェクトのリストがあります。このリストをソートする必要があります。したがって、まずクラスにソートする機能を追加する必要があります。私の例はVBであり、C＃に変換するのは難しくありません。

そうのようなあなたのクラスに並べ替え追加：

Public Class ArticleEntity 
    Implements IComparable(Of ArticleEntity) 

    Public Overloads Function CompareTo(ByVal Other As ArticleEntity) As Integer _ 
     Implements IComparable(Of ArticleEntity).CompareTo 
     Return Me._PropertyToSort.CompareTo(Other._PropertyToSort) 
    End Function 

その後、あなたは（ArticleEntity）のリストに追加する必要があるすべてのものを追加した後、次のことができます。

MyListOfArticleEntities.Sort() 

私はこれは何だと思いますあなたが探しています。そうでない場合は教えてください。

Answer 7

あなたのコレクションはがListである必要がありますか？

新しい要素を挿入する前にリストから要素にアクセスする必要がない場合は、heapがうまくいくように聞こえます。基本的には、希望：

1. 挿入ヒープにすべてのあなたの最初の要素が
2. その後、
3. まったく同じように、余分な項目を挿入ヒープからListに、ソートされた順序で、各項目を読みます。

これらの各ステップは、1オブジェクトにつきO（log n）時間だけです。私は、C＃がヒープの実装を持っていることは確かです。

注：グローバルメモリプールの意味ではなく、データ構造の意味で「ヒープ」を意味します。