목록이 왜 <T>.BinarySearch (...)입니까?

Question

List를보고 있는데 몇 가지 오버로드가있는 BinarySearch 메서드가 표시되며 List에서이 메서드를 사용하는 것이 합리적인지 궁금합니다.

목록을 정렬하지 않으면 왜 바이너리 검색을 원하나요? 목록이 정렬되지 않은 경우 메서드를 호출하면 CPU 시간이 낭비됩니다. List에서이 메서드를 사용하면 무슨 점이 있습니까?

Answer 1

정렬 및 검색은 목록에서 두 가지 매우 일반적인 작업입니다. 일반 목록에 이진 검색을 제공하지 않음으로써 개발자의 옵션을 제한하는 것은 비우호적입니다.

라이브러리 디자인에 손상이 필요합니다. .NET 설계자는 두 배열 모두 C#의 목록에 바이너리 검색 기능을 제공하기로 결정했습니다. 왜냐하면 이들은 유용하고 일반적인 작업이고 전화를 걸기 전에 선행 조건 (즉, 목록이 주문 됨)을 이해하도록하십시오.

Sort() 오버로드 중 하나를 사용하여 List<T>을 분류하기는 쉽습니다. 당신이 정렬하는 불변성이 필요하다고 생각한다면 항상 SortedList<TKey,TValue> 또는 SortedSet<T>을 대신 사용할 수 있습니다.

Answer 2

예 그러나 목록에는 Sort() 메소드도 있으므로 BinarySearch 전에 호출 할 수 있습니다.

Answer 3

정렬되지 않은 목록에서 BinarySearch를 호출하는 것은 완전히 바보 같지만 큰 목록이 정렬되어 있다면 완벽하다는 점에 동의합니다.

스트림의 항목이 100,000 개 이상의 정적 목록에 존재하는지 확인하는 데 사용했습니다.

바이너리 이진 검색은 데이터베이스를 검색하는 것보다 빠르게 진행되는 list.Find보다 훨씬 빠르게 수행됩니다.

저는 그것이 의미가 있으며, 거기에 기쁘게 생각합니다 (그렇지 않다면 그것을 구현하는 로켓 과학이 아니라).

Answer 4

다른 사람들은 BinarySearch이 매우 유용하다고 지적했습니다. List<T>. 그러나 실제로는 List<T>에 속하지 않습니다. C++ STL 경험이있는 사람이라면 즉시 인식 할 수 있습니다.

최근의 C# 언어 개발을 통해 정렬 된 목록 (예 : ISortedList<T> : IList<T>)의 개념을 정의하고 BinarySearch (등)을 해당 인터페이스의 확장 방법으로 정의하는 것이 더 적합합니다. 이것은보다 깨끗하고 직각 형 디자인입니다.

나는 이것을 Nito.Linq 라이브러리의 일부로 시작했습니다. 2 개월 만에 첫 번째 안정적인 버전이 나올 것으로 기대합니다.

Answer 5

BinarySearch은 IList<T>.Add 만 IsReadOnly = false과 IList<T>에 대한 의미가 있습니다처럼 분류되는 List<T>에 의미가 있습니다. 그것은 지저분하지만, 처리 할 대상 일뿐입니다. 때로는 기능 X가 기준 Y에 달려 있습니다. Y가 항상 참이 아니라는 사실이 X를 쓸모 없게 만듭니다.

지금, 내 의견으로는, 그것은 .NET은 어떤IList<T> 구현을위한 일반Sort 및 BinarySearch 방법이 없음을 초조 (예를 들어,, 확장 방법). 그렇게했다면 임의 액세스를 제공하는 읽기 전용이 아닌 컬렉션 내의 항목을 쉽게 검색하여 및을 검색 할 수 있습니다.

그런 다음 다시 작성하면 언제든지 직접 (또는 copy someone else's) 작성할 수 있습니다.

Answer 6

바이너리 검색이 놀랍게 정확하게 쓰는 것이 어렵다는 다른 올바른 답변에 유의하십시오. 많은 코너 케이스와 까다로운 정수 연산이 있습니다. 바이너리 검색은 정렬 된 목록에 대한 일반적인 작업이므로 BCL 팀은 고객이 모두 자신의 바이너리 검색 알고리즘을 작성하도록 권장하기보다는 번 올바르게 이진 검색 알고리즘을 작성하여 서비스를 수행했습니다. 상당수의 고객이 만든 알고리즘이 잘못 될 수 있습니다.

Answer 7

검색 및 정렬은 알고리즘 기본 요소입니다. 표준 라이브러리가 빠르고 안정적인 구현을하는 데 도움이됩니다. 그렇지 않으면 개발자가 바퀴를 다시 만드는 데 시간을 낭비하게됩니다.

그러나 .NET Framework의 경우 특정 알고리즘을 사용하면 덜 유용 할 수 있습니다. 어떤 경우에는 자신의 행동이 정의되지 않은 : 목록이 동일한 값을 갖는 두 개 이상의 요소를 포함

1. List<T>.BinarySearch 경우, 방법은 사건의 하나를 반환하고,이 사건 중 하나를 반환 할 수 있습니다, 반드시 첫 번째가 아니야.

2. List<T>이 구현은 불안정한 정렬을 수행합니다. 즉, 두 요소가 같으면 순서가 유지되지 않을 수 있습니다.. 반면, 안정적인 정렬은 동일한 요소의 순서를 유지합니다.

결정론적인 알고리즘이 매우 빠르며, 빌딩 블록으로 훨씬 유용 할 것이기 때문에 수치 스럽습니다. Python, Ruby 및 Go에서 이진 검색 알고리즘이 모두 첫 번째로 일치하는 요소를 찾는다는 것은 주목할만한 사실입니다.

Answer 8

아마 다른 점은 배열이 정렬되지 않은 것과 똑같이 될 수 있다는 것입니다. 그래서 이론적으로 BinarySearch를 배열에 두는 것도 무효가 될 수 있습니다.

그러나 더 높은 수준의 언어의 모든 기능과 마찬가지로 데이터를 이해하고 이해해야하는 사람이 적용해야합니다. 그렇지 않으면 오류가 발생합니다. 물론, ..... 약간의 교차 검사를 적용 할 수있는, 우리는 "IsSorted"고 말했다 플래그를 가질 수 있으며 그렇지 않으면 이진 검색에 실패하지만,

Answer 9

일부 의사 코드 :

if List is sorted 
    use the BinarySearch method 
else if List is not sorted and you think sorting it is "waste of CPU time" 
    use a different algorithm that is more suitable and efficient