海量数据处理:查找重复元素

心已赠人 2022-05-22 05:14 249阅读 0赞

已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数?

本题最好的解决方案是通过使用位图法来实现,8位整数可以表示的最大十进制数值为99999999,如果每个数字对应于位图中的一个bit位,那么存储八位整数大约需要99Mbit,因为1Byte = 8bit,所以99Mbit折合成内存为99/8=12.375MB的内存,即可以只用12.375MB的内存表示所有8位数电话号码的内容.

import java.util.Random;
    
    /** * Created by 94829 on 2018-06-15. */ public class number {
        int ARRNUM = 100;
        int mmin = 10000000;
        int mmax = 99999999;
        int N = (mmax - mmin + 1);
        int BITS_PER_WORD = 32;
        int WORD_OFFSET(int b){
            return b/BITS_PER_WORD;
        }
    
        int BIT_OFFSET(int b){
            return b % BITS_PER_WORD;
        }
    
        void SetBit(int[]words,int n){
            n -=  mmin;
            words[WORD_OFFSET(n)]  |= (1 << BIT_OFFSET(n));
        }
    
        void ClearBit(int[]words ,int n){
            words[WORD_OFFSET(n)]&=~(1 << BIT_OFFSET(n));
        }
        boolean GetBit(int[]words,int n){
            int bit = words[WORD_OFFSET(n)]&(1 >>BIT_OFFSET(n));
            return bit != 0;
        }
        public void sort(){
            int i;
            int j;
            int arr[] = new int[ARRNUM];
            System.out.println("数组大小:"+ARRNUM);
            //用来存放位图,每一位对应mmin和mmax范围内的一个数
            int[]words = new int[1 + N/BITS_PER_WORD];
            int count = 0;
            Random r = new Random();
            //生成100个随机数存放在数组arr中
            for (j=0;j<ARRNUM;j++){
                arr[j] = r.nextInt(N);
                arr[j] += mmin;
                System.out.print(arr[j] + "  ");
            }
            System.out.println();
            for (j=0;j<ARRNUM;j++){
                SetBit(words,arr[j]);
            }
            System.out.println("排序后的a为:" );
            for (i=0;i<N;i++){
                if(GetBit(words,i)){
                    System.out.print(i + mmin+"   ");
                    count++;
                }
            }
            System.out.println();
            System.out.println("总个数为:"+count);
        }
    
        public static void main(String[] args){
            new number().sort();
        }
    }

![70][]

上例中,采用时间作为种子,产生了100个随机数,对这100个数进行位图法排序,进而找出其中重复的数据.

[70]: /images/20220522/de231ea0787b49ebb511203123d37481.png