빠른 검색을위한 데이터 구조

Question

기관의 데이터 그리드 스테이션 용 응용 프로그램을 개발해야하는 경우. 응용 프로그램의 목적은 오전 10 시부 터 오전 10시 30 분 사이에 일주일에 한 번씩 데이터 그리드 스테이션에서 데이터를 수신 한 다음 데이터 구조에 저장하고 데이터는 숫자로만 구성되지만 번호는 한 항목에 대해 매우 길 수 있습니다 배열,리스트, 링크리스트, 이중 링크리스트, 큐, 우선 순위 큐, 스택, 바이너리 검색 트리, AVL 트리, 스레드 바이너리 트리, 힙, 정렬 된 순차 배열 및 건너 뛰기 목록에서 주어진 시나리오에 가장 적합한 데이터 구조

정렬 된 숫자를 저장하고 싶습니다. 정렬 된 데이터는 오름차순 또는 내림차순 일 수 있으며 주 관심사는 "빠르고 효율적인 검색"입니다.

Answer 1

귀하의 설명에서 나는 다른 데이터를 숫자 나 숫자와 함께 저장하지 않는다는 사실을 알고 있습니다. 그래서 기본적으로 숫자가 세트에 있는지 아닌지 알고 싶습니다.

가장 빠른 방법은 각 숫자에 대한 플래그 배열을 갖는 것입니다. 1에서 1000 사이의 숫자를 처리한다고 가정 해 보겠습니다. 200이라는 숫자가 세트에 있는지 알고 싶습니다. 플래그가 true 또는 false 인 위치 200을보십시오. 아시다시피, 이것은 가장 빠른 방법입니다. 왜냐하면 당신은 한 곳만 둘러보기 때문입니다.

여기 부울 플래그에 대해 이야기 할 때 조금만 저장하면 충분합니다. 숫자, 사용 가능한 메모리 및 시스템 아키텍처에 따라 부울을 비트, 바이트, 단어 등으로 저장하는 것이 좋습니다.

이렇게 말한 결과, 위와 같은 접근 방식이 더 이상 가능하지 않은 많은 숫자를 처리해야 할 수도 있습니다. 그것은 이론상으로는 가장 빠르지 만, 제한된 메모리로 하드 디스크로 스왑하고, 많은 디스크를 읽으며, 다른 알고리즘이 더 좋을 수도 있습니다. 당신의 선택을 할 것이다 : 연속 번호를 저장

• 및 해시 알고리즘

를 사용하여 이진 트리

의 숫자를 저장

그들에 이진 검색을 수행하는 이들의 어떤 가장 효율적이며, 데이터와 기계에 따라 달라집니다.

Answer 2

검색 유형에 따라 다릅니다. 숫자가 데이터 집합 내에 있는지 알아 보려면 해시가 매우 빠르고 데이터 집합의 크기와 무관합니다. 그리고 정렬 할 필요가 없으며 주문의 개념도 없습니다. 나는 래리 벽, 펄의 저자를 인용 할 수있는 경우

는 :

는 연관 배열을 통해 선형 스캔을하는 클럽에로드 된 우지 죽음에 사람을 시도하는 것과 같다.

(연관 배열 해시와 동의어이다.)