返回顶部

收藏

使用布隆过滤算法进行排序

更多

使用布隆过滤算法进行排序

[说明]

如果不妥或者遗漏之处,欢迎大家批评指正。

[Java]代码

package com.test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

/**
 * 使用布隆过滤算法进行排序
 * 
 * 算法细节参见《编程珠玑》 或者《数学之美》
 * 
 * 问题描述:
 * 有n个不重复的正整数,用布隆过滤算法进行排序。
 * 
 * 算法优点:
 * 1.速度快 O(n)
 * 2.占用空间少
 * 缺点:
 * 1.只能对正整数排序
 * 2.不能对含有重复值的序列进行排序,含重复值的排序后只会出现一次,可以结合使用map来记录出现多次的情况
 * 
 * @author 乔学士
 *
 */
public class BloomFilterTester {

    /**
     * 生成n个不重复的数据 (范围是0-100*n)
     * @param n
     * @return
     */
    public static List<Integer> generateList(int n){
        List<Integer> list = new ArrayList<Integer>(n);
        Random rand  =  new Random();
        for(int i=0; i<n; i++){
            int num = rand.nextInt(100*n);
            while(list.contains(num)){
                num =rand.nextInt(100*n);
            }
            list.add(num);
        }
        return list;
    }

    public static void main(String[] args) {
        int n = 10000;
        List<Integer> list = BloomFilterTester.generateList(n);

        //Bloom Filter 排序
        //在java中boolean占一个字节而不是一个位  其实用一个位来表示最好
        //这里方面起见用boolean来模拟位。(true表示1 false表示0)
        boolean[] bitVector = new boolean[n*100];//因为生成的数据范围是从0-100*n,所以要把位向量设置为100*n的大小。

        for(int num : list){
            bitVector[num-1]=true; //把位向量里的第(下标-1)个元素的值设置为1(true)
        }

        //新new一个list,存放从filter中得到的数据,方便跟list进行比较
        List<Integer> newList = new ArrayList<Integer>(n); 
        for(int i = 0 ; i < bitVector.length; i++){
            if(bitVector[i]){
                newList.add(i+1); //如果向量的某一位是1(true),则把下标+1放到newList中
            }
        }

        //使用Collections里的sort方法对list进行排序,并逐个与newList中的数据进行比较。
        Collections.sort(list); 
        System.out.println(list.equals(newList)?"排序成功":"排序失败");

    }

}

标签:排序

收藏

0人收藏

支持

0

反对

0

发表评论