大家有什么好办法么？
现在有100M条数据，每条数据都固定长度，占100字节，它们放在一个10G的文件A中，并且这100M条数据都不相同。对每一条数据都已经生成了一个KEY，它们的长度也都是100个字节，一一对应的放在另一个10G的文件B中，在这些KEY中，有大约有20%是相同的。现在要完成的任务是：将A中对应KEY不同的数据提出来，生成一个文件C（长度大约是8G），就是说：如果A中的两条数据对应相同的KEY，那么就只记录A中先出现的数据，放弃A中较后面出现的数据。对输出文件C中的数据顺序没有要求。也可以放松一点要求，就是在C中偶尔可以有KEY重复的数据（比如说要求重复的数据不超过100条，赫赫），但是不容许丢掉应有的数据。假定我们使用一台普通台机，比方说4G内存、500M硬盘、双核、XP。大家讨论一下，这个任务可以在2个小时内完成么？大家的程序大约要运行多长时间呢？
我编程试了一下，发现程序很耗时，我不知道改进的空间有多少。不知道大家原先有没有遇到类似的问题。 我觉得先对文件B中数据进行排序(当然需要用到外部排序,比如归并排序).排序过程中在数据中添加每个数据的原先序号.
然后,对于所有KEY相同的数据,只保留第一个序号.然后对所有序号再次排序.然后根据这个序号序列,产生C 谢谢mathe的回复。
我就是将B进行归并排序的。我没有直接移动数据，我的算法相当于：1、建立了100M个长度为1的链表。2、合并相邻的链表（即：2i和2i+1的链表），如果有重复的数据，就直接在链表中删除。3、重复第2步，直到合成1个链表。4、依据链表和文件A生成文件C。
我的链表也存在文件中（一个文件记录了所有链表的头（8*50M，我是从长度为2的链表开始的），一个记录了全部链表（8*100M）），但是程序太慢了。随着链表数量减少和长度增加，第2步也越来越慢，可能是我用了过多的_fseeki64的缘故。结果是我无法实现目标。我在排序过程中的比较算法，已经尽量使得KEY在文件B中就比较有序，以此来减少链表的来回跳跃，但是改善不大。
我不知道如何进行较大的优化呢。不知道大家有没有做过类似的事情。 我觉得直接移动B中数据可能会更加好一些.不然需要对B中数据大量的随机访问,太慢了一些.
还有一种方法可以对B中数据再次进行Hash,比如产生10000个左右的Hash值,讲所有Hash值相同的数据先写到同一个文件,然后对这10000个文件中数据各自进行排序 直接移动B中的数据，在归并时是要插入数据的。另一方面B的数据较长呢，而且用快速排序还要额外的开销，所以一直没有试快速排序。
提到的Hash的方法有一个问题，就是如果将Hash值相同的数据写到同一个文件，是要同时打开10000个文件么？还是将文件B扫描10000次呢？将10G的文件扫一遍是秒的量级，这样2小时左右就难以完成了。 排序B时候同时排B,A数据就可以了
然后进行对A紧缩操作 一个文件就有10G，500M硬盘怎么够？ 应该是500G硬盘.
我觉得同时打开10000个文件应该还是可行的,如果机器有4G的内存,这个不是很大的压力 放入DB，再select distinct
如非要自己编，可模拟这一过程：先做个B*树索引，然后再遍历树选取数据
实现树的层次不大于7层。另外，建索引时顺便将原文件分成小块，以便于遍历时检索 sqlldr 导入数据库
create table c as select a.* from a,b where a.id=b.id and ...
页:
[1]