V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
ivanlw
V2EX  ›  程序员

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

  •  
  •   ivanlw ·
    tolinwei · 2014-03-18 18:11:29 +08:00 · 3994 次点击
    这是一个创建于 3663 天前的主题,其中的信息可能已经有所发展或是发生改变。
    有20个以上的文件,每个文件1G,每个文件内容都是:
    姓名 电话
    他们都没有规律的存在文件当中,而且不重复。
    要求写一段程序,可以对这些文件进行任意时间的预处理,重新组织他们,要求用户在程序中输入一个人的名字,返回对应的电话号码,搜索时间自然是越短越好了
    请问有什么思路吗?
    ====================
    自己测试了下,用mockaroo.com生成了一个里面有100000条记录的单文件,也才2.3M,似乎这个数量多得可怕,其实用什么神奇的外排序以后,要短时间找到指定记录似乎也很难吧?
    附上20个测试文件,当然是2.3M的每个,1G的实在弄不出来了……
    https://www.dropbox.com/sh/ouw5obag5dq257l/AF7g4xniMb
    16 条回复    1970-01-01 08:00:00 +08:00
    iloahz
        1
    iloahz  
       2014-03-18 18:47:50 +08:00   ❤️ 1
    我试了一下,10000条“名字 12345678901”这样的记录在txt里大概是175kb,所以20G的文件大概也就是1198372571条记录。

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

    如果你内存不充足,那就是建各种索引呗,这个我不是很熟。比如你可以根据第一个字将所有记录分类,然后第二个字,然后第三个字……这样每次在内存里的就只有一个字的索引表,这个就相当小了。这段胡扯不要在意。。。。
    yangff
        2
    yangff  
       2014-03-18 19:18:27 +08:00   ❤️ 1
    1)排序每个文件,并分别输出。也就是先读入第一个文件(1g内存总放的下吧),然后直接sort排序后按顺序输出。
    2)建立一个堆,从这20个文件里面各取出第一条记录,(记录,来自哪个文件)放进堆中。
    3)取出堆顶部的记录,放到一个文件当中,然后看一下这个记录是从哪个文件来的,从那个文件中取出下一条记录,放入堆中重复这个过程直到所有记录被排序。
    注意一下在放入文件的时候,将长度对其,比如说“某某 133xxxxxxxx”、“某某某某 133xxxxxxxx”之类的,长度不一样的串,在后面补充空格直到所有串都能够对其(也就是有相同的长度)。如果能二进制压一下就更好了。

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

    另外最后这步其实可以优化的更好。
    ivanlw
        3
    ivanlw  
    OP
       2014-03-18 19:42:03 +08:00
    @yangff 感谢你的第三布,我想到的是每个文件排序后用理论上的N路归并排序,但是那样子代码的循环控制太复杂了(考虑到随时用完要取新的下一段记录)。还有几个问题:
    1.有什么语言能比较方便的执行这些文件IO的操作呢?
    2.fseek是什么的东西?我搜到的是这个: http://www.cplusplus.com/reference/cstdio/fseek/,能不能给点其他关键字。
    3.如果在排序后的那个文件(20G)里面搜,用你所说的fseek的方法的话,是不是不用把他们全部读进内存中?如果要全部读的话,肯定放不下的,希望你是有考虑到这点的。
    yangff
        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
    pubby
        5
    pubby  
       2014-03-18 23:37:35 +08:00
    如果在机械硬盘上操作,要考虑其特性做好适合的索引,仅仅排序的话未必做到最快,因为二分fseek还是会让磁头产生最多30多次随机定位,都知道随机读肯定不如顺序读

    不考虑成本,排序后直接塞内存,大不了分多几台机器塞并发查就是了
    alexapollo
        6
    alexapollo  
       2014-03-19 01:34:27 +08:00
    明显是hash啊,O(1)效率
    ivanlw
        7
    ivanlw  
    OP
       2014-03-19 02:45:43 +08:00
    @pubby
    @alexapollo 能指点下怎么在硬盘上具体的建索引吗?没有这方面的经历
    ivanlw
        8
    ivanlw  
    OP
       2014-03-19 07:32:02 +08:00
    @alexapollo 如果你指的是用编程语言内置的Hashset或者unordered_set,内存肯定放不下那么多东西;如果你要自己设计hash function映射到文件制定位置,希望给一个这样子的函数的方案,谢谢
    ivanlw
        9
    ivanlw  
    OP
       2014-03-19 08:35:10 +08:00
    @yangff 前面是名字的话,没有长度范围,没办法对其吧?
    qoshi
        10
    qoshi  
       2014-03-19 08:57:57 +08:00
    约10^10条数据
    可以进行两次哈希
    内存中维护一张10^5次的表(这个不难)
    其中每一个项映射一张10^5的表(硬盘中)
    第一次hash找到对应表的位置,再进行一次hash,找到结果
    done~~
    ivanlw
        11
    ivanlw  
    OP
       2014-03-19 09:26:54 +08:00
    @qoshi 如果说第一个内存中维护的表可以理解成用HashSet或者<unordered_set>的话,可以理解得多来;但是请问第二个到硬盘的映射怎么具体实现呢,上面也好多个人就提了映射,哈希……
    roricon
        12
    roricon  
       2014-03-19 13:21:07 +08:00
    能重新组织文件的话,把这写数据重新组织到不同文件夹下,文件夹按照

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

    txt里面保存电话号码……
    剩下效率的问题就交给系统了……
    alexapollo
        13
    alexapollo  
       2014-03-19 20:48:10 +08:00
    @ivanlw 排序,分区,多级hash
    qoshi
        14
    qoshi  
       2014-03-20 09:07:38 +08:00
    @ivanlw 文件指针???
    yanpeipan
        15
    yanpeipan  
       2014-03-20 14:25:02 +08:00
    字典树
    yangff
        16
    yangff  
       2014-03-23 18:46:40 +08:00
    @ivanlw 名字显然有长度范围啊,如果一定要当作没有,那就只能对名字再建索引了……
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3153 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 12:31 · PVG 20:31 · LAX 05:31 · JFK 08:31
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.