lucene中用到的優先隊列

jdk有一個java.util.PriorityQueue。lucene中也有個PriorityQueue.為了節約空間和更高效,lucene沒有使用jdkp中的PriorityQueue.它們的主要讀取方法時間都是的log(n),但也有些不同。

下面看看lucene中使用的 PriorityQueue。 它内部是一個堆排序。 java.util.PriorityQueue是一個自增長的優先隊列.也就是說，随着插入元素的增加，它的容量會越來越大，而 org.apache.lucene.util.PriorityQueue則不會,它是一個指定的容量的優先隊列。因為它儲存的始終是最大的資料.是以,如果隻取前n個資料時可以用lucene的 PriorityQueue,這樣可以達到節省記憶體。 下面分析一下原代碼. 下面是lucene中的PriorityQueue的插入節點的實作細節， public Object insertWithOverflow(Object element) { if (size < maxSize) {//小于最大容量，直接放進堆       put(element);       return null;     } else if (size > 0 && !lessThan(element, heap[1])) {//如果目前的堆已滿，并且大于目前最小的元素,則将最小元素傳回，并插入新元素       Object ret = heap[1];       heap[1] = element;       adjustTop();//重新進行堆排序       return ret;     } else {//堆已滿并且要插入的元素小于堆中最小的元素       return element;     } } heap[1]是堆頂,儲存堆中的最小元素.

由引看出在 org.apache.lucene.util.PriorityQueue中n是固定的，是以重新進行堆排序的時間是恒定的。

可能是為了提高插入效率,在 org.apache.lucene.util.PriorityQueue的實作類TopDocCollector類中儲存了隊列中的最小元素，如果存在最小元素,則可以先與最小元素進行比較.再決定是否執行插入操作. 用變量儲存了目前隊列中最小的元素.以提高效率    public void collect(int doc, float score) {     if (score > 0.0f) {       totalHits++;       if (reusableSD == null) {         reusableSD = new ScoreDoc(doc, score);       } else if (score >= reusableSD.score) {//如果有最小元素,則與最小元素比較。如果大于最小元素則更新最小元素,并執行插入操作.         // reusableSD holds the last "rejected" entry, so, if         // this new score is not better than that, there's no         // need to try inserting it         reusableSD.doc = doc;         reusableSD.score = score;       } else {//如果小于最小元素，直接傳回         return;       }       reusableSD = (ScoreDoc) hq.insertWithOverflow(reusableSD);     }   }

不過個人認為 insertWithOverflow方法裡已經做了類似判斷,而且從效率上來講沒差別,沒必要在外面增加最小值判斷,這樣做反而容易引起邏輯不一緻.