一个经典的问题，也就是10^N个数，远超过内存的大小，如何排序。答案虽然我自己也想到了，但别人更早想到，经典做法，把文件拆成多份，然后多线程对文件分别进行排序，然后进行多路归并，多路归并时，经典做法就是用优先队列。这也是Lucene在And操作时选择的方法，在DisjunctionSumScorer中有ScorerDocQueue scorerDocQueue，它就是一个优先队列。
ScorerDocQueue的成员有：
/* 保存堆中的元素 */
private final HeapedScorerDoc[] heap;
/* 堆最多元素数量 */
private final int maxSize;
/* 堆中当前元素数量 */
private int size;
/* 与heap[1]值相同，它是为了提高速度 */
private HeapedScorerDoc topHSD;
HeapedScoreDoc类的成员只有两个，一个是Scorer本身，另一个是Scorer的第一个doc id也就是最小的一个doc id。
private void initScorerDocQueue() throws IOException {
scorerDocQueue = new ScorerDocQueue(nrScorers);
for (Scorer se : subScorers) {
if (se.nextDoc() != NO_MORE_DOCS) {
scorerDocQueue.insert(se);
}
}
}
在DisjunctionSumScorer类中initScorerDocQueue函数将subScorers放入优先队列中。
Read full article from Lucene中的堆(Heap)[ScorerDocQueue,TopScoreDocCollector] - quweiprotoss的日志 - 网易博客
No comments:
Post a Comment