两个1G左右的文件,文件中每行记录一个地址,现在想查找两个文件中重复的地址条目,有什么较好的方法吗?

2011-03-14 10:58:05

6 Answers

简单想了一下,感觉这样应该可行:
方便说明, 用A,B表示两个文件吧
用先遍历一遍A, Hash一把,把Hash到一起的放在一个文件里(比如有:产生了10000个文件), 文件内容标识一下: A:{原始内容}:行数

然后再遍历B, 同样的Hash, 类似处理, 只是内容标识修改为:B:{原始内容}:行数

然后依次遍历新产生的N个文件, 用大不了用HashMap搞定(当然Hash时做的足够好, 每个文件都比较小了)

2011-03-14 12:46:33

地址是纯数字记录的还是其他?

若是纯数字的话,且值均小于2^32-1,可以构造一个大数组array(int[Integer.SIZE],1G的数据足够保存),初始值为0.
首先遍历文件1:对于每次读取的地址,将数组对应位置的值增一。如地址为k,则array[k]++;

然后再遍历文件2:对每次读取的地址,判断数组中对应位置的值是否为零,即array[k]==0?若不为零,则说明文件1中存在该地址值。

要么就大文件排序,然后用归并去找重。

2011-03-14 14:26:36

上面的方法我觉得可能会有内存上的问题,如果高性能机肯定没问题。我说的也是使用Hash算法,使用Hash算法将上面的两个文件中的内容分隔成小的文件,然后再对每对小文件进行重复计算

2011-03-14 15:44:49
  1. 纯数字的话, @newcomer的回答很好, 但是可以更好一些:
    "若是纯数字的话,且值均小于2^32-1,可以构造一个大数组array(int[Integer.SIZE],1G的数据足够保存),初始值为0."
    --> 这里我们不用int数组, 而用 位图(bitmap)的 概念, 即用一个bit来表示对应的整数有没有出现过(注意我们不需要 计算重复此数, 只须知道有重复即可), 一个文件的bitmap: array(byte[Integer.MAX_VALUE/8]) = 256M. 下面的算法 和newcomer给出的差不多, 不多说了.

  2. 如果题中的"地址"指的是web地址, 就更方便了, 还是用hash. 我们来算一下, 假定一个url地址长度为30个字节(不算多吧), 那么一个文件差不多有30M 条记录. 每条记录hash到16字节, 因为hash空间足够大(2的128次方, 10的38次方级). 基本不用考虑碰撞了. 这样hash后结果为480m.

最后要说的是, 如果内存够大, 就把两个文件都做bitmap或hash后存入内存; 否则只保存一个文件的hash在内存, 顺序读出另一个文件条目, 与内存中的hash做比较.(类似Oracle的Hash Join).

2011-03-14 17:57:31

可以试试用哈希函数把每行记录转成数值,最后比较两个文件中有没有相同的数值。不过要注意碰撞问题。

2011-03-14 19:10:07

可以用java调用shell,先从第一个文件读出若干行,再从第二个文件读出相同的行数,将从两个文件读出的内容逐行进行比对,一直将第二个文件读完,循环这个过程直至比对完成。

2011-03-14 20:31:46
您不能回答该问题或者回答已经关闭!

相关文章推荐

  • C#中using指令的几种用法

    using + 命名空间名字,这样可以在程序中直接用命令空间中的类型,而不必指定类型的详细命名空间,类似于Java的import,这个功能也是最常用的,几乎每个cs的程序都会用到

  • C#实例解析适配器设计模式

    将一个类的接口变成客户端所期待的另一种接口,从而使原本因接口不匹配而无法在一起工作的两个类能够一起工作

  • 使用托管C++粘合C#和C++代码(二)

    本文实现一下C++代码调用C#代码的过程。我构造一个简单并且直观的例子:通过C++ UI 触发C# UI.

  • Async和Await使异步编程更简单

    C#5.0中async和await两个关键字,这两个关键字简化了异步编程,之所以简化了,还是因为编译器给我们做了更多的工作

  • C#开发高性能Log Help类设计开发

    项目中要在操作数据库的异常处理中加入写Log日志,对于商业上有要求,写log时对其它操作尽可能影响小,不能因为加入log导致耗时太多

  • C#开发中的反射机制

    反射的定义:审查元数据并收集关于它的类型信息的能力。元数据(编译以后的最基本数据单元)就是一大堆的表,当编译程序集或者模块时,编译器会创建一个类定义表,一个字段定义表,和一个方法定义表等

  • C#运行时相互关系

    C#运行时相互关系,包括运行时类型、对象、线程栈和托管堆之间的相互关系,静态方法、实例方法和虚方法的区别等等

  • C#协变和逆变

    “协变”是指能够使用与原始指定的派生类型相比,派生程度更大的类型,“逆变”则是指能够使用派生程度更小的类型

  • C#基础概念之延迟加载

    延迟加载(lazy load)是Hibernate3关联关系对象默认的加载方式,延迟加载机制是为了避免一些无谓的性能开销而提出来的,所谓延迟加载就是当在真正需要数据的时候,才真正执行数据加载操作

  • C#中的索引器的简单理解和用法

    C#中的类成员可以是任意类型,包括数组和集合。当一个类包含了数组和集合成员时,索引器将大大简化对数组或集合成员的存取操作

  • 使用托管C++粘合C#和C++代码(一)

    C#在xml读写,数据库操纵,界面构造等很多方面性能卓越;C++的效率高,是底层开发的必备武器

  • 深入C# 序列化(Serialize)、反序列化(Deserialize)

    C#中的序列化和反序列化,序列化是.NET运行时环境用来支持用户定义类型的流化的机制