大数据之初窥门径

  前段时间接触到一个基本的大数据的问题，十亿个整数查重。现实意义非凡，同类的商品，同样兴趣个体的筛选，相同频段的好友，各种在大数据时代里面的具象，仍然基于一个十亿个整数查重的基本问题。

  在java里面，int类型的数据从0-2的32次方个不同的数字，我们用一个2的32次方个位这么长的数组来映射所有int类型整数。因为数字总是逃不过这个范围，需求的空间是2的29次方个byte，因为java中只有byte数组来表示位，一个byte等于八个位所以2的32次方个数字转化成2的29次方个byte数组，总大小应该在内存的允许范围之内。

  对于问题的分析，需要对数据类型和问题具象的难点进行适当的算法设计，这样问题就会迎刃而解了。

  难点在于10亿个数字读入的时候，具体的数字到底怎么处理。如果你在纠结10亿个数字怎么存入内存中，那要跨过大数据的门槛，还要再加修行了。

  读入一个数字，它的特征，只有对于你设计的算法进行适当的处理，才能真正地处理掉。刚说了申请了一个2的29次方个byte数组，一个byte等于八个bit，也就是00000000。这个进来的数字，必须要以八为关键点进行分解。比如说进来一个数字是44，这个数字对于8来说是什么呢？5*8+4，这样的式子是不是有些启示。一个byte代表8个数字，从0-2的32次方对应于byte下标的0-2的29次方。44就是存在于byte[5]的第4位，注意：位是从第0位开始计数的。拿到一个数字之后，分解成需要的因子之后把相应的位置修改成1，第二次进来的时候检测到相应位为一，则这个数字重复了。输出一个。

   byte数组是有整数来呈现的，修改相应位置就是加个2的余数次方的整数，检测的时候再把byte变成二进制，创建一个8长度的int数组，只存0,1。作为验证。

  这个算法可能不是很优秀，但是对于处理大数据的入门思维有了一定的启发。

 

评论

2 楼 chentingk 2015-03-01  

Tbc1993 写道

以前胡哥讲这个的时候没怎么听懂，看了你这个还是觉得似懂非懂，注定不是做技术的啊  

never mind 只是个效率慢的算法

1 楼 Tbc1993 2014-11-20  

以前胡哥讲这个的时候没怎么听懂，看了你这个还是觉得似懂非懂，注定不是做技术的啊