Hits類中緩存的實現、LRU算法
關于Hits類。
這個Hits類可是非常的重要，因為Lucene使用了緩存機制，關于緩存的實現就是在這個Hits類中。Hits工作過程中，使用了LRU算法，即通過一個HitDoc結構來實現一個雙向鏈表，使用LRU置換算法，記錄用戶最近訪問過的Document。
開門見山，直接拿出Hits類的實現代碼來說話。
package org.apache.lucene.search;
import java.io.IOException;
import java.util.Vector;
import java.util.Iterator;
import org.apache.lucene.document.Document;
import org.apache.lucene.index.CorruptIndexException;
public final class Hits {
private Weight weight;
private Searcher searcher;
private Filter filter = null;
private Sort sort = null;
private int length; // Hits的長度，即滿足查詢的結果數量
private Vector hitDocs = new Vector(); // 用作緩存檢索結果的(Hit)
private HitDoc first; // head of LRU cache
private HitDoc last; // tail of LRU cache
private int numDocs = 0; // number cached
private int maxDocs = 200; // max to cache
Hits(Searcher s, Query q, Filter f) throws IOException {
weight = q.weight(s);
searcher = s;
filter = f;
getMoreDocs(50); // retrieve 100 initially | 從緩存中取出檢索結果，如果緩存為null，則需要查詢，查詢后將結果加入緩存中
}
Hits(Searcher s, Query q, Filter f, Sort o) throws IOException {
weight = q.weight(s);
searcher = s;
filter = f;
sort = o;
getMoreDocs(50); // retrieve 100 initially | 從緩存中取出檢索結果，如果緩存為null，則需要查詢，查詢后將結果加入緩存中
}
/**
* 將滿足檢索結果的Document加入到緩存hitDocs中
*/
private final void getMoreDocs(int min) throws IOException {
/////////////////////////////////////////////////////////////////////////////////////////////
System.out.println("■■■■■■■■■■■■■■■■■■■■■■■■進入getMoreDocs()方法中時，hitDocs.size="+hitDocs.size());
///////////////////////////////////////////////////////////////////////////////////////////
if (hitDocs.size() > min) {
min = hitDocs.size();
}
int n = min * 2; // 擴充緩存容量為默認的2倍(默認最小情況下，也要擴充緩存。即使檢索結果為1條記錄，緩存的長度也擴充為100)
TopDocs topDocs = (sort == null) ? searcher.search(weight, filter, n) : searcher.search(weight, filter, n, sort);
length = topDocs.totalHits;
ScoreDoc[] scoreDocs = topDocs.scoreDocs;
float scoreNorm = 1.0f;
if (length > 0 && topDocs.getMaxScore() > 1.0f) {
scoreNorm = 1.0f / topDocs.getMaxScore();
}
int end = scoreDocs.length < length ? scoreDocs.length : length;
for (int i = hitDocs.size(); i < end; i++) {
hitDocs.addElement(new HitDoc(scoreDocs[i].score * scoreNorm,
scoreDocs[i].doc));
}
/////////////////////////////////////////////////////////////////////////////////////////////
System.out.println("■■■■■■■■■■■■■■■■■■■■■■■■離開getMoreDocs()方法中時，hitDocs.size="+hitDocs.size());
///////////////////////////////////////////////////////////////////////////////////////////
}
// 返回Hits的長度，即滿足查詢的Document的數量，并非是緩存Vector hitDocs的長度
public final int length() {
return length;
}
// 根據Document的編號獲取到Document
public final Document doc(int n) throws CorruptIndexException, IOException {
/////////////////////////////////////////////////////////////////////////////////////////////
System.out.println("hitDocs.size()="+hitDocs.size());
/////////////////////////////////////////////////////////////////////////////////////////////
HitDoc hitDoc = hitDoc(n);
// Update LRU cache of documents
remove(hitDoc); // remove from list, if there
addToFront(hitDoc); // add to front of list
if (numDocs > maxDocs) { // if cache is full
HitDoc oldLast = last;
remove(last); // flush last
oldLast.doc = null; // let doc get gc'd
}
if (hitDoc.doc == null) {
hitDoc.doc = searcher.doc(hitDoc.id); // cache miss: read document
}
return hitDoc.doc;
}
// 得到第n個Document的得分
public final float score(int n) throws IOException {
return hitDoc(n).score;
}
// 得到第n個Document的編號
public final int id(int n) throws IOException {
return hitDoc(n).id;
}
public Iterator iterator() {
return new HitIterator(this);
}
private final HitDoc hitDoc(int n) throws IOException {
if (n >= length) {
throw new IndexOutOfBoundsException("Not a valid hit number: " + n);
}
if (n >= hitDocs.size()) {
getMoreDocs(n);
}
return (HitDoc) hitDocs.elementAt(n);
}
private final void addToFront(HitDoc hitDoc) { // insert at front of cache
if (first == null) {
last = hitDoc;
} else {
first.prev = hitDoc;
}
hitDoc.next = first;
first = hitDoc;
hitDoc.prev = null;
numDocs++;
}
private final void remove(HitDoc hitDoc) { // remove from cache
if (hitDoc.doc == null) { // it's not in the list
return; // abort
}
if (hitDoc.next == null) {
last = hitDoc.prev;
} else {
hitDoc.next.prev = hitDoc.prev;
}
if (hitDoc.prev == null) {
first = hitDoc.next;
} else {
hitDoc.prev.next = hitDoc.next;
}
numDocs--;
}
}
final class HitDoc {
float score;
int id;
Document doc = null;
HitDoc next; // in doubly-linked cache
HitDoc prev; // in doubly-linked cache
HitDoc(float s, int i) {
score = s;
id = i;
}
}
上面代碼中，紅色標注的部分為后面測試之用。
一次查詢時，需要構造一個Query實例。從Hits類的成員變量來看，在檢索的過程中，一個Query實例并不是只使用一次，那么多次使用進行查詢就需要記錄這個Query實例的狀態。
為了更加直觀，寫了一個測試類，來觀察緩存長度的分配情況：
package org.shirdrn.lucene.learn.test;
import java.io.IOException;
import java.util.Date;
import java.util.Iterator;
import org.apache.lucene.analysis.cjk.CJKAnalyzer;
import org.apache.lucene.document.DateTools;
import org.apache.lucene.document.Document;
import org.apache.lucene.document.Field;
import org.apache.lucene.index.CorruptIndexException;
import org.apache.lucene.index.IndexWriter;
import org.apache.lucene.index.Term;
import org.apache.lucene.queryParser.ParseException;
import org.apache.lucene.search.Hit;
import org.apache.lucene.search.Hits;
import org.apache.lucene.search.IndexSearcher;
import org.apache.lucene.search.Query;
import org.apache.lucene.search.TermQuery;
import org.apache.lucene.store.LockObtainFailedException;
public class MyHitsTest {
public void create() throws CorruptIndexException, LockObtainFailedException, IOException{
String indexPath = "H:\\index";
IndexWriter writer = new IndexWriter(indexPath,new CJKAnalyzer(),true);
for(int i=0;i<500;i++){
Document doc = new Document();
doc.add(new Field("title","搜索引擎收錄新頁面與文章原創性問題",Field.Store.YES,Field.Index.TOKENIZED));
doc.add(new Field("date",
DateTools.timeToString((new Date().getTime()), DateTools.Resolution.MINUTE),
Field.Store.YES, Field.Index.UN_TOKENIZED));
doc.add(new Field("author","Shirdrn",Field.Store.YES,Field.Index.UN_TOKENIZED));
String contents = "如果分詞后的多個關鍵字，在關鍵文章分詞中，某一關鍵片段中出現的關鍵頻率最高，這個關鍵片段當然是Google檢索結果呈現的那兩行關鍵摘要。";
doc.add(new Field("contents",contents,Field.Store.NO,Field.Index.TOKENIZED));
writer.addDocument(doc);
}
writer.optimize();
writer.close();
}
public void search() throws CorruptIndexException, IOException{
Query query = new TermQuery(new Term("contents","關鍵"));
String indexPath = "H:\\index";
IndexSearcher searcher = new IndexSearcher(indexPath);
Hits hits = searcher.search(query);
System.out.println("★★★共檢索出滿足的結果 "+hits.length()+" 條。");
Iterator it = hits.iterator();
while(it.hasNext()){
System.out.print("★調用Hits的doc()方法，(Vector): ");
hits.doc(0); //執行這一行代碼是為了觀察：當獲取一個Document的時候緩存的長度，因為第一次查看緩存的時候其長度是為0的，如果檢索結果數量不為0則之后緩存長度是不為0的，至少為100
Hit hit = (Hit)it.next();
System.out.println("★檢索到的Hit的ID為 ： "+hit.getId());
}
}
}
class MyTest{
public static void main(String[] args) throws CorruptIndexException, LockObtainFailedException, IOException, ParseException {
MyHitsTest hitsTest = new MyHitsTest();
//hitsTest.create();
hitsTest.search();
}
}
首先要構造500個Document，建立索引，之后，執行檢索的操作，結果如下所示：
■■■■■■■■■■■■■■■■■■■■■■■■進入getMoreDocs()方法中時，hitDocs.size=0
■■■■■■■■■■■■■■■■■■■■■■■■離開getMoreDocs()方法中時，hitDocs.size=100
★★★共檢索出滿足的結果 500 條。
★調用Hits的doc()方法，(Vector): hitDocs.size()=100★檢索到的Hit的ID為 ： 0
★調用Hits的doc()方法，(Vector): hitDocs.size()=100★檢索到的Hit的ID為 ： 1
★調用Hits的doc()方法，(Vector): hitDocs.size()=100★檢索到的Hit的ID為 ： 2
……
★調用Hits的doc()方法，(Vector): hitDocs.size()=100★檢索到的Hit的ID為 ： 98
★調用Hits的doc()方法，(Vector): hitDocs.size()=100★檢索到的Hit的ID為 ： 99
★調用Hits的doc()方法，(Vector): hitDocs.size()=100■■■■■■■■■■■■■■■■■■■■■■■■進入getMoreDocs()方法中時，hitDocs.size=100
■■■■■■■■■■■■■■■■■■■■■■■■離開getMoreDocs()方法中時，hitDocs.size=200
★檢索到的Hit的ID為 ： 100
★調用Hits的doc()方法，(Vector): hitDocs.size()=200★檢索到的Hit的ID為 ： 101
★調用Hits的doc()方法，(Vector): hitDocs.size()=200★檢索到的Hit的ID為 ： 102
……
★調用Hits的doc()方法，(Vector): hitDocs.size()=200★檢索到的Hit的ID為 ： 198
★調用Hits的doc()方法，(Vector): hitDocs.size()=200★檢索到的Hit的ID為 ： 199
★調用Hits的doc()方法，(Vector): hitDocs.size()=200■■■■■■■■■■■■■■■■■■■■■■■■進入getMoreDocs()方法中時，hitDocs.size=200
■■■■■■■■■■■■■■■■■■■■■■■■離開getMoreDocs()方法中時，hitDocs.size=400
★檢索到的Hit的ID為 ： 200
★調用Hits的doc()方法，(Vector): hitDocs.size()=400★檢索到的Hit的ID為 ： 201
★調用Hits的doc()方法，(Vector): hitDocs.size()=400★檢索到的Hit的ID為 ： 202
……
★調用Hits的doc()方法，(Vector): hitDocs.size()=400★檢索到的Hit的ID為 ： 398
★調用Hits的doc()方法，(Vector): hitDocs.size()=400★檢索到的Hit的ID為 ： 399
★調用Hits的doc()方法，(Vector): hitDocs.size()=400進入getMoreDocs()方法中時，hitDocs.size=400
離開getMoreDocs()方法中時，hitDocs.size=500
★檢索到的Hit的ID為 ： 400
★調用Hits的doc()方法，(Vector): hitDocs.size()=500★檢索到的Hit的ID為 ： 401
★調用Hits的doc()方法，(Vector): hitDocs.size()=500★檢索到的Hit的ID為 ： 402
……
由結果可見看到，構造一個Hits的實例的時候，調用getMoreDocs()方法。
第一次進入getMoreDocs()方法時，hitDocs.size() = 0 > min = 50不成立，接著n = min*2 = 50*2 = 100，因此離開getMoreDocs()方法時hitDocs.size() = 100；
第二次進入getMoreDocs()方法時，hitDocs.size() = 100 > min = 50成立，從而設置min = hitDocs.size() = 100，接著n = min*2 = 100*2 = 200， 因此離開getMoreDocs()方法時hitDocs.size() = 200；
第三次進入getMoreDocs()方法時，hitDocs.size() = 200 > min = 100成立，從而設置min = hitDocs.size() = 200，接著n = min*2 = 200*2 = 400， 因此離開getMoreDocs()方法時hitDocs.size() = 400；
如果滿足查詢的檢索結果的Document數量足夠大的話，應該繼續是：
第四次進入getMoreDocs()方法時，hitDocs.size() = 400，離開getMoreDocs()方法時hitDocs.size() = 800；
第五次進入getMoreDocs()方法時，hitDocs.size() = 800，離開getMoreDocs()方法時hitDocs.size() = 1600；
……
根據上面，最后一次(第四次)進入getMoreDocs()方法的時候，hitDocs.size() = 400 > min = 400不成立，接著n = min*2 = 400*2 = 800，此時雖然緩存擴充了，但是執行searcher.search(weight, filter, n) 的時候取到了100條滿足條件的Document，故而緩存的實際大小為hitDocs.size() = 500， 因此離開getMoreDocs()方法時hitDocs.size() = 500，其實此次如果滿足查詢的Document數量足夠，可以達到hitDocs.size() = 800。
浙公網安備 33010602011771號