需求：在做图库稳定性测试时，需要将斯坦福大学的社区网络图数据集顶点的去重导入到图库中。
去重方法：:
①在PC有限资源中实现（通过byte位置映射方式）,效率中等，文本主要是讲该方法。
②通过Spark mapreduce实现，效率高，实现简单，但需要spark环境。
③通过Hadoop mapreduce实现，效率较高，实现简单，但需要hadoop环境。
④将数据导入到数据库中，创建唯一索引，效率极低。
⑤将大文件才分若干个小文件，在小文件内去重，再将2个或多个小文件合并去重，以此类推（当文件中非重复内容很庞大时依然不能解决问题）。
⑥……
数据集下载地址：http://snap.stanford.edu/data/com-Friendster.html ，数据集解压后大概30GB左右。
Java基础知识
容量关系
//EB(艾字节)、PB(拍字节)、TB(太字节)、GB(千兆字节)、MB(兆字节)、KB(千字节)、Byte(字节)、bit(比特)
1EB=1024PB
1PB=1024TB
1TB=1024GB
1GB=1024MB
1MB=1024KB
1KB=1024Byte
1Byte=8bit位运算符
参考文章Java位运算
分析与实现
到这里我们对数据的二进制操作有了初步的认识，一个Byte字节是占8个比特的，一个bit是由0和1两个取值，那么可以通过0和1来表示某个值是否存在(既0:不存在,1:存在)。我们知道一个int值是占32(4*8)个bit的，那现在只需要一个1bit就能标示该值，一个int整整减少了31bit空间。假设要对4个int进行去重原来需要4*4=16Byte=128bit，当需要对32亿个int进行去重时原来需要32亿*4=128亿Byte=1028亿bit≈11.92GB，通过Byte数组+01标识方式只需要(32亿-31亿)*4=4亿Byte=32亿bit≈372MB, 前者需要的空间成本和时间成本远远超出想象。详解如下：例如，已知有个array数组，数组内容是{6,9,29,9},在byte字节数组中表示如下图：
要对数组进行去重就需要将各个数组的数值映射到byte数组的某个bit位上，用0或1来表示该卡位上是否存在数据，这里面就涉及到两个重要的变量index和position，index表示bytes数组的某个字节的索引，position表示在某个字节的哪个卡位。公式：
index = n / 8;//等于 n >> 3。eg:6/8=0,表示6在bytes[0]字节上
postion = n % 8;//等于n & 0x07。eg:6%8=6,表示在第6个卡位上无符号int
在Java语言中本身是不支持无符号整数（unsigned int）的，这里所说的无符号只是为了说明取值在[0-Integer.MAX_VALUE]的数值空间，因为该方式能更好的节约内存空间，如果你处理的数据没有负数，那么可以采用该方法。
完整代码:
/**
* 无符号Int BitMap，int取值[0,2147483647]
*
* @author Jianbo.Peng
* @date 2021/9/25 2:12 下午
*/
public class UnsignedIntBitMap {
private final byte[] bytes;
/**
* 根据maxInt创建BitMap
*
* @param maxInt 需处理的整数最大值
*/
public UnsignedIntBitMap(int maxInt) {
//计算所需的空间大小，其中+1是为0预留的
int spaceSize = calcByteSpace(maxInt) + 1;
this.bytes = new byte[spaceSize];
}
/**
* 赋值
*
* @param n
*/
public void setBit(int n) {
//计算bytes的index索引值
int index = n / 8;
//计算byte的卡位值
int position = n % 8;
//给index索引下的position卡位复制
//eg:position = 6,那么1 << position == 64,所以卡位上值是1
//bytes[index] 0 0 0 0 0 0 0 0
//1 << position 0 1 0 0 0 0 0 0
//| 0 1 0 0 0 0 0 0
//结果是1
bytes[index] |= 1 << position;
}
/**
* 判断是否存在
*
* @param n
* @return
*/
public boolean exist(int n) {
//计算bytes的index索引值
int index = n / 8;
//计算byte的卡位值
int position = n % 8;
//判断index索引和position卡位上的值是不是为1
return (bytes[index] & (1 << position)) != 0;
}
public boolean setBitNotExist(int n) {
boolean exist = exist(n);
if (exist) {
return false;
}
setBit(n);
return true;
}
/**
* 重置
*
* @param n
*/
public void reset(int n) {
//计算bytes的index索引值
int index = n / 8;
//计算byte的卡位值
int position = n % 8;
//清空index索引和position卡位的数据
//eg:position = 6,那么1 << position == 64
//bytes[index] 0 1 0 0 0 0 0 0
//~(1 << position) 1 0 1 1 1 1 1 1
//& 0 0 0 0 0 0 0 0
//结果是0
bytes[index] &= ~(1 << position);
}
/**
* 根据需要去重的最大的int值进行计算需要开辟多大的空间
*
* @param maxInt 所需的byte数量
* @return
*/
public int calcByteSpace(int maxInt) {
return maxInt / 8 + (maxInt % 8 > 0 ? 1 : 0);
}
public byte[] getBytes() {
return bytes;
}
}测试程序:
/**
* 简单的测试程序，主要是验证下代码没有问题
*/
@Test
public void testSimpleUnsignedIntBitMap() {
int arraySize = 10;
int maxIntVal = 5;
int[] array = new int[arraySize];
for (int i = 0; i < arraySize; i++) {
array[i] = randomInt(maxIntVal);
}
System.out.println("原数组：" + Arrays.toString(array));
UnsignedIntBitMap bitMap = new UnsignedIntBitMap(maxIntVal);
List<Integer> endResults = new ArrayList<>();
for (int val : array) {
boolean b = bitMap.setBitNotExist(val);
if (b) {
endResults.add(val);
}
}
System.out.println("处理后数组：" + endResults.toString());
}
/**
* 复杂测试
* @throws IOException
*/
@Test
public void testMagnitudeUnsignedIntBitMap() throws IOException {
//com-friendster.all.cmty.txt文件大概30GB左右
File file = new File("com-friendster.all.cmty.txt");
LineIterator iterator = FileUtils.lineIterator(file, "UTF-8");
File outFile = new File("target.txt");
//临时缓存，达到一定阈值，保存到文件中
List<String> cacheList = new ArrayList<>();
int cacheSize = 1000;
UnsignedIntBitMap bitMap = new UnsignedIntBitMap(Integer.MAX_VALUE);
long startDate = System.currentTimeMillis();
while (iterator.hasNext()) {
String line = iterator.nextLine();
if (!StringUtils.startsWith(line, "#")) {
String item[] = line.split("\t");
int num0 = Integer.parseInt(item[0]);
int num1 = Integer.parseInt(item[1]);
boolean b = bitMap.setBitNotExist(num0);
if (b) {
cacheList.add(item[0]);
}
b = bitMap.setBitNotExist(num1);
if (b) {
cacheList.add(item[1]);
}
if (cacheList.size() >= cacheSize) {
FileUtils.writeLines(outFile, cacheList, true);
cacheList.clear();
}
}
}
if (!cacheList.isEmpty()) {
FileUtils.writeLines(outFile, cacheList, true);
cacheList.clear();
}
System.out.println("处理耗时：" + (System.currentTimeMillis() - startDate));
}
private int randomInt(int maxIntVal) {
return new Random().nextInt(maxIntVal + 1);
}有符号int
有符号int相对无符号int所需的空间是乘2的，根据需求酌情选择。
完整代码：
/**
* 有符号Int BitMap int取值[-2147483648,2147483647]
*
* @author Jianbo.Peng
* @date 2021/9/25 2:12 下午
*/
public class IntBitMap {
private final byte[] bytes;
private int spaceSize;
private int midSpaceSize;
/**
* 根据maxInt创建BitMap
*
* @param maxInt 需处理的整数最大值,maxInt应该是Math.abs(maxInt)
*/
public IntBitMap(int maxInt) {
//正数和负数空间要乘2,其中+1是为0预留的
this.midSpaceSize = calcByteSpace(maxInt);
this.spaceSize = this.midSpaceSize * 2 + 1;
this.bytes = new byte[spaceSize];
}
/**
* 赋值
*
* @param n
*/
public void setBit(int n) {
//计算bytes的index索引值
int index = (n / 8);
//将要正数负数各占一半空间
index = (midSpaceSize + index);
//计算byte的卡位值
int position = n % 8;
//给index索引下的position卡位复制
//eg:position = 6,那么1 << position == 64,所以卡位上值是1
//bytes[index] 0 0 0 0 0 0 0 0
//1 << position 0 1 0 0 0 0 0 0
//| 0 1 0 0 0 0 0 0
//结果是1
bytes[index] |= 1 << position;
}
/**
* 判断是否存在
*
* @param n
* @return
*/
public boolean exist(int n) {
//计算bytes的index索引值
int index = n / 8;
//将要正数负数各占一半空间
index = (midSpaceSize + index);
//计算byte的卡位值
int position = n % 8;
//判断index索引和position卡位上的值是不是为1
return (bytes[index] & (1 << position)) != 0;
}
public boolean setBitNotExist(int n) {
boolean exist = exist(n);
if (exist) {
return false;
}
setBit(n);
return true;
}
/**
* 重置
*
* @param n
*/
public void reset(int n) {
//计算bytes的index索引值
int index = n / 8;
//将要正数负数各占一半空间
index = (midSpaceSize + index);
//计算byte的卡位值
int position = n % 8;
//清空index索引和position卡位的数据
//eg:position = 6,那么1 << position == 64
//bytes[index] 0 1 0 0 0 0 0 0
//~(1 << position) 1 0 1 1 1 1 1 1
//& 0 0 0 0 0 0 0 0
//结果是0
bytes[index] &= ~(1 << position);
}
/**
* 根据需要去重的最大的int值进行计算需要开辟多大的空间
*
* @param maxInt 所需的byte数量
* @return
*/
public int calcByteSpace(int maxInt) {
return maxInt / 8 + (maxInt % 8 > 0 ? 1 : 0);
}
public byte[] getBytes() {
return bytes;
}
}有符号long
排序
根据上文分析与实现可以得出数据存在bytes数组中本来就是有序的，只需遍历整个bytes数组，将卡位上数值为1数据去除即可。
方法1：
直接遍历bytes数组取byte卡位上的值，如果是无符号还需要考虑负数问题(这里就不阐述了)
List<Integer> sortList = new ArrayList<>();
for (int index = 0; index < bitMap.getBytes().length; index++) {
byte bVal = bitMap.getBytes()[index];
for (int position = 0; position < 8; position++) {
//boolean exist = ((bVal >> position) & 0x1) != 0; 与下一行代码等同
boolean exist = (bVal & (1 << position)) != 0;
if (exist) {
int val = index * 8 + position % 8;
sortList.add(val);
}
}
}
System.out.println("排序结果：" + sortList.toString());方法2：
已知maxIntVal值，循环检测exist是否存在值
List<Integer> sortList = new ArrayList<>();
for (int i = 0; i <= maxIntVal; i++) {
if (bitMap.exist(i)) {
sortList.add(i);
}
}
System.out.println("排序结果：" + sortList.toString());
2 条评论
::weibo:wb(26):: 写的不错~
讲得很清楚