목록에서 요소의 최적 위치 찾기

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); 

색인이 양수 또는 0이면 해당 항목이 목록에서 발견되었습니다. 음수 인 경우에는 목록에서 다음으로 높은 항목의 인덱스에 대한 비트 보수가 포함됩니다. 이것에 대한 그래서

는 :

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가 수행해야하는 유일한 작업은 하나의 항목이 이전인지 또는 이후인지를 결정할 수 있다는 것입니다. 이 경우 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(); 

    } 

당신이 그것을 필요로하는 항목을 삽입한다 ..

아니면 다른 뭔가를해야합니까? Icompare가 필요하지 않습니다. 일반적인 문자열을 정렬하고 있습니다.

Answer 5

색인을 통해 액세스 할 수있는 목록이므로 Chris Doggett의 anwser와 비슷한 이진 검색을 구현할 수 있습니다. 이렇게하면 현재 순차적으로 구현할 때 목록을 검토하는 것보다 더 나은 런타임이 제공됩니다.

런타임에 목록에있는 항목의 수는 현재 선형이므로 n 항목을 입력하면 약 n의 런타임. 당신이 은 log2 (n)에 삽입 당, 예를 들어,의 더 나은 실행으로 끝날 것이다 (SortedList이 방법에 의해 내부적으로처럼) 이진 검색을 사용하여

* n *** log2 (n) * n 개의 항목을 삽입 할 때의 총 런타임.

이진 검색의 기본 개념은 간단하다 :

이

1. 목록 항목

2. , 당신은 가능한 위치 (왼쪽 = 0, 목록에서 바로 = 현재 카운트로 전체 범위를 먼저 받아)

3. 왼쪽 오른쪽 같다면, 당신은 중간을 선택,

4. 그렇지 않으면 적절한 위치를 발견했다 요소 (왼쪽 + 오른쪽)/2를 선택하고 삽입 할 키와 비교하십시오. 비교의 결과가 < 0이면

   • , 당신은 결과가 큰 경우, 따라서 목록
   • 의 왼쪽 절반 다음 반복에 대한 검색 범위를 재설정, 오른쪽 중간 인덱스 1로 설정 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. 나중에 힙에 모든 초기 요소하는 List에 힙에서
3. 가 정렬 된 순서로 각 항목을 읽어
동일한 방법으로 별도의 항목을 삽입 .

각 단계는 개체 당 O (로그 n) 시간입니다. C#에는 힙 (heap) 구현이 있습니다.

참고 : 전역 메모리 풀의 의미가 아니라 데이터 구조의 관점에서 "힙"을 의미합니다.