不可思议的秒级文件处理算法？

Question

我现在有7个文件，大小分别为 2K,20K,200K,2M,20M,200M,2G
这些文件中的内容都是分行的（即一行一条数据）
不同的文件中可能存在相同的数据，比如 2K的文件中含有字符"abcdef" 200M的那个中也有"abcdef"
现在我需要将这些文件中不相同的内容（相同的部分只去一个，过滤掉重复的）全部整理到另外一个单独的文件中去，采用什么样的算法能够最快最高效！有没有可能在秒级完成？

Answer 1

换个问法，最高效的算法可以达到什么级别，
A 秒级别
B 分级别
C 2小时内
D 3小时内
E 3小时已经是最大忍耐限度了硬盘配置：
四核 AMD/或 I7
MEM  4G~8G
显卡 2G 带GPU

Answer 2

你要知道，你这种属于数据对比过程，不是什么算法问题，要提高速度除了优化数据结构以外，就是讲究合理的利用缓存与数据的读写方式，或者换个运行效率较高的开发工具来处理。
不说别的，就单纯的文件读写速度来说，读写数据的缓存大小设置因机器而已都会有不同，有些机器每次处理4K速度快，有些是8K，有些可能是2K。VB的运行效率本来就不高，也不是很适合做比较大量的数据对比工作，应为这会觉得很慢，虽然能做，不过效率要低过VC的几十倍。当然可以通过交互界面让人不感觉到这种过程有那么久，不过这种是实在没有办法的情况下用的招。如果说VB用相同的算法和过程要处理25秒，VC可能只需要800毫秒，这是我曾经测试的结果。你要提高效率，如果单纯是这种对比，建议用VC来做，如果不会VC，可以用VC写API函数给VB调用，其他的就是基本的循环判断语句或数组操作，花个几分钟就能了解C语言的这些东西。
给你介绍VC中API接口的处理方法，用这种VB+VC的架构应该能提高整个过程的处理速度。
http://blog.csdn.net/supermanking/article/details/5347763

Answer 3

sorry,C我也会的，我只是想多发几个板块寻求更多的信息

Answer 4

既然你会C语言，那干嘛不直接用C语言做个这种程序对比看看，看看实际需要多少时间不就可以了。相对来说，这种东西没什么算法可言，如果要说到算法，就是做字符串或是数据行的特征码来对比，在轮询每一个字节的过程中，计算那一行字符串的异或校检码或CRC码之类的东西，当读完一行，并取得那一行的校检码，就与先前的校检码数组做对比，如果不存在，就加入校检码数组，并做行标记，如果存在，在与先前相同校检码的行标记的行内容做具体对比，这种方法就有点像GIF文件格式的压缩数据方法，不过这种过程能不能起到缩短对比时间的作用要看数据的，搞不好还没有直接对比快。但总之，不去做是不知道结果如何的，这样的对比也不算很难，建议你做一个看看如果不能满足需求再问问题。

Answer 5

VB 加载300万行数据，最快需要7秒，用占内存的方法，一下子全部读入那种，如果上G，只有分段读了，再加比对，2G数据估计要几分钟

Answer 6

另外,关于硬件,有几个看法:
1.AMD 相对于Intel,CPU性能差太多.
2.显存大小对您的"算法"基本不搭界.
3.显卡貌似都是带GPU的.

Answer 7

你这个需求，应该说，还是有些算法技巧的。1.要查询两个分别有 n1 条记录和 n2 条记录的文件中记录的异同，则需要读取记录并进行比较的次数是 n1 x n2 次。如果你把这 7 文件两两比较，需要比较 n1 x n2 x n3 x n4 x n5 x n6 x n7 次。这是一个很大的数字。实际上，你可以首先把前 6 个小文件无条件合并，然后用合并的文件与最后一个大文件进行逐记录比较。注意，凡是不重复的数据，立即加入到大文件中。也就是说，下一次将参与比较。你需要的比较次数是 (n1 + n2 + n3 + n4 + n5 + n6) x n7。如果文件内部也可能有重复记录，稍麻烦一点。你需要检查大文件内部的重复记录。即，将大文件逐条写入临时文件时，逐条检查记录是否已存在于临时文件中。此时，你需要的比较次数是 (n1 + n2 + n3 + n4 + n5 + n6) x n7 x n7。2.VB 的字符串比较是很缓慢的。建议在 VC++ 中采用二进制字节逐个比较。一条记录不要无条件地比到底，只要发现了不相等的字节，立即返回。等等……

Answer 8

一般来说，VB : VC 程序执行花费的时间 5:4 左右是正常的，相差太大就是编程水平的问题了。大数据量的处理，必定要用到外存，看你机器内存足够，拿出 6G 用来做模拟硬盘。
1)将所有数据分成每份 1K 条记录，这 1K 条记录在内存中排序、去除重复项后分别存成文件到模拟硬盘。
2)然后不停用归并排序法（改进是需要去除重复项）将每 2 个文件合并成更大的文件，并删除原先的两个小文件。
3)最终一个大文件就是结果。
这样的算法耗时最多是分级别的。如果要利用4核CPU:
步骤 1) 中将小数据文件平分到 4 个目录中。
步骤 2) 同时运行 4 个程序实例分别处理一个目录。
步骤 3) 需要将 4 个文件再运用改进的归并排序法合并成最终结果。

Answer 9

Quote: 引用 11 楼 SupermanKing 的回复:

4核超线程技术，用云技术不是更好，呵呵

Quote:

云是狗屁：
云存储——不就网盘么
云服务——不就是在线更新么
云计算——普通应用 CPU 不是瓶颈。

Answer 10

对于目前较为普遍的个人电脑而言，要做到对上G的数据进行字符串分析还要达到秒级，这也叫普通应用？虽然我没有实际测试过，但从理论看，如果一台计算机分析2G以上的这种无规律字符串数据，相信处理时间怎么都不太少吧？如果把这些时间都摊开来让其他的计算机帮忙运算，肯定能提高效率。其实这和你介绍的超线程技术并无冲突，因为他们的理念是相同的，只不过在相同数量的超线程要比这种云架构高效而已，但云的优势就是数量多，在数量上可远超这种多核CPU的核心数，所以云技术并不是没有优势的。特别是在大量的数据任务运算中，更能体现云的价值，当然，如果做1000个循环这种小事也用云，肯定没法和这种超线程比，甚至比单线程还慢，因为云还要等网络信息的反馈等东西，但数据量一大，云端机一多，这种架构的运算效果就会远超这种单纯的超线程技术，毕竟云端也可超线程，云+超线程，可以想像是多么壮观的运算场面。

Answer 11

嘿嘿，2G文件，机械硬盘秒级是不可能了，必须是SATA3的固态硬盘。

Answer 12

嗯，如老虎所说，数据库是首选，可以利用全文索引或字典来提高速度。
其次，大文件夹不要直接读到内存中，要用内存映射方式+VB模拟指针来搜索，我以前曾经实验过，较大的文件使用内存映射+VB模拟指针的方式比直接使用VB内置命令快上近100倍，具体代码可参见我实验后写的一篇文章《VB快速查找大型文件中包含的字符串 》。