游戏编程精粹学习 - 使用Bloom过滤来提高计算性能(BloomFilter)

原文在《游戏编程精粹2》的1.2中，BloomFilter是一种可以快速检测是否存在集合包含关系的数据结构，但有一定的误识别率。

该结构的优点

判断包含关系时效率较高，粗略测试了下比List快一倍(不拆分哈希)
由于内部是位数组BitArray，做交集并集几乎不产生开销

该结构的缺点

有一定的误识别率
使用情境有限

我在Github找了一个BloomFilter的库(这个库使用时会产生大量GC,但学习来用够了)：

https://github.com/joeyrobert/bloomfilter

首先构建一个长度为N的位数组，将传入数据的哈希值按位拆分成不同段，每一个段作为一个Key放入这个长度为N的位数组。

判断包含时再把对象的多个key与位数组进行比较即可。

当然既然都存在误判率，而且是以效率为优先的话，也可以不按位拆分哈希，我写了一个最简单的版本:

public class MyBloomFilter<T>

{

    BitArray mBitArray;

    public MyBloomFilter(int bitLength)

    {

        mBitArray = new BitArray(bitLength);

    }

    public void Add(T obj)

    {

        var key = Mathf.Abs(obj.GetHashCode()) % mBitArray.Length;

        mBitArray[key] = true;

    }

    public bool Contains(T obj)

    {

        var key = Mathf.Abs(obj.GetHashCode()) % mBitArray.Length;

        return mBitArray[key];

    }

}

注意C#已经内置了位数组这样的数据结构BitArray。

结合之前的可预测随机数(http://www.cnblogs.com/hont/p/8716586.html)，我写了这样一个例子

假设这是一个草药采集的功能，每一个不同颜色的方块代表一颗草药

鼠标点击来采集它们。

代码如下

using System.Collections.Generic;

using UnityEngine;

public class HerbGenerator : MonoBehaviour

{

    public int x;

    public int y;

    public int probability = ;

    List<HerbObject> mCreatedHerbList = new List<HerbObject>();

    MyBloomFilter<int> mCollectedHerbList = new MyBloomFilter<int>();

    void Update()

    {

        GetArea(x - , y - , x + , y + );

        if (Input.GetMouseButtonDown())

        {

            var hit = default(RaycastHit);

            var isHit = Physics.Raycast(Camera.main.ScreenPointToRay(Input.mousePosition), out hit);

            if (isHit)

            {

                var herbObject = hit.transform.GetComponent<HerbObject>();

                mCollectedHerbList.Add(herbObject.seed);

                Destroy(hit.transform.gameObject);

            }

        }

    }

    void GetArea(int beginX, int beginY, int endX, int endY)

    {

        for (int i = ; i < mCreatedHerbList.Count; i++)

        {

            if (!mCreatedHerbList[i]) continue;

            Destroy(mCreatedHerbList[i].gameObject);

        }

        var cacheState = Random.state;

        mCreatedHerbList.Clear();

        float spacingScale = 1f;//增加间距防止两颗草药同时消失.

        for (int x = beginX, k = ; x < endX; x++)

        {

            for (int y = beginY; y < endY; y++, k++)

            {

                var seed =  + x + y * (endX - beginX);

                if (mCollectedHerbList.Contains(seed)) continue;

                Random.InitState(seed);

                var r = (int)(Random.value * );

                if (r %  < probability)

                {

                    var cube = GameObject.CreatePrimitive(PrimitiveType.Cube);

                    var herbObject = cube.AddComponent<HerbObject>();

                    herbObject.seed = seed;

                    cube.transform.position = new Vector3(x * spacingScale, , y * spacingScale);

                    GalaxyBuild(r, cube);

                    mCreatedHerbList.Add(herbObject);

                }

            }

        }

        Random.state = cacheState;

    }

    void GalaxyBuild(int seed, GameObject go)

    {

        var cacheState = Random.state;

        Random.InitState(seed);

        var meshRenderer = go.GetComponent<MeshRenderer>();

        switch ((int)(Random.value *  % ))

        {

            case ://草药类型1

                meshRenderer.material.color = Color.red;

                break;

            case ://草药类型2

                meshRenderer.material.color = Color.blue;

                break;

            case ://草药类型3

                meshRenderer.material.color = Color.green;

                break;

        }

        Random.state = cacheState;

    }

}

HerbGenerator

出现误判时会发生A草药采完后B草药同时消失的情况，只能增加草药刷新的间距来缓解这个问题。

巴特西

游戏编程精粹学习 - 使用Bloom过滤来提高计算性能(BloomFilter)

该结构的优点

该结构的缺点

最新文章

热门文章