服务器之家

服务器之家 > 正文

海量数据去重排序bitmap(位图法)在java中实现的两种方法

时间:2021-07-16 14:32     来源/作者:gavenyeah

在海量数据中查找出重复出现的元素或者去除重复出现的元素是面试中常考的文图。针对此类问题,可以使用位图法来解决。例如:已知某个文件内包含若干个电话号码,要求统计不同的号码的个数,甚至在o(n)时间复杂度内对这些号码进行排序。

位图法需要的空间很少(依赖于数据分布,但是我们也可以通过一些放啊发对数据进行处理,使得数据变得密集),在数据比较密集的时候效率非常高。例如:8位整数可以表示的最大十进制数值为99999999,如果每个数组对应于一个bit位,那么把所有的八进制整数存储起来只需要:99mbit = 12.375mb.

实际上,java jdk1.0已经提供了bitmap的实现bitset类,不过其中的某些方法是jdk1.4之后才有的。

下面我先自己实现一下bitmap 的原理,然后再直接调用jdk的bitset类分别实现bitmap, 方便比较理解:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
package swordoffer;
//去除重复并排序
import java.util.arrays;
import java.util.bitset;
import java.util.random;
/**
 * @author gavenyeah
 * @date time:
 * @des:
 */
public class bitmap {
  int arrnum = 800;
  int len_int = 32;
  int mmax = 9999;
  int mmin = 1000;
  int n = mmax - mmin + 1;
  public static void main(string args[]) {
     new bitmap().findduplicate();
    new bitmap().finddup_jdk();
  }
  public void finddup_jdk() {
    system.out.println("*******调用jdk中的库方法--开始********");
    bitset bitarray = new bitset(n);
    int[] array = getarray(arrnum);
    for (int i = 0; i < arrnum; i++) {
      bitarray.set(array[i] - mmin);
    }
    int count = 0;
    for (int j = 0; j < bitarray.length(); j++) {
      if (bitarray.get(j)) {
        system.out.print(j + mmin + " ");
        count++;
      }
    }
    system.out.println();
    system.out.println("排序后的数组大小为:" + count );
    system.out.println("*******调用jdk中的库方法--结束********");
  }
  public void findduplicate() {
    int[] array = getarray(arrnum);
    int[] bitarray = setbit(array);
    printbitarray(bitarray);
  }
  public void printbitarray(int[] bitarray) {
    int count = 0;
    for (int i = 0; i < n; i++) {
      if (getbit(bitarray, i) != 0) {
        count++;
        system.out.print(i + mmin + "\t");
      }
    }
    system.out.println();
    system.out.println("去重排序后的数组大小为:" + count);
  }
  public int getbit(int[] bitarray, int k) {// 1右移 k % 32位 与上 数组下标为 k/32 位置的值
    return bitarray[k / len_int] & (1 << (k % len_int));
  }
  public int[] setbit(int[] array) {// 首先取得数组位置下标 i/32, 然后 或上
                    // 在该位置int类型数值的bit位:i % 32
    int m = array.length;
    int bit_arr_len = n / len_int + 1;
    int[] bitarray = new int[bit_arr_len];
    for (int i = 0; i < m; i++) {
      int num = array[i] - mmin;
      bitarray[num / len_int] |= (1 << (num % len_int));
    }
    return bitarray;
  }
  public int[] getarray(int arrnum) {
    @suppresswarnings("unused")
    int array1[] = { 1000, 1002, 1032, 1033, 6543, 9999, 1033, 1000 };
    int array[] = new int[arrnum];
    system.out.println("数组大小:" + arrnum);
    random r = new random();
    for (int i = 0; i < arrnum; i++) {
      array[i] = r.nextint(n) + mmin;
    }
    system.out.println(arrays.tostring(array));
    return array;
  }
}

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对服务器之家的支持。如果你想了解更多相关内容请查看下面相关链接

原文链接:https://blog.csdn.net/y999666/article/details/51220833

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
2021德云社封箱演出完整版 2021年德云社封箱演出在线看
2021德云社封箱演出完整版 2021年德云社封箱演出在线看 2021-03-15
返回顶部