大数据url 去除重复

前天接到电话面试，有一个url 去除重复的问题，场景大概是：

公司获取了大量url,肯定是超过内存了，按行存放，现在目的想剔除重复的数据

比如：一个5G 的txt 文件，url 一行一行的存放，而我们的内存只限制1G

 

我当时首先考虑分拆文件，然后hash,然后想排序比较，当时没想到好的办法，这里先说第一种：

 

方案一：

1.拆分文件，A B C D E，

   条件：

  1.保证每个文件读取小于内存限制1G,这样会分成5个文件

  2.拆分的时候，按行读取，可以用TreeSet 集合去除重复，并且并且排序，然后在接近内存容量的时候输出到文件

  结果：分割成5个左右的1G，并且排好序，且单个文件url不重复

   

 

2 . 这时候获得的文件，我们可以假设内容为，数字代替url

        A         B           C      D     E

        2         4            2      6     17

        4         6            3     16     27

        6         8           4      26    37

        7         17          5     36     47

        9         24          6     46     57

        11        34         9     56     67

        12         44       11     66     77

       22         54        12     76     87

        42        64         22     86     97

 。。。。。。。。。。。。。。。。。略

 

这时候就行合并、排序，。因为都是都大到小，或者相反的顺序，因此可以从头开始读取，假设我们1G内存，只能装10W行 url.那么合并读取

 

执行：

     分别从读取A,B,C,D,E 第一行开始2,4,2,6,17，那么读取第一行之后，去重复，排序之后是：

     A1:2,4,6,17 

     这里的操作方式应该比较多，我选择的的是最小数优先的原则，第一次取值A1,已经选择，发现 2，是最小的，并且是从A，C 文件中诞生的，那么第二次选择 我会从A,C的第二行开始选择，分别是4,3.这里4会被踢出，3，保留，这是A1:2,3,4,6,17 

     

     因为3是从C提取的，然后从C的第三行开始，获得4，重复，然后继续获得5，然后放入

     A1:2,3,4,5,6,16

    这时候发现从C中获得的5 大于从A的第二行的4，以及B中获得的4.（这里要跟新每个文件最后一次读取过的值，方便比较），然后继续读取A,B下一行：6和6 ，踢出，继续下一行7，8。然后加入

    A1：2，3，4，5，6，7，8，17

    然后现在的7 大于 D中的6，就从D的下一行开始，获得16，然后同样的方式，重复的踢出，然后找到最小的值，从该值的下一行读取，知道A1文件 有1G，开始第二个文件

 

 

 思路：以文件行为单位，以最小的值，为方向，不断向下查找，重复就继续，否则添加，最后以相同的方式多个文件合并，最后就会形成不重复的，排序好的url 文件集合。当然这里可以像我一样选择多个文件同时进行，也可以选择 两个进行。

 

 

 

如果有N个内存或者服务器，那么可以分配进行，也就是说像管理员找书那样，将书分成很多部分，然后每一部分都由一个人负责查找，然后将结果送到中间的一个人进行处理，这样效率肯定是比较高的，这样的方式无论是查找，去重 都很 好，应该是分布式的应用，多个服务器运作，中间件通知反馈消息。

 

 

 

小结：

      1.整个思路可能没有动态的图，还有的模糊，有什么不好的地方，请大家指点，有更好的方法，欢迎大家推荐。

      2.这里用的Set的不存重复元素的特性，也是hash的比较，还有自带排序的功能，当然排序方式可以自己写，快排的效率很高，但是注意深度问题，无规则的数据很好。

      3.关于大数据的利用，目前没怎么接触，就自己鼓捣一些方法，也不知道效率如何，相信以后会加强这方面的学习的。

     

 

评论

7 楼 greemranqq 2014-02-13  

Darth-Panda 写道

greemranqq 写道

嗯，关于mapReduce 给我很多启示，像大文件数据，只要有不重复的数据超过内存了，那么必然就存在文件分割，但是我从bitmap 中得到的启示是：我们建一个内存放下的超大数组（默假设从0到100W），里面用0,1表示元素的存在与否，然后像hashMap 那样进行对内容进行hash,然后很据值（比如hashCode = 12345）,将数组12345 这个位置设为1，那么存放的内容较少，能节省一部分空间。然后剩余的部分继续用同样的数组，只是位置从100W-200W，区间自己定义，有点类似我的 大数据实战二 的练习，这样可以减少一部分IO的工作量。

说实话没看懂……0-100W应该是不够用的，比如MD5，结果是一个32位整数，超过100W很容易，这个时候该怎么处理？

0~100W 是一个数组，相当于100W个格子，当然这个区间跟内存大小等自己设置。我先假设有一个区间，里面有100W个格子，第一轮默认存放 hashCode 为1~100W的值， 比如我字符串A，计算的hashCode = 999，那么我会将第999的格子里面放入1，表示已经有了，当另一个字符串B出现，并且计算的hashCode 也等于 999，我发现那个格子有值了，表示重复了。第一次匹配 就将hashCode 在0~100W 这个区间的所有字符串踢出，并且去除重复，剩下的就是就存放100W-200W区间的数据，这样循环就行了，中间建还可以记录 最大的hashCode值，分布情况等，能空间区间不用重复劳动。

假设我10亿的数据，在极端的情况下，全不重复。因为我区间格子 比较存放的是1，能节约空间，那么就可以设置区间大一点，比如第一次 0~1亿，反正内存不超就行，那么第一次1亿数据就完成了，写入文件，然后继续这样操作。

如果在数据大量重复，比如10亿数据，其中有9亿重复，那么一次就能搞定。

这样的做法能节省内存空间，IO 的次数 看重复的几率。

6 楼 Darth-Panda 2014-02-13  

greemranqq 写道

嗯，关于mapReduce 给我很多启示，像大文件数据，只要有不重复的数据超过内存了，那么必然就存在文件分割，但是我从bitmap 中得到的启示是：我们建一个内存放下的超大数组（默假设从0到100W），里面用0,1表示元素的存在与否，然后像hashMap 那样进行对内容进行hash,然后很据值（比如hashCode = 12345）,将数组12345 这个位置设为1，那么存放的内容较少，能节省一部分空间。然后剩余的部分继续用同样的数组，只是位置从100W-200W，区间自己定义，有点类似我的 大数据实战二 的练习，这样可以减少一部分IO的工作量。

说实话没看懂……0-100W应该是不够用的，比如MD5，结果是一个32位整数，超过100W很容易，这个时候该怎么处理？

5 楼 greemranqq 2014-02-12  

Darth-Panda 写道

俺的解法：用fopen64读文件，lseek64读一行，每行做hash，N=hash(line)，N写到一个内存里的数据结构，可以用bitmap（2^32个整数最多占用0.5G内存），N对应的bit置1，随后把该行写进结果文件；如果有新行的N相同，会发现该bit已经置1了，所以可以丢弃掉。然后继续读下一行。这样会比较快。

没做过大数据，随便写写，陋见以博一笑。

嗯，关于mapReduce 给我很多启示，像大文件数据，只要有不重复的数据超过内存了，那么必然就存在文件分割，但是我从bitmap 中得到的启示是：我们建一个内存放下的超大数组（默假设从0到100W），里面用0,1表示元素的存在与否，然后像hashMap 那样进行对内容进行hash,然后很据值（比如hashCode = 12345）,将数组12345 这个位置设为1，那么存放的内容较少，能节省一部分空间。然后剩余的部分继续用同样的数组，只是位置从100W-200W，区间自己定义，有点类似我的 大数据实战二 的练习，这样可以减少一部分IO的工作量。

4 楼 Darth-Panda 2014-02-12  

Darth-Panda 写道

greemranqq 写道

Darth-Panda 写道

俺的解法：用fopen64读文件，lseek64读一行，每行做hash，N=hash(line)，N写到一个内存里的数据结构，可以用bitmap（2^32个整数最多占用0.5G内存），N对应的bit置1，随后把该行写进结果文件；如果有新行的N相同，会发现该bit已经置1了，所以可以丢弃掉。然后继续读下一行。这样会比较快。

没做过大数据，随便写写，陋见以博一笑。

bitmap 的想法很好，有例子发一个吗？  我在后面2篇文章里面有原始的代码，可以进行文件生成 和 测试，可以共同研究下，分析下各种方法的优劣啊

bitmap本质上还是uint数组，只不过在访问的时候需要把index映射为per bit的位置。这个解法的问题在于如果发生hash冲突时（意味着也许内容不同的行映射到同一个bit位了），会出错。如果采用更大范围的bitmap就超过了1G的内存上限。面试官多半会从这个角度质疑。

所以拆文件的做法会更稳妥些，比如把Hash值相同的行保存到临时文件里（这样可以保证重复的行一定会进入同一个文件）。根据bitmap处理完Hash值不同的其他行之后，逐个读取这些临时文件的内容，如果确实是重复的行就丢弃。坏处是增加了磁盘IO次数，效率会降低些。

其实本质上是个Map/Reduce问题，用hash函数把5G的源文件拆成若干个小文件（map过程），然后把这些hash值相同的临时文件做去重处理，最后把结果汇总（Reduce过程），这样面试官应该会满意些。

3 楼 Darth-Panda 2014-02-12  

greemranqq 写道

Darth-Panda 写道

俺的解法：用fopen64读文件，lseek64读一行，每行做hash，N=hash(line)，N写到一个内存里的数据结构，可以用bitmap（2^32个整数最多占用0.5G内存），N对应的bit置1，随后把该行写进结果文件；如果有新行的N相同，会发现该bit已经置1了，所以可以丢弃掉。然后继续读下一行。这样会比较快。

没做过大数据，随便写写，陋见以博一笑。

bitmap 的想法很好，有例子发一个吗？  我在后面2篇文章里面有原始的代码，可以进行文件生成 和 测试，可以共同研究下，分析下各种方法的优劣啊

bitmap本质上还是uint数组，只不过在访问的时候需要把index映射为per bit的位置。这个解法的问题在于如果发生hash冲突时（意味着也许内容不同的行映射到同一个bit位了），会出错。如果采用更大范围的bitmap就超过了1G的内存上限。面试官多半会从这个角度质疑。

所以拆文件的做法会更稳妥些，比如把Hash值相同的行保存到临时文件里（这样可以保证重复的行一定会进入同一个文件）。根据bitmap处理完Hash值不同的其他行之后，逐个读取这些临时文件的内容，如果确实是重复的行就丢弃。坏处是增加了磁盘IO次数，效率会降低些。

2 楼 greemranqq 2014-02-11  

Darth-Panda 写道

俺的解法：用fopen64读文件，lseek64读一行，每行做hash，N=hash(line)，N写到一个内存里的数据结构，可以用bitmap（2^32个整数最多占用0.5G内存），N对应的bit置1，随后把该行写进结果文件；如果有新行的N相同，会发现该bit已经置1了，所以可以丢弃掉。然后继续读下一行。这样会比较快。

没做过大数据，随便写写，陋见以博一笑。

bitmap 的想法很好，有例子发一个吗？  我在后面2篇文章里面有原始的代码，可以进行文件生成 和 测试，可以共同研究下，分析下各种方法的优劣啊

1 楼 Darth-Panda 2014-02-11  

俺的解法：用fopen64读文件，lseek64读一行，每行做hash，N=hash(line)，N写到一个内存里的数据结构，可以用bitmap（2^32个整数最多占用0.5G内存），N对应的bit置1，随后把该行写进结果文件；如果有新行的N相同，会发现该bit已经置1了，所以可以丢弃掉。然后继续读下一行。这样会比较快。

没做过大数据，随便写写，陋见以博一笑。