Lucene 학습 노트 의 - 핵심 데이터 구조 Priority Queue 의 실현 원리

Luene 의 핵심 응용 장면 은 전문 검색 이다.쉽게 말 하면 사용자 가 입력 한 키 워드 를 통 해 관련 문 서 를 일치 시 킨 다음 일치 정도 에 따라 TopN 의 조회 결 과 를 사용자 에 게 되 돌려 주 는 것 입 니 다.여기 서 해결 해 야 할 핵심 문 제 는 TopN 의 결 과 를 어떻게 빨리 되 돌려 주 느 냐 하 는 것 이다. 이것 은 본질 적 으로 정렬 의 문제 이다.정렬 하면 우 리 는 많은 선택 이 있 습 니 다. 거품 이 나 고 빨리 배열 하고 병합 합 니 다.이 정렬 알고리즘 들 은 데이터 양 이 적 을 때 문제 가 되 지 않 습 니 다.일단 데이터 양 이 너무 많 으 면 문제 가 된다.
예 를 들 어 1000 만 개의 배열 정렬:

        Integer[] a = new Integer[10000000];

        for(int i=0;i<10000000;i++){
            a[i] = (int) (Math.random()*10000000);
        }
        long start = System.currentTimeMillis();
        Arrays.sort(a);
        System.out.println((System.currentTimeMillis() - start) +"   ");

내 컴퓨터 에 5 초 정도 걸 리 는데 이 대기 시간 은 사용자 체험 에 있어 서 그다지 feeling good 이 아니다.
이 럴 때 는 최 적 화 를 고려 해 야 한다.최 적 화 는 기본적으로 감법 을 하 는 과정 이다.다시 우리 의 핵심 수요 로 돌아 가기: 검색 키 워드 를 바탕 으로 TopN 의 결 과 를 되 돌려 줍 니 다.즉, 우 리 는 TopN 의 결과 가 질서정연 하면 된다.상기 수 요 를 바탕 으로 우 리 는 새로운 데이터 구 조 를 도입 했다. 더미 (Heap).
더 미 는 특수 한 이 진 트 리 이다.이 진 트 리 란 모든 노드 에 최대 두 개의 키 노드 가 있다. 최대 두 아 이 를 낳 고 초 생 은 허용 되 지 않 는 다.
이 진 트 리 라 는 나무 구조 에 있어 가장 핵심 적 인 관 계 는 부자 노드 관계 이다.서로 다른 노드 관 계 를 정의 하면 우 리 는 다양한 데이터 구 조 를 얻어 서로 다른 장면 의 업무 문제 에 대응 할 수 있다.예 를 들 면:
'자식 노드 가 부모 노드 보다 크 면 안 된다' 고 규정 하면 우 리 는 뿌리 노드 가 가장 큰 노드 이 고 큰 무 더 기 를 얻 을 수 있다.
'하위 노드 가 부모 노드 보다 작 으 면 안 된다' 고 규정 하면 우 리 는 뿌리 노드 가 가장 작은 노드 이 고 작은 지붕 더 미 를 얻 을 수 있다.
'뿌리 노드 가 왼쪽 나무 보다 크 고 오른쪽 나무 보다 작 으 며 나무 도 마찬가지 입 니 다' 라 고 규정 하면 우 리 는 이 진 트 리 를 찾 을 수 있 습 니 다.두 갈래 검색 트 리 의 좌우 균형 을 맞 추기 위해 우 리 는 '붉 은 검 은 나무', 'AVL 나무', Treap 등 다양한 전략의 균형 트 리 를 얻 었 다.
이런 개념 적 인 것들 은 이해 할 수 있 으 면 OK.
쌓 인 경 위 를 이해 하면 우 리 는 약간 곤 혹 스 러 울 수 있 지만 질서 있 는 구 조 를 직접적 으로 유지 하지 않 았 다.예, 질서 있 는 구 조 를 직접 유지 하지 않 고 데 이 터 를 삭제 함으로써 정렬 기능 을 수행 합 니 다.이 점 을 이해 하 는 것 이 특히 중요 하 다.큰 무 더 기 를 예 로 들 면 무 더 기 는 가장 큰 요소 이기 때문에 우 리 는 한 더미 에 대해 확신 할 수 있다. 우 리 는 무 더 기 를 쌓 은 데 이 터 를 계속 삭제 하면 빈 더미 까지 질서 있 는 결 과 를 얻 을 수 있다.이것 이 바로 정렬 된 사상 이다.
그러면 어떻게 더 미 를 이용 하여 TopN 의 질서 있 는 출력 을 실현 합 니까?검색 한 점 수 를 정렬 항목 으로 하여 가장 높 은 점 수 를 받 은 N 개의 결 과 를 출력 하 기 를 바 랍 니 다.우 리 는 먼저 N 개의 결 과 를 옮 겨 다 니 며 N 개의 요소 가 있 는 작은 지붕 더 미 를 얻 었 다.쌓 인 요소 가 가장 작 기 때문에 남 은 점수 결 과 를 옮 겨 다 니 며 쌓 인 뿌리 노드 와 비교 하면 됩 니 다.점수 결과 가 쌓 인 뿌리 노드 보다 작 으 면 버 립 니 다.점수 결과 가 쌓 인 뿌리 노드 보다 크 면 뿌리 노드 를 삭제 합 니 다.그리고 이 채점 결 과 를 사용 하여 더미 에 업데이트 합 니 다.이렇게 해서 마지막 에 이 무 더 기 는 우리 가 원 하 는 TopN 을 지 켰 다.
예 를 들 어 1000 만 의 데이터 에 대해 우 리 는 가장 큰 100 개의 숫자 를 제시 하고 코드 는 다음 과 같다.

Integer[] a = new Integer[10000000];

        for(int i=0;i<10000000;i++){
            a[i] = (int) (Math.random()*10000000);
        }
        long start = System.currentTimeMillis();

        PriorityQueue pq = new PriorityQueue(100) {
            @Override
            protected boolean lessThan(Integer t1, Integer t2) {
                return t1 < t2;
            }
        };

        for(int i=0;i<10000000;i++){
            pq.insertWithOverflow(a[i]);
        }
        Integer[] b = new Integer[100];
        for(int i=99;i>=0;i--){
            b[i] = pq.pop();
        }
        System.out.println((System.currentTimeMillis() - start) +"   ");
        System.out.println(Arrays.asList(b));

이 시간 은 50 여 밀리초 밖 에 걸 리 지 않 는 다.이 성능 차 이 는 거의 100 배 이다.이러한 데이터 구 조 를 쌓 는 것 이 TopN 이라는 장면 에서 얼마나 적합 한 지 알 수 있다.
사실 JDK 는 더미 에 기반 한 우선 순위 대열 인 Priority Queue 가 있 는데 왜 Lucene 이 바퀴 를 다시 만들어 야 합 니까?
JDK 의 기본 Priority Queue 는 자동 으로 확장 할 수 있 으 며 Lucene 은 길 이 를 정 해 야 합 니 다.JDK 의 기본 Priority Queue 는 데이터 구 조 를 비교적 긴밀 하 게 봉 인 했 고 Lucene 은 쌓 인 지붕 을 조정 하 는 등 유연성 이 필요 하 다.
작은 지붕 더 미 는 이 진 트 리 이기 때문에 그 논리 구 조 는 대체적으로 다음 과 같다.

    1
 3    2
5 8  7 6

관찰 하면 이 규칙 을 발견 할 수 있다. 바로 1 층 에 1 개의 요소 만 있다 는 것 이다.2 층 에는 최대 2 개의 원소 가 있다.3 층 에는 최대 4 개의 원소 가 있 는데, 즉 N 층 에는 2 ^ (n - 1) 개의 원소 가 있다.이 법칙 은 뒤에 유용 하 다.
그러면 어떻게 인 코딩 을 해서 한 무 더 기 를 만 듭 니까?가장 간단 한 실현 방식 은 배열 을 바탕 으로 Lucene 의 실현 을 예 로 들 어 배 우 는 것 이다.

public abstract class PriorityQueue {
    private int size;
    private final int maxSize;
    private final T[] heap;

배열 을 정의 하 였 습 니 다.다음 과 같은 규정 만 하면 옳 은 논리 구 조 를 만족 시 킬 수 있다.

1. heap[0]     。
2. heap[1]    。
3. heap[2~3]    ，heap[4~7]      ... heap[2^n ~ 2^(n+1)-1]  n+1 

이렇게 하면 요소 가 배열 의 어느 위치 에 있 는 지 우 리 는 그것 이 어느 층 에 속 하 는 지 알 수 있다.
다음 에 해결 해 야 할 문 제 는:

어떻게 요 소 를 더미 에 삽입 합 니까?

앞 에 N 개의 요소 가 있다 고 가정 하면 코드 는 매우 간단 하 다.

    public final T add(T element) {
        ++this.size;
        this.heap[this.size] = element;
        this.upHeap(this.size);
        return this.heap[1];
    }

두 단계: s1 요 소 를 꼬리 에 추가 합 니 다.s2: 이 요 소 는 아버지 노드 보다 작 을 수 있 기 때문에 아버지 노드 와 재 귀적 으로 비교 하고 위 치 를 바 꾸 면 됩 니 다. 여 기 는 약간 거품 이 나 는 느낌 입 니 다.탁 구 를 물 에 눌 러 놓 고 손 을 놓 으 면 뜬다 고 상상 하 는 것 이다.

어떻게 더미 에서 원 소 를 삭제 합 니까?

   public final T pop() {
        if (this.size > 0) {
            T result = this.heap[1];
            this.heap[1] = this.heap[this.size];
            this.heap[this.size] = null;
            --this.size;
            this.downHeap(1);
            return result;
        } else {
            return null;
        }
    }

두 단계: s1: 배열 꼬리 에 있 는 요소 로 노드 요 소 를 덮어 씁 니 다.s2: 이 요소 가 임 근 노드 를 이 길 수 있 는 지 의 위 치 는 아직 확실 하지 않 기 때문에 두 개의 키 노드 와 비교 하여 위 치 를 조정 해 야 합 니 다.이곳 은 약간 가라앉 은 느낌 이 든다.쇠 공 을 물 에 빠 뜨리 고 스스로 가 라 앉 았 다 고 상상 하 는 것 이다.
여기 서 쌓 인 삽입 과 삭제 작업 은 생각 이 비교적 가 볍 고 신기 하 므 로 잘 생각해 볼 만하 다.
Lucene 에서 Priority Queue 는 어떤 응용 장면 이 있 습 니까?

HitQueue, 검색 점수 의 핵심.

FieldValueHitQueue, 필드 정렬 의 핵심.....

한 마디 로 하면 이 데이터 구 조 는 Lucene 에서 30 ~ 40 개의 하위 클래스 로 매우 광범 위 하 게 응용 된다.그 실현 체 제 를 이해 하 는 것 은 다른 기능 을 이해 하 는 데 큰 도움 이 된다.