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

Java 超大文件统计

  •  1
     
  •   MrXiong · 2018-06-11 10:39:16 +08:00 · 6533 次点击
    这是一个创建于 2117 天前的主题,其中的信息可能已经有所发展或是发生改变。

    对于超大文件也就是无法一次性加载到内存,行数据是 key:value,统计同一个,key 的不同 value 个数,并输出到文件,格式为 key:n,输出的文件假设也很大,也无法加载到内存中,求思路

    第 1 条附言  ·  2018-06-11 13:06:41 +08:00
    首先感谢各位老铁的回复,但是请看清题意,java 文件操作用的少,但是使用 java 类库我还是没问题的!
    38 条回复    2018-06-14 19:14:13 +08:00
    zynlp
        1
    zynlp  
       2018-06-11 10:46:02 +08:00 via iPhone
    这种活就交给 python 吧
    MrXiong
        2
    MrXiong  
    OP
       2018-06-11 10:46:47 +08:00
    @zynlp 语言其次的,思路是关键
    araraloren
        3
    araraloren  
       2018-06-11 10:47:57 +08:00
    思路不就是读多少处理多少么。。
    huiyadanli
        4
    huiyadanli  
       2018-06-11 10:48:14 +08:00
    把超大文件处理到数据库中,然后用 sql 统计数据
    wplct
        5
    wplct  
       2018-06-11 10:48:20 +08:00
    java 不是可以按行读取么
    wplct
        6
    wplct  
       2018-06-11 10:51:20 +08:00
    要不,先跑一边计数每个 key 有多少个 value,然后一个个 key 分开处理,慢是慢些
    xylophone21
        7
    xylophone21  
       2018-06-11 10:59:16 +08:00
    超大是多大?目的是什么?(考试还是工程)
    如果是工程问题,最简单的方法其实是转嫁矛盾,读一行,写一条数据到文件行不行?文件不好查找,直接用数据库行不行?数据库还不够,分表行不行?分表还不行,用跟牛 X 的数据库分表啊。
    如果是考试,那就往 hadoop 生态,MapReduce 上扯。
    MrXiong
        8
    MrXiong  
    OP
       2018-06-11 11:01:04 +08:00
    @xylophone21 直接上 MapReduce 进行处理?
    EchoUtopia
        9
    EchoUtopia  
       2018-06-11 11:01:53 +08:00
    postgres:
    insert into words_count(word) values('example') on conflict do update count=words_count.count + 1 returning id
    wplct
        10
    wplct  
       2018-06-11 11:02:12 +08:00
    all_key = {}
    with open('f.text') as f:
    key = f.readline().split(':')[0]
    if key not in all_key:
    all_key[key] = 0
    all_key[key] += 1

    result = {}

    for key in all_key.keys():
    values = set()
    with open('f.text') as f:
    key, value = f.readline().split(':')
    if key == key:
    values.add(value)
    result[key] = len(values)
    wplct
        11
    wplct  
       2018-06-11 11:02:48 +08:00
    你可以再改成一次跑多个 key 的统计,
    EchoUtopia
        12
    EchoUtopia  
       2018-06-11 11:02:57 +08:00
    postgres:
    insert into words_count(word) values('example') on conflict do update set count=words_count.count + 1 returning id
    FreeEx
        13
    FreeEx  
       2018-06-11 11:12:10 +08:00
    流处理了解一下
    kaiser1992
        14
    kaiser1992  
       2018-06-11 11:14:17 +08:00
    Java 读取文件哪有一次性加载到内存的
    EchoUtopia
        15
    EchoUtopia  
       2018-06-11 11:15:58 +08:00
    https://github.com/EchoUtopia/my-python-practices/blob/master/trie.js
    之前用 js 统计了《心理学与生活》这本书的词频,用的前缀树,这本书纯文字只有 1M 多,我用 js 读取整本书、将单词插入前缀树、搜索一个单词、列出单词的频次并按照频次排序,所有操作加起来不到 0.5 秒。
    BBCCBB
        16
    BBCCBB  
       2018-06-11 11:24:20 +08:00
    bufferreader 啊, 不都是流处理吗?
    SoCrazyStone
        17
    SoCrazyStone  
       2018-06-11 11:57:17 +08:00
    Java 直接读就可以吧,不是一次加载进内存,然后存到数据库里,结束了再导到文件?
    wplct
        18
    wplct  
       2018-06-11 12:35:56 +08:00
    @EchoUtopia #15 想啥呢,内存放不下,应该是 gb 量级了
    pathbox
        19
    pathbox  
       2018-06-11 12:42:33 +08:00 via iPhone
    一行一行的 read 处理 就没有大文件内存限制了
    rrfeng
        20
    rrfeng  
       2018-06-11 12:44:17 +08:00
    awk '!a[key:value]{n[key]++}END{for(i in n)print i,n[i]}'
    rockyou12
        21
    rockyou12  
       2018-06-11 12:50:10 +08:00
    lz 怕是从来没写过 java 的文件操作,如果直接用 stream 来读,本来就该用个小的 buffer 来读。不然直接用 nio 的 readline 就行了。自己谷歌下 java nio read file
    CoderGeek
        22
    CoderGeek  
       2018-06-11 12:55:49 +08:00
    ...一行一行就好了
    EchoUtopia
        23
    EchoUtopia  
       2018-06-11 12:57:22 +08:00
    @wplct #18 文件上 gb 量级不代表前缀树也有这么大。。
    wplct
        24
    wplct  
       2018-06-11 12:59:48 +08:00
    楼上的,楼主不是流式处理 ,是因为这个需求需要去重,一次性处理内存可能不够
    panpanpan
        25
    panpanpan  
       2018-06-11 13:14:35 +08:00 via iPhone
    导进数据库里面 group by 一下难道不是最简单的方式?
    MrXiong
        26
    MrXiong  
    OP
       2018-06-11 13:20:00 +08:00
    @panpanpan 这是公司的转正题目,使用数据库是不是不太好啊
    xmh51
        27
    xmh51  
       2018-06-11 13:21:15 +08:00
    分而治之 把大文件拆分掉成 N 份 每份都计算 key 的 value count 值(需要带上 value ),然后把 key 按 hashcode 计算得到文件里面。最后合并结果文件
    xmh51
        28
    xmh51  
       2018-06-11 13:21:57 +08:00
    感觉像算法题 果然是算法题 ......
    xmh51
        29
    xmh51  
       2018-06-11 13:24:36 +08:00
    优化下 分而治之 读大文件不用拆分,一行一行读即可,直接计算 hashcode,把 key value 直接放到 N 份文件中的指定一个文件中。然后直接计算结果,最后合并结果
    MrXiong
        30
    MrXiong  
    OP
       2018-06-11 13:27:31 +08:00
    @xmh51 你的意思是每个 hash 一个文件吗,并且你忘记去重了
    verrickt
        31
    verrickt  
       2018-06-11 13:29:31 +08:00 via Android   ❤️ 1
    先对文件用外部排序按 key 排序。然后读一行,看下一行的 key,一样的话加计数,不一样把计数写到输出文件里。大体上还是外部排序+归并的思路
    xmh51
        32
    xmh51  
       2018-06-11 13:42:58 +08:00
    @MrXiong 去重在 hash 之后的一个步骤。一共两次 第一次 归并 key value 到指定文档,第二次 去重计算 count
    xmh51
        33
    xmh51  
       2018-06-11 13:46:19 +08:00
    @MrXiong 第一次 归并 key value 到指定的 n 个文件中(保证 key 相同的数据在同一个文件中,可以用 hashcode 分),第二次 去重计算 count,最好合并结果
    20015jjw
        34
    20015jjw  
       2018-06-11 14:00:39 +08:00 via Android
    data base 课最基本的内容吧
    dangluren
        35
    dangluren  
       2018-06-11 14:27:04 +08:00
    你好,这种问题,就和 mapreduce 类似了。如果你不用 mapreduce,可以这样做(其实也是 mapreduce 的原理)
    假如数据有 10G,你内存 1G, 假设比较均匀,不存在数据倾斜情况(倾斜不能太严重)。
    1. 你先一行一行的读取,然后得到 key 的 hashcode, 然后对%20,得到的数是几,就写到第几个文件去。
    2. 由第一步你就得到了 20 个文件了,如果数据没倾斜,大概一个就 500M, 这时候同一个 key 的肯定在同一个文件,进行处理就可以了。
    3. 如果有点数据倾斜,就%30, %50 的尝试。如果某一个 key 就超过了 1G,某个 key 很大的情况下,你可以先把这个 key 过滤出来,写入到一个文件中,然后再使用布隆过滤器或者其他什么方法
    kaiser1992
        36
    kaiser1992  
       2018-06-11 15:11:48 +08:00
    采用分治思想,借助 Hadoop
    qingfengxm
        37
    qingfengxm  
       2018-06-11 15:11:53 +08:00
    不知道你说的超大文件有多大? 10G 还是 10T。你这说的其实就是大数据单词计数,mapreduce 或者 spark 搞定
    dif
        38
    dif  
       2018-06-14 19:14:13 +08:00
    mapreduce
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3043 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 14:38 · PVG 22:38 · LAX 07:38 · JFK 10:38
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.