더 빠른`elem` Haskell에서 이진 검색 사용

Question

나는 Text의 목록을 가지고 있으며, 정렬 된 순서로되어 있습니다. 선형 검색 대신 이진 검색으로 구현하여 훨씬 더 빠른 elem 버전을 작성할 수 있습니다. 그런 버전이 이미 존재합니까?

Answer 1

하스켈의 목록은 연결된 목록으로 구현되어 임의의 i 번째 요소에 대한 액세스가 O(i)에 있음을 의미합니다. 일반적인 사용법에서는 목록의 경우 이진 검색 버전 elem이 표준 버전보다 시간이 오래 걸릴 것입니다 (아래 @ DanielFischer의 설명 참조).

당신은 다른 컨테이너를 사용하실 수 있습니다

등 제공 당신에게 (n지도/집합의 원소의 개수) O(log n) 액세스 시간을 제공하는 균형 이진 트리로 구현되어 Data.Set 또는 Data.Map, 등.

Answer 2

이진 검색에는 임의 액세스가 필요합니다. haskell리스트는 랜덤 액세스를 제공하지 않기 때문에 (중간에 엘리먼트에 액세스하는 것은 선형 시간이 걸린다) 바이너리 검색은 도움이되지 않는다.

데이터가 임의 액세스를 제공하는 Array 인 경우 이진 검색이 가능합니다.

Answer 3

나는 텍스트 목록을 가지고 있으며 정렬 된 순서로되어 있습니다.

데이터 구조를 변경하면 알고리즘이 명확 해집니다 (Brooks를 바꾸어 말함).

이것은 우리의 데이터 구조가 전형적으로 가변 배열 (포인터 해킹으로 돌아 가지 않음을 의미)이 아닌 하스켈에 특히 해당됩니다.

예 : 텍스트를 저장하는 힙 또는 트리를 사용하면 O (log (n)) 요소를 쉽게 구현할 수 있습니다. 그들이 더 빨리 삽입 할 수 있도록 정렬되어 있다는 사실을 활용할 수 있습니다.