锁定老帖子 主题:两个大数据量处理的问题.被鄙视了呜呜
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2011-09-14
import java.util.HashMap;
public class HashWordCount { private static HashMap<String,Integer> hm = new HashMap<String,Integer>(1000); public static void main(String[] args) { String[] args2 = {"asdf", "asdf", "as", "a"}; for (int i = 0; i < args.length; i++) { if(hm.containsKey(args2[i])){ int num = hm.get(args2[i]) ; num++ ; hm.put(args[2], num) ; }else{ hm.put(args2[i], 1) ; } } } } 貌似我这个做法很2 |
|
返回顶楼 | |
发表时间:2011-09-14
第一题:
第一种思路: 反向链表统计一亿词的词频,然后快速排序取top1000 第二种思路: 通过散列算法按照一定规则分散到若干个集合中,对每一个集合排序,最后再对所有的集合并归排序。 |
|
返回顶楼 | |
发表时间:2011-09-14
lzxz1234 写道 cdcx 写道 可以构造一棵树. 树的每个节点是一个字母.对于每个单词在树上都有一个唯一的路径.回溯这个路径可以得到完整的单词.这些路径不会太多,不超过几万个.每次解析一个单词都在这个树中查找,如果找不到就构建它,如果找到就在叶节点加1. 比如AB,ABC, ABD, AC
构造是下面的树. 得到这个树后可以遍历这颗树来比较频率最高的单词. A / \ B C / \ C D 很靠谱,+1,尝试着实现了一下 public class WordTree { public static void main(String[] args) { WordTree t = new WordTree(); String[] ss = {"asdf", "asdf", "as", "a"}; for(String s : ss) { t.accept(s); } CharNode cNode = t.getMaxNode(); System.out.println(cNode.num + " : " + cNode.getS()); } /** * 接收并处理一条新纪录 * @author lzxz * @param s */ public void accept(String s) { this.accept((CharSequence)s.toUpperCase()); } /** * 得到最大数量节点 * @author lzxz * @return */ public CharNode getMaxNode() { int maxNum = 0; CharNode maxNode = null; for(CharNode cNode : list) { if(cNode.num > maxNum) { maxNode = cNode; maxNum = cNode.num; } } return maxNode; } /** * 得到最大数量节点,要求必须全部大写 * @author lzxz * @param cs */ public void accept(CharSequence cs){ this.root.accept(cs); } private CharNode root = new CharNode(null, '$'); private final List<CharNode> list = new ArrayList<CharNode>(); private class CharNode { private char c; private int num; private CharNode parent = null; private Map<Character, CharNode> next; /** * 得到到达本路径的字符串全量 * @author lzxz * @return */ private String getS() { if(this.parent == null) { return String.valueOf(c); } return this.parent.getS() + c; } /** * 接收并处理一条新纪录 * @author lzxz * @param cs */ private void accept(CharSequence cs) { CharNode node = next.get(cs.charAt(0)); if(node == null) { node = new CharNode(this, cs.charAt(0)); next.put(cs.charAt(0), node); list.add(node); } if(cs.length() == 1){ node.num ++; } else { node.accept(cs.subSequence(1, cs.length())); } } /** * 指定参数构造CharNode实例。 * @param parent * @param c */ public CharNode(CharNode parent, char c){ num = 0; this.parent = parent; this.c = c; next = new HashMap<Character, CharNode>(); } } } 我刚才又想了想..这个真的还是不行..打个比方...我1000万个数字从1到1000万 第一曾是 9个 1-9 第二层就是 没个派生出十个子节点就是 100 个 第三层就是 1000 个 第四层 10000 第五曾100000 .... 到了第7层的时候就是1000万了 所以如上你创建了1111111个Node .里面有这么 多个HashMap ... 对内存占用量还是太大太大..... 这仅仅是数字..如果是汉字..在最坏条件下..第一层 65535 ..第二层....65535的平方...最后..就死掉了... |
|
返回顶楼 | |
发表时间:2011-09-14
第二题:
快速排序,然后二分查找 |
|
返回顶楼 | |
发表时间:2011-09-14
引用 我刚才又想了想..这个真的还是不行..打个比方...我1000万个数字从1到1000万 第一曾是 9个 1-9 第二层就是 没个派生出十个子节点就是 100 个 第三层就是 1000 个 第四层 10000 第五曾100000 .... 到了第7层的时候就是1000万了 所以如上你创建了1111111个Node .里面有这么 多个HashMap ... 对内存占用量还是太大太大..... 这仅仅是数字..如果是汉字..在最坏条件下..第一层 65535 ..第二层....65535的平方...最后..就死掉了... 确实有问题,我用大数据量测了下,即使把Map换成数组,然后自己扩容,也不过处理20W个身份证号,所以到底怎么整,还真得继续考虑下 |
|
返回顶楼 | |
发表时间:2011-09-14
zha_zi 写道 第一题:
第一种思路: 反向链表统计一亿词的词频,然后快速排序取top1000 第二种思路: 通过散列算法按照一定规则分散到若干个集合中,对每一个集合排序,最后再对所有的集合并归排序。 你看一下我第二题的解法吧...http://ansjsun.iteye.com/blog/1163037... |
|
返回顶楼 | |
发表时间:2011-09-14
lzxz1234 写道 引用 我刚才又想了想..这个真的还是不行..打个比方...我1000万个数字从1到1000万 第一曾是 9个 1-9 第二层就是 没个派生出十个子节点就是 100 个 第三层就是 1000 个 第四层 10000 第五曾100000 .... 到了第7层的时候就是1000万了 所以如上你创建了1111111个Node .里面有这么 多个HashMap ... 对内存占用量还是太大太大..... 这仅仅是数字..如果是汉字..在最坏条件下..第一层 65535 ..第二层....65535的平方...最后..就死掉了... 确实有问题,我用大数据量测了下,即使把Map换成数组,然后自己扩容,也不过处理20W个身份证号,所以到底怎么整,还真得继续考虑下 即使是自己扩容也是实现了一遍arrayList....不是解决的根本... 目前我的想法是先分批归并...最后得到一个总和的排序..如果查询串重复率很高的话.内存也许能吃的开..但是速度肯定不会让人满意的.... 我估计答案是用倒排索引的办法解决的... |
|
返回顶楼 | |
发表时间:2011-09-15
ansjsun 写道 lzxz1234 写道 cdcx 写道 可以构造一棵树. 树的每个节点是一个字母.对于每个单词在树上都有一个唯一的路径.回溯这个路径可以得到完整的单词.这些路径不会太多,不超过几万个.每次解析一个单词都在这个树中查找,如果找不到就构建它,如果找到就在叶节点加1. 比如AB,ABC, ABD, AC
构造是下面的树. 得到这个树后可以遍历这颗树来比较频率最高的单词. A / \ B C / \ C D 很靠谱,+1,尝试着实现了一下 public class WordTree { public static void main(String[] args) { WordTree t = new WordTree(); String[] ss = {"asdf", "asdf", "as", "a"}; for(String s : ss) { t.accept(s); } CharNode cNode = t.getMaxNode(); System.out.println(cNode.num + " : " + cNode.getS()); } /** * 接收并处理一条新纪录 * @author lzxz * @param s */ public void accept(String s) { this.accept((CharSequence)s.toUpperCase()); } /** * 得到最大数量节点 * @author lzxz * @return */ public CharNode getMaxNode() { int maxNum = 0; CharNode maxNode = null; for(CharNode cNode : list) { if(cNode.num > maxNum) { maxNode = cNode; maxNum = cNode.num; } } return maxNode; } /** * 得到最大数量节点,要求必须全部大写 * @author lzxz * @param cs */ public void accept(CharSequence cs){ this.root.accept(cs); } private CharNode root = new CharNode(null, '$'); private final List<CharNode> list = new ArrayList<CharNode>(); private class CharNode { private char c; private int num; private CharNode parent = null; private Map<Character, CharNode> next; /** * 得到到达本路径的字符串全量 * @author lzxz * @return */ private String getS() { if(this.parent == null) { return String.valueOf(c); } return this.parent.getS() + c; } /** * 接收并处理一条新纪录 * @author lzxz * @param cs */ private void accept(CharSequence cs) { CharNode node = next.get(cs.charAt(0)); if(node == null) { node = new CharNode(this, cs.charAt(0)); next.put(cs.charAt(0), node); list.add(node); } if(cs.length() == 1){ node.num ++; } else { node.accept(cs.subSequence(1, cs.length())); } } /** * 指定参数构造CharNode实例。 * @param parent * @param c */ public CharNode(CharNode parent, char c){ num = 0; this.parent = parent; this.c = c; next = new HashMap<Character, CharNode>(); } } } 这个问题我也考虑过.. 但是怕出现如下场景 用户查询100次中国 然后用户查询了100000次中国人 于是中国就变成100100次了 这个就是tire树,字典树 你查1亿次字典,字典里面中国也不会变成100100次,而只有一个中-国,和一个中-国-人 对于非文字段落,而且是有意义的词语用这个是比较合适的,毕竟中文里面的词语能有多少 |
|
返回顶楼 | |
发表时间:2011-09-15
oaklet 写道 1亿个词扔到数据库里,select count order by 一下就出来了
您能哥屋恩吗? |
|
返回顶楼 | |
发表时间:2011-09-15
开发一年了,接触这样的难题。帮忙活跃一下,学习下。期待最终解决方案
|
|
返回顶楼 | |