一道预处理和搜索记录的题目……

• 请不要在回答技术问题时复制粘贴 AI 生成的内容

This topic created in 4471 days ago, the information mentioned may be changed or developed.

有20个以上的文件，每个文件1G，每个文件内容都是：
姓名电话
他们都没有规律的存在文件当中，而且不重复。
要求写一段程序，可以对这些文件进行任意时间的预处理，重新组织他们，要求用户在程序中输入一个人的名字，返回对应的电话号码，搜索时间自然是越短越好了
请问有什么思路吗？
====================
自己测试了下，用mockaroo.com生成了一个里面有100000条记录的单文件，也才2.3M，似乎这个数量多得可怕，其实用什么神奇的外排序以后，要短时间找到指定记录似乎也很难吧？
附上20个测试文件，当然是2.3M的每个，1G的实在弄不出来了……
https://www.dropbox.com/sh/ouw5obag5dq257l/AF7g4xniMb

文件

预处理

记录

16 replies • 1970-01-01 08:00:00 +08:00

iloahz

Mar 18, 2014

我试了一下，10000条“名字 12345678901”这样的记录在txt里大概是175kb，所以20G的文件大概也就是1198372571条记录。

如果你内存充足的话，就全放内存里面，然后来一个很简单的二分查找就可以搞定了。假设机器是普通的机械硬盘，取100m/s的读取速度，那么读入大概是三分钟多一点，然后要来一个排序，假设机器cpu一秒10^8条指令，目测这个过程大概在半小时左右。预处理到此为止。然后查询就来得快了，log级别，单次查询复杂度大概就30，随便秒出了。

如果你内存不充足，那就是建各种索引呗，这个我不是很熟。比如你可以根据第一个字将所有记录分类，然后第二个字，然后第三个字……这样每次在内存里的就只有一个字的索引表，这个就相当小了。这段胡扯不要在意。。。。

yangff

Mar 18, 2014

1）排序每个文件，并分别输出。也就是先读入第一个文件（1g内存总放的下吧），然后直接sort排序后按顺序输出。
2）建立一个堆，从这20个文件里面各取出第一条记录，（记录，来自哪个文件）放进堆中。
3）取出堆顶部的记录，放到一个文件当中，然后看一下这个记录是从哪个文件来的，从那个文件中取出下一条记录，放入堆中重复这个过程直到所有记录被排序。
注意一下在放入文件的时候，将长度对其，比如说“某某 133xxxxxxxx”、“某某某某 133xxxxxxxx”之类的，长度不一样的串，在后面补充空格直到所有串都能够对其（也就是有相同的长度）。如果能二进制压一下就更好了。

现在你应该得到了一个排序后的文件，现在直接在这上面二分查找，用fseek直接定位到目标位置，因为记录的长度是固定的，这个位置可以直接计算得到。

另外最后这步其实可以优化的更好。

ivanlw

Mar 18, 2014

@yangff 感谢你的第三布，我想到的是每个文件排序后用理论上的N路归并排序，但是那样子代码的循环控制太复杂了（考虑到随时用完要取新的下一段记录）。还有几个问题：
1.有什么语言能比较方便的执行这些文件IO的操作呢？
2.fseek是什么的东西？我搜到的是这个： http://www.cplusplus.com/reference/cstdio/fseek/，能不能给点其他关键字。
3.如果在排序后的那个文件（20G）里面搜，用你所说的fseek的方法的话，是不是不用把他们全部读进内存中？如果要全部读的话，肯定放不下的，希望你是有考虑到这点的。

yangff

Mar 18, 2014

@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

pubby

Mar 18, 2014

如果在机械硬盘上操作，要考虑其特性做好适合的索引，仅仅排序的话未必做到最快，因为二分fseek还是会让磁头产生最多30多次随机定位，都知道随机读肯定不如顺序读

不考虑成本，排序后直接塞内存，大不了分多几台机器塞并发查就是了

alexapollo

Mar 19, 2014

明显是hash啊，O(1)效率

ivanlw

Mar 19, 2014

@pubby
@alexapollo 能指点下怎么在硬盘上具体的建索引吗？没有这方面的经历

ivanlw

Mar 19, 2014

@alexapollo 如果你指的是用编程语言内置的Hashset或者unordered_set，内存肯定放不下那么多东西；如果你要自己设计hash function映射到文件制定位置，希望给一个这样子的函数的方案，谢谢

ivanlw

Mar 19, 2014

@yangff 前面是名字的话，没有长度范围，没办法对其吧？

qoshi

Mar 19, 2014

约10^10条数据
可以进行两次哈希
内存中维护一张10^5次的表（这个不难）
其中每一个项映射一张10^5的表（硬盘中）
第一次hash找到对应表的位置，再进行一次hash，找到结果
done~~

ivanlw

Mar 19, 2014

@qoshi 如果说第一个内存中维护的表可以理解成用HashSet或者<unordered_set>的话，可以理解得多来；但是请问第二个到硬盘的映射怎么具体实现呢，上面也好多个人就提了映射，哈希……

roricon

Mar 19, 2014

能重新组织文件的话，把这写数据重新组织到不同文件夹下，文件夹按照

root/
-----/姓
--------/名第一字
--------------------/名第二字
--------------------------------/名最后一个字.txt
--------/名第二字

txt里面保存电话号码……
剩下效率的问题就交给系统了……

alexapollo

Mar 19, 2014

@ivanlw 排序，分区，多级hash

qoshi

Mar 20, 2014

@ivanlw 文件指针？？？

yanpeipan

Mar 20, 2014

字典树

yangff

Mar 23, 2014

@ivanlw 名字显然有长度范围啊，如果一定要当作没有，那就只能对名字再建索引了……