这是一个创建于 3903 天前的主题，其中的信息可能已经有所发展或是发生改变。
有20个以上的文件，每个文件1G，每个文件内容都是：
姓名 电话
他们都没有规律的存在文件当中，而且不重复。
要求写一段程序，可以对这些文件进行任意时间的预处理，重新组织他们，要求用户在程序中输入一个人的名字，返回对应的电话号码，搜索时间自然是越短越好了
请问有什么思路吗？
====================
自己测试了下，用mockaroo.com生成了一个里面有100000条记录的单文件，也才2.3M，似乎这个数量多得可怕，其实用什么神奇的外排序以后，要短时间找到指定记录似乎也很难吧？
附上20个测试文件，当然是2.3M的每个，1G的实在弄不出来了……
https://www.dropbox.com/sh/ouw5obag5dq257l/AF7g4xniMb
姓名 电话
他们都没有规律的存在文件当中，而且不重复。
要求写一段程序，可以对这些文件进行任意时间的预处理，重新组织他们，要求用户在程序中输入一个人的名字，返回对应的电话号码，搜索时间自然是越短越好了
请问有什么思路吗？
====================
自己测试了下，用mockaroo.com生成了一个里面有100000条记录的单文件，也才2.3M，似乎这个数量多得可怕，其实用什么神奇的外排序以后，要短时间找到指定记录似乎也很难吧？
附上20个测试文件，当然是2.3M的每个，1G的实在弄不出来了……
https://www.dropbox.com/sh/ouw5obag5dq257l/AF7g4xniMb
 |
1
iloahz 2014-03-18 18:47:50 +08:00  1
我试了一下，10000条“名字 12345678901”这样的记录在txt里大概是175kb，所以20G的文件大概也就是1198372571条记录。
如果你内存充足的话，就全放内存里面，然后来一个很简单的二分查找就可以搞定了。假设机器是普通的机械硬盘，取100m/s的读取速度，那么读入大概是三分钟多一点，然后要来一个排序，假设机器cpu一秒10^8条指令，目测这个过程大概在半小时左右。预处理到此为止。然后查询就来得快了，log级别，单次查询复杂度大概就30，随便秒出了。 如果你内存不充足，那就是建各种索引呗，这个我不是很熟。比如你可以根据第一个字将所有记录分类，然后第二个字，然后第三个字……这样每次在内存里的就只有一个字的索引表，这个就相当小了。这段胡扯不要在意。。。。 |
 |
2
yangff 2014-03-18 19:18:27 +08:00 1
1）排序每个文件，并分别输出。也就是先读入第一个文件（1g内存总放的下吧），然后直接sort排序后按顺序输出。
2）建立一个堆，从这20个文件里面各取出第一条记录，（记录，来自哪个文件）放进堆中。 3）取出堆顶部的记录，放到一个文件当中，然后看一下这个记录是从哪个文件来的，从那个文件中取出下一条记录，放入堆中重复这个过程直到所有记录被排序。 注意一下在放入文件的时候，将长度对其，比如说“某某 133xxxxxxxx”、“某某某某 133xxxxxxxx”之类的，长度不一样的串，在后面补充空格直到所有串都能够对其（也就是有相同的长度）。如果能二进制压一下就更好了。 现在你应该得到了一个排序后的文件，现在直接在这上面二分查找，用fseek直接定位到目标位置，因为记录的长度是固定的，这个位置可以直接计算得到。 另外最后这步其实可以优化的更好。 |
 |
3
ivanlw OP @yangff 感谢你的第三布，我想到的是每个文件排序后用理论上的N路归并排序，但是那样子代码的循环控制太复杂了（考虑到随时用完要取新的下一段记录）。还有几个问题：
1.有什么语言能比较方便的执行这些文件IO的操作呢？ 2.fseek是什么的东西？我搜到的是这个： http://www.cplusplus.com/reference/cstdio/fseek/，能不能给点其他关键字。 3.如果在排序后的那个文件（20G）里面搜，用你所说的fseek的方法的话，是不是不用把他们全部读进内存中？如果要全部读的话，肯定放不下的，希望你是有考虑到这点的。 |
|
4
yangff 2014-03-18 21:09:09 +08:00
@ivanlw
1）C++就行了。当然，一般正常的语言支持的IO功能也都足以实现，看你习惯哪个吧。 2）就是这个，fseek是用来在文件里面快速移动读取位置的（当然效率肯定不如内存了），因为你不能直接把整个文件读到内存里面，所以只能这样操作了。 3）当然系统不会一次把整个文件读进来。这样是可以直接操作文件指针到你所要读取的位置的，这也就是为什么之前要把记录的长度对其成一样的，就是为了方便fseek的操作。 不过fseek在32位系统上只支持2g文件的操作，所以可能要用到Windows下SetFilePointer+ReadFile，linux下我不是很清楚，似乎是要-D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64 http://stackoverflow.com/questions/14184031/what-is-the-difference-between-largefile-source-and-file-offset-bits-64 |
 |
5
pubby 2014-03-18 23:37:35 +08:00
如果在机械硬盘上操作，要考虑其特性做好适合的索引，仅仅排序的话未必做到最快，因为二分fseek还是会让磁头产生最多30多次随机定位，都知道随机读肯定不如顺序读
不考虑成本，排序后直接塞内存，大不了分多几台机器塞并发查就是了 |
 |
6
alexapollo 2014-03-19 01:34:27 +08:00
明显是hash啊，O(1)效率
|
|
7
ivanlw OP |
|
8
ivanlw OP @alexapollo 如果你指的是用编程语言内置的Hashset或者unordered_set，内存肯定放不下那么多东西；如果你要自己设计hash function映射到文件制定位置，希望给一个这样子的函数的方案，谢谢
|
 |
10
qoshi 2014-03-19 08:57:57 +08:00
约10^10条数据
可以进行两次哈希 内存中维护一张10^5次的表（这个不难） 其中每一个项映射一张10^5的表（硬盘中） 第一次hash找到对应表的位置，再进行一次hash，找到结果 done~~ |
|
11
ivanlw OP @qoshi 如果说第一个内存中维护的表可以理解成用HashSet或者<unordered_set>的话，可以理解得多来；但是请问第二个到硬盘的映射怎么具体实现呢，上面也好多个人就提了映射，哈希……
|
 |
12
roricon 2014-03-19 13:21:07 +08:00
能重新组织文件的话，把这写数据重新组织到不同文件夹下，文件夹按照
root/ -----/姓 --------/名第一字 --------------------/名第二字 --------------------------------/名最后一个字.txt --------/名第二字 txt里面保存电话号码…… 剩下效率的问题就交给系统了…… |
|
13
alexapollo 2014-03-19 20:48:10 +08:00
@ivanlw 排序，分区，多级hash
|
 |
15
yanpeipan 2014-03-20 14:25:02 +08:00
字典树
|
Select Language