scala BitSet实现算法：一千万个随机数，随机数范围在1到1亿之间，现在要求写出一种算法，将1到1亿之间没有出现的随机数求出来

闲话

跟BitSet缠了好几天，书上介绍的甚少，过了好几遍文档，和java的BitSet相比，可以像Set一样地操纵的设计更合理，但总觉得少了很多有用的方法，和其他Set相比，可能大数据量时效率提升明显，但使用者很难接触到底层的结构（java的BitSet并没有这样），很难作用最大化，曾无数次给我一种用了假BitSet的感觉，所以说的不对的，还请大家不吝赐教！

从实例出发

实现算法：一千万个随机数，随机数范围在1到1亿之间，现在要求写出一种算法，将1到1亿之间没有出现的随机数求出来

Version 1 最简单的实现

没有考虑大数据集的问题，效率可想而知

var bit:BitSet=BitSet() var bat:BitSet=BitSet() for(i<-1 to 100){ bit+=i } for(i<-1 to 10 ){ bat+=(new Random).nextInt(100)//随机数没要求是不重复的 } val c:BitSet=bit--bat println(c)

Version 2 速度最快，但不准确

并行计算的效率让我欣喜若狂（超级快），但在这里出现了最多的问题，有些甚至至今仍未解决

var bit: BitSet = BitSet(100000000) var bat: BitSet = BitSet() (1 to 100000000).par.foreach(i => { // println(i) //问题一：这个地方导致了放弃这种方式，有并行，速度很快，但是不准确 //神奇，并行得到的结果是不全的，丢失了部分数据，但在这做个打印，就不会丢失任何数据(测试了一下，挪动这个打印的位置到在后面都不行) //小数据集数据丢失明显，越大数据集越不明显，所以断定速度是真的提升，跟数据丢失关系不大 bit += i }) // 问题二：简直神奇！！当初始化bitset时为空时，最后这个括号和大括号在同一行就会报错,注释接在括号后面也会报错！！ // Multiple exceptions thrown during a parallel computation 是ArrayIndexOutOfBoundsException // 初始化bit时加上100000000后不再报错，粗略测试了一下，加100000以上的数字都不再报错，小的数字不行，怀疑和初始化有关，但BitSet不是能自动扩容的吗，可能和超大数据量有关 //下面这个循环有循环有同样的问题，所以我将结尾的括号和大括号放在不同行 (1 to 100000000).par foreach (i => { bat += (new Random).nextInt(10) //随机数没要求是不重复的 } ) val res: BitSet = bit -- bat println("随机数中没有出现的数字集合：" + res)

Version 3

其实是在写出最终版之后尝试做的改进，之后我一直在考虑速度，尝试使用Stream，延时计算，但并没起到加速的作用

val ss = BitSet()#:: { c ++ (1 to 100000000).par.toList } #:: { b ++ (1 to 10000000).map(_ => Random.nextInt(99999999) + 1).toList }#::Stream.empty[BitSet] val r = ss(1) -- ss(2)

Version 4

更换了初始化的方式，但是更慢，可能是最终版的并行起到了作用

val s=BitSet((1 to 100000000):_*)

Version 5 最终版

准确，速度一般，在idea中正常运行一分钟左右

object work01 { def main(args: Array[String]): Unit = { time { var b: BitSet = BitSet() var c: BitSet = BitSet() //用较小数据集测试 // val bat = c++(1 to 10).par.toList // val bit = b ++ (1 to 5).map(_ => Random.nextInt(9) + 1).toList val bit = b ++ (1 to 1e8.toInt).map(_ => Random.nextInt(99999999) + 1).toList val bat = c ++ (1 to 1e8.toInt).par.toList //并没有要求随机数不重复 //只计算未出现的数字的数量 // val r=1e8.toInt-bit.size // println(r) //求出所有未出现的数字 val r: BitSet = bat -- bit // println(r) println(r.size) } } def time[R](block: => R): R = { val t0 = System.nanoTime() val result = block // call-by-name val t1 = System.nanoTime() println("Elapsed time: " + (t1 - t0) + "ns") result } }

用较小数据集测试多次，算法正确

若只求出数量，速度非常快（瞬间完成），因为此时只有千万级的数据量，而亿级数据，速度明显变慢，过亿的数据量让BitSet有些棘手

完整地跑了一下亿级数据，时间1分6秒左右，在这只打印了数量，所求数字的集合已经求出只是没打印出来

尾语

无论是scala还是BitSet，我对他们的学习都将不会停止，和java相比scala的确让代码量大大减少，但函数是一等公民的思想也让代码的写和读变得困难，目前我看scala还是一团乱麻，不过我觉得它会慢慢变得有趣的