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

一个大数据文件查找问题 的讨论

  •  
  •   wog · 2013-02-02 22:57:35 +08:00 · 2739 次点击
    这是一个创建于 4312 天前的主题,其中的信息可能已经有所发展或是发生改变。
    有个特别大的文件,上千万行,1G多,
    格式是这样的,
    0,aaaa,1
    1,aaaa,2
    2,bbbb,1
    3,bbbb,2
    ..
    ..
    ..

    第一列是不重复的,第二列是字符串,有重复的,第三列是递增的数字,可能不连续,第二列相同的行第三列是不同的,但是第二列不同的数据第三列有可能相同

    现在的问题是给出第二列和第三列,找出第一列,
    这个数据量比较大,不能用数据库
    问有什么比较好的算法?谢谢。
    /************************************************************************/
    他题目没说清,打如果是需要频繁的增删改查,
    我的想法是,先压缩数据,大概是
    struct data{
    char *str;//字符串
    vector<int> pos;//第一列的值
    };


    于是上面的数据就压缩成两条
    struct data data1={"aaaa",{0,1}};
    struct data data2={"bbbb",{2,3}};

    之后申请指针数组

    struct data *ptrs[];
    之后建立一个映射f(n)=m,n是第二列字符串,得到的m是偏移量,把上面的数据指针填到ptrs[m]里,如果不能保证f(n)映射一一对应,那就把struct data改成
    struct data2{
    char *str;//字符串
    vector<int> pos;//第一列的值
    struct data2 *next;//下一个相同映射值的指针
    };
    我想问下,
    1,如果在实际应用中,我说的这种方法可行不
    2,如果有内存限制,这个问题该怎么办(我只能想到遍历。。。)
    2 条回复    1970-01-01 08:00:00 +08:00
    wog
        1
    wog  
    OP
       2013-02-02 22:59:22 +08:00
    这是我刚逛论坛碰见的问题,上面没人回答,于是拿到这里讨论下
    http://www.newsmth.net/nForum/#!article/CoderInterview/3045
    best1a
        2
    best1a  
       2013-02-02 23:18:37 +08:00
    标题不是说了是查么,没必要考虑增删改的情况
    这种题目看起来好像面试题。。。一般做法是,根据第二或第三个字段做个hash啥的,分到N个文件中,如果内存限制比较死,那N可以弄大点
    然后再各种方法做小范围的查找。。。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   952 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 20:43 · PVG 04:43 · LAX 12:43 · JFK 15:43
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.