ブール演算--javaビットマップ検索実装

14071 ワード
じっこうアルゴリズム
前言
ブール演算は偉大なブール発明の代数演算であり、簡単な論理と非しかなく、最初は役に立たなかったが、コンピュータへの影響が大きすぎて、インフラから検索エンジンまでどこにもいなかった.
シーン
私たちとして、日常の仕事の中で、私もその需要に直面しました.シーンは、変化が頻繁ではないため、ユーザーの複数の次元のマッチングに関連する複雑な構成があります.
毎回データベースを検索するのは明らかにお得ではありません.データ量も多すぎず、万未満のレベルで、人が配置していますか.これはとても自然で、サーバーのメモリにキャッシュしましょう、しかしいつも力の一つ一つのマッチングができないでしょう、うるさいです、効率もとても低くて、その上ロジックの判断は少し複雑で、配置は主に4つの次元です:機種、ルート、国家、バージョン、各次元はすべて1つの配列で、ある値は1つの["ALL"]で、意味はすべてマッチングします;
引用する
そこでブール演算を考えてみると、比較的簡単で、各値は長い数字のビットに対応して、何本のデータがあって、各次元の各値は最大何ビットですか.
合計10000個の構成であれば、「中国」に対応するビットベクトルは最大10000ビットであり、「中国」という値に対して、100ビット目が1であることは、100個目の構成がこの「中国」次元値を含むことを示す.照会国が「中国」であるのはmapから「中国」に対応するビットベクトルと「ALL」に対応するビットベクトルを取って演算することである.Javaは大きな整数の実現を持っています:BigInteger;構造方法にバイナリビットを表すbyte配列を渡すことができ、byte配列の長さは明らかに:(構成本数/8)+1であり、BigInteger内部では主に左の連続する0を除去する処理が行われる.
すぐに始まる
我々はMongoDBデータベースを使用しているため、操作はspring-dataによるmongodbのパッケージです.CriteriaとQueryのAPIがあり、これもspringの一貫したスタイルです.
そこで、共通のビットマップクエリーを実現し、CriteriaのAPIと似ています.これにより、コードの変更が小さくなります(import springのパッケージを自分のものに変えると、ほとんど終わりません).
まずテストcase(例は少しlowですが、見てみましょう):
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;

import org.junit.Assert;
import org.junit.Test;

import bitmapSearch.BitmapSearcher;
import bitmapSearch.Criteria;

public class BitmapSearchTest {

	@Test
	public void testQuery() {
		List cars = Arrays.asList(new Car(), //
				new Car("  ").setToAreas("ALL"), //
				new Car("   ", 3).setToAreas("   "), //
				new Car("   ", 6).setToAreas("  "));
		BitmapSearcher searcher = new BitmapSearcher(cars, new BitmapSearcher.IndexCreator() {
			@Override
			public String[] indexKeys() {
				return new String[] { "id", "brand", "legs", "toAreas", "desc" };
			}

			@Override
			public Object[] fieldValue(Car bean, String indexKey) {
				if ("id".equals(indexKey)) {
					return new Object[] { bean.id };
				} else if ("brand".equals(indexKey)) {
					return new Object[] { bean.getBrand() };
				} else if ("legs".equals(indexKey)) {
					return new Object[] { bean.getLegs() };
				} else if ("toAreas".equals(indexKey)) {
					return bean.getToAreas();
				}else if ("desc".equals(indexKey)) {
					return new Object[] { bean.getDesc() };
				}
				return null;
			}
		});
		Car rs1 = searcher.findOne(
				Criteria.where("legs").is(6)//
						.andOperator(new Criteria().orOperator(//
								Criteria.where("id").is(4), //
								Criteria.where("desc").is("MadeInChina")))//
				, null);//
		Assert.assertTrue(rs1.brand.equals("   "));
		List rs2 = searcher.find(Criteria.where("toAreas").in("  ", "ALL"));
		Assert.assertTrue(rs2 != null && rs2.size() == 2);
	}

	private static class Car {
		final int id;
		static AtomicInteger ID_GEN = new AtomicInteger();
		String brand = "QQ";
		int legs = 4;
		String[] toAreas;
		String desc = "";

		public Car() {
			super();
			id = ID_GEN.incrementAndGet();
		}

		public Car(String brand) {
			this();
			this.brand = brand;
		}

		public Car(String brand, int legs) {
			this();
			this.brand = brand;
			this.legs = legs;
		}

		public String getBrand() {
			return brand;
		}

		public void setBrand(String brand) {
			this.brand = brand;
		}

		public int getLegs() {
			return legs;
		}

		public void setLegs(int legs) {
			this.legs = legs;
		}

		public Car setToAreas(String... toAreas) {
			this.toAreas = toAreas;
			return this;
		}

		public String[] getToAreas() {
			return toAreas;
		}

		public String getDesc() {
			return desc;
		}

		public void setDesc(String desc) {
			this.desc = desc;
		}

	}
}

 
   
  
 其中，抽象一个内部类IndexCreator，把构造索引以及如何获取索引字段值的工作抛给用户 
  
  
/**
 * 
 */
package bitmapSearch;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 *          
 * 
 * @author HouKangxi
 *
 */
public final class BitmapSearcher {
	/**
	 *   list,  。
	 */
	@SuppressWarnings("rawtypes")
	private final List beansList;
	/**
	 *        : K: index, value:
	 */
	private Map> indexMap;
	/**
	 *      
	 */
	@SuppressWarnings("rawtypes")
	private final IndexCreator indexCreator;

	/**
	 *      
	 * 
	 *
	 *
	 * @param INDEX>
	 */
	public static interface IndexCreator {
		/**
		 *       
		 * 
		 * @return
		 */
		INDEX[] indexKeys();

		/**
		 *              
		 * 
		 * @param bean
		 *            - list    
		 * @param indexKey
		 *            -    
		 * @return
		 */
		Object[] fieldValue(T bean, INDEX indexKey);
	}

	/**
	 *     
	 * 
	 * @param objList
	 *            -   list
	 * @param ic
	 *            -      
	 */
	public  BitmapSearcher(List objList, IndexCreator ic) {
		indexCreator = ic;
		if (objList != null && objList.size() > 0) {
			beansList = Collections.unmodifiableList(objList);
			createAllIndex();
		} else {
			beansList = Collections.emptyList();
		}
	}

	Map getBitmap(Object key) {
		return indexMap.get(key);
	}

	/**
	 *       
	 * 
	 * @param 
	 * 
	 * @param criteria
	 *            -     
	 * @param sorter
	 *            -       
	 * @return
	 */
	public  T findOne(Criteria criteria, Comparator sorter) {
		List list = find(criteria);
		if (list == null || list.isEmpty()) {
			return null;
		}
		if (sorter != null)
			Collections.sort(list, sorter);
		//      
		return list.get(0);
	}

	/**
	 *    list
	 * 
	 * @param 
	 * @param criteria
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public  List find(Criteria criteria) {
		if (beansList == null || beansList.isEmpty()) {
			return null;
		}
		BigInteger bInt = criteria.proc(this, null);
		if (bInt == null) {
			return null;
		}
		ArrayList indexes = new ArrayList();
		int idx;
		while ((idx = bInt.getLowestSetBit()) >= 0) {
			indexes.add(idx);
			//         1   &  ，             1
			bInt = bInt.and(bInt.subtract(BigInteger.ONE));
		}
		//    indexes          ，     ，           1
		if (indexes.isEmpty()) {
			return null;
		}
		@SuppressWarnings("rawtypes")
		ArrayList rslist = new ArrayList(indexes.size());
                for (int i : indexes) {
		     rslist.add(beansList.get(i));
		}
		return rslist;
	}

	private void createAllIndex() {
		Map> t_Index = new HashMap>();
		Object[] keyNames = indexCreator.indexKeys();
		for (int i = 0; i < keyNames.length; i++) {
			t_Index.put(keyNames[i], new HashMap());
		}
		int i = 0;
		final int SUM = beansList.size();
		for (Object o : beansList) {
			createIndex(o, t_Index, SUM, i, keyNames);
			i++;
		}
		indexMap = new HashMap>(t_Index.size());
		bytes2BigInteger(t_Index, indexMap);
	}

	private void createIndex(Object o, Map> t_Index, final int SUM, final int index,
			Object[] indexes) {
		if (o == null) {
			return;
		}
		final int bytesLen = (SUM >> 3) + 1;
		final int byteIndex = bytesLen - 1 - (index >> 3);
		final int value = 1 << (index % 8);

		for (int i = 0; i < indexes.length; i++) {
			Object key = indexes[i];
			@SuppressWarnings("unchecked")
			Object fieldValues[] = indexCreator.fieldValue(o, key);
			if (fieldValues == null) {
				continue;
			}
			Map bIntMap = t_Index.get(key);
			for (Object fieldValue : fieldValues) {
				if (fieldValue != null) {
					byte[] bInt = bIntMap.get(fieldValue);
					if (bInt == null) {
						bIntMap.put(fieldValue, bInt = new byte[bytesLen]);
					}
					bInt[byteIndex] |= value;
				}
			}
		}
	}

	@SuppressWarnings("unchecked")
	private void bytes2BigInteger(Map> t_Index,
			Map> bigInts) {
		for (Map.Entry> entry : t_Index.entrySet()) {
			Object key = entry.getKey();
			Map value = entry.getValue();
			if (value == null || value.isEmpty()) {
				continue;
			}
			@SuppressWarnings("rawtypes")
			Map ov = value;
			for (Map.Entry v : value.entrySet()) {
				ov.put(v.getKey(), new BigInteger(v.getValue()));
			}
			bigInts.put(key, ov);
		}
	}

}

   
  
 
  
 
   
  
   Criteria      ：
 
   
   
/**
 * 
 */
package bitmapSearch;


import java.math.BigInteger;
import java.util.LinkedList;
import java.util.List;


/**
 *       
 * 
 * @author houkangxi
 *
 */
public class Criteria {
	protected Object key;


	protected List chain;
	private Criteria prev = this;


	public Criteria() {
		chain = new LinkedList();
	}


	public Criteria(Object key) {
		this();
		this.key = key;
	}


	Criteria(int noInitChain) {
	}


	public static Criteria where(Object key) {
		return new Criteria(key);
	}


	private Criteria addToChain(Criteria c) {
		prev = c;
		chain.add(c);
		return this;
	}


	public Criteria is(Object val) {
		prev.addToChain(new CriteriaOpIs(prev.key, val));
		return this;
	}


	public Criteria ne(Object val) {
		prev.addToChain(new CriteriaOpNot(prev.key, val));
		return this;
	}


	public Criteria in(Object... val) {
		prev.addToChain(new CriteriaOpIn(prev.key, val));
		return this;
	}


	public Criteria and(String key) {
		return addToChain(new CriteriaOpAnd(key));
	}


	public Criteria or(String key) {
		return addToChain(new CriteriaOpOr(key));
	}


	public Criteria andOperator(Criteria... o) {
		return addToChain(new CriteriaOpAnd(o));
	}


	public Criteria orOperator(Criteria... o) {
		return addToChain(new CriteriaOpOr(o));
	}


	BigInteger proc(BitmapSearcher sea, BigInteger prev) {
		if (chain == null) {
			return null;
		}
		BigInteger rs = prev;
		for (Criteria c : chain) {
			rs = c.proc(sea, rs);
		}
		return rs;
	}


	@Override
	public String toString() {
		return getClass().getSimpleName() + "@key=" + key;
	}
}
  
  
 
   
/**
 * 
 */
package bitmapSearch;

import java.math.BigInteger;
import java.util.Arrays;

/**
 * @author houkangxi
 *
 */
abstract class CriteriaChain extends Criteria {

	CriteriaChain(String key) {
		super(key);
	}

	CriteriaChain(Criteria[] list) {
		super(0);
		this.chain = Arrays.asList(list);
	}

	protected abstract BigInteger op(BigInteger o1, BigInteger o2);

	@Override
	protected final BigInteger proc(BitmapSearcher sea, BigInteger prev) {
		if (chain == null || chain.isEmpty()) {
			return null;
		}
		BigInteger h = chain.get(0).proc(sea, null);
		for (int i = 1; i < chain.size() && h != null; i++) {
			h = op(h, chain.get(i).proc(sea, h));
		}

	        return op(prev, h);
	}

}

  
  
 
   
/**
 * 
 */
package bitmapSearch;

import java.math.BigInteger;

/**
 * And （ ）  
 * @author houkangxi
 *
 */
class CriteriaOpAnd extends CriteriaChain {

	CriteriaOpAnd(String key) {
		super(key);
	}

	CriteriaOpAnd(Criteria[] list) {
		super(list);
	}

	@Override
	protected BigInteger op(BigInteger o1, BigInteger o2) {
		if (o2 == null || o1 == null) {
			return null;
		}
		return o1.and(o2);
	}
}
/**
 * 
 */
package bitmapSearch;

import java.math.BigInteger;
import java.util.Map;

/**
 * IN   
 * @author houkangxi
 *
 */
class CriteriaOpIn extends Criteria {
	Object[] colls;

	CriteriaOpIn(Object key, Object[] colls) {
		super(key);
		this.colls = colls;
	}

	@Override
	protected BigInteger proc(BitmapSearcher sea, BigInteger prev) {
		Map bitmap = sea.getBitmap(key);
		if (bitmap == null || colls == null) {
			return null;
		}
		BigInteger bit = null;
		for (int i = 0; i < colls.length; i++) {
			Object val = colls[i];
			BigInteger I = bitmap.get(val);
			if (I != null) {
				bit = bit == null ? I : bit.or(I);
			}
		}
		return bit;
	}
}
/**
 * 
 */
package bitmapSearch;

import java.math.BigInteger;
import java.util.Map;

/**
 * Is  
 * 
 * @author houkangxi
 *
 */
class CriteriaOpIs extends Criteria {
	private Object ov;

	CriteriaOpIs(Object k, Object ov) {
		super(k);
		this.ov = ov;
	}

	@Override
	protected BigInteger proc(BitmapSearcher sea, BigInteger prev) {
		Map bimap = sea.getBitmap(key);
		if (bimap == null) {
			return null;
		}
		return bimap.get(ov);
	}
}
/**
 * 
 */
package bitmapSearch;

import java.math.BigInteger;
import java.util.Map;

/**
 * NOT ( )  
 * @author houkangxi
 *
 */
class CriteriaOpNot extends Criteria {
	private Object ov;

	CriteriaOpNot(Object k, Object ov) {
		super(k);
		this.ov = ov;
	}

	@Override
	protected BigInteger proc(BitmapSearcher sea, BigInteger prev) {
		Map bimap = sea.getBitmap(key);
		if (bimap == null) {
			return null;
		}
		BigInteger b = bimap.get(ov);
		if (b == null) {
			return null;
		}
		return b.not();
	}
}
/**
 * 
 */
package bitmapSearch;

import java.math.BigInteger;

/**
 * Or （ ）  
 * @author houkangxi
 *
 */
class CriteriaOpOr extends CriteriaChain {

	CriteriaOpOr(String k) {
		super(k);
	}

	CriteriaOpOr(Criteria[] list) {
		super(list);
	}

	@Override
	protected BigInteger op(BigInteger o1, BigInteger o2) {
		if (o2 == null) {
			return o1;
		}
		if (o1 == null) {
			return o2;
		}
		return o1.or(o2);
	}
}
@Transactional注記個人概要
滝のロールレイアウト