论坛首页 综合技术论坛

两个大数据量处理的问题.被鄙视了呜呜

浏览 27948 次
精华帖 (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
0 请登录后投票
   发表时间:2011-09-14  
第一题:
      第一种思路: 反向链表统计一亿词的词频,然后快速排序取top1000
      第二种思路: 通过散列算法按照一定规则分散到若干个集合中,对每一个集合排序,最后再对所有的集合并归排序。
0 请登录后投票
   发表时间: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的平方...最后..就死掉了...
0 请登录后投票
   发表时间:2011-09-14  
第二题:
       快速排序,然后二分查找
0 请登录后投票
   发表时间:2011-09-14  
引用

我刚才又想了想..这个真的还是不行..打个比方...我1000万个数字从1到1000万
第一曾是
9个 1-9
第二层就是 没个派生出十个子节点就是 100 个
第三层就是 1000 个
第四层 10000
第五曾100000
....
到了第7层的时候就是1000万了
所以如上你创建了1111111个Node .里面有这么 多个HashMap ...

对内存占用量还是太大太大.....


这仅仅是数字..如果是汉字..在最坏条件下..第一层 65535 ..第二层....65535的平方...最后..就死掉了...

确实有问题,我用大数据量测了下,即使把Map换成数组,然后自己扩容,也不过处理20W个身份证号,所以到底怎么整,还真得继续考虑下
0 请登录后投票
   发表时间:2011-09-14  
zha_zi 写道
第一题:
      第一种思路: 反向链表统计一亿词的词频,然后快速排序取top1000
      第二种思路: 通过散列算法按照一定规则分散到若干个集合中,对每一个集合排序,最后再对所有的集合并归排序。

你看一下我第二题的解法吧...http://ansjsun.iteye.com/blog/1163037...
0 请登录后投票
   发表时间:2011-09-14  
lzxz1234 写道
引用

我刚才又想了想..这个真的还是不行..打个比方...我1000万个数字从1到1000万
第一曾是
9个 1-9
第二层就是 没个派生出十个子节点就是 100 个
第三层就是 1000 个
第四层 10000
第五曾100000
....
到了第7层的时候就是1000万了
所以如上你创建了1111111个Node .里面有这么 多个HashMap ...

对内存占用量还是太大太大.....


这仅仅是数字..如果是汉字..在最坏条件下..第一层 65535 ..第二层....65535的平方...最后..就死掉了...

确实有问题,我用大数据量测了下,即使把Map换成数组,然后自己扩容,也不过处理20W个身份证号,所以到底怎么整,还真得继续考虑下



即使是自己扩容也是实现了一遍arrayList....不是解决的根本...

目前我的想法是先分批归并...最后得到一个总和的排序..如果查询串重复率很高的话.内存也许能吃的开..但是速度肯定不会让人满意的....

我估计答案是用倒排索引的办法解决的...
0 请登录后投票
   发表时间: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次,而只有一个中-国,和一个中-国-人
对于非文字段落,而且是有意义的词语用这个是比较合适的,毕竟中文里面的词语能有多少
0 请登录后投票
   发表时间:2011-09-15  
oaklet 写道
1亿个词扔到数据库里,select count    order by 一下就出来了

您能哥屋恩吗?
0 请登录后投票
   发表时间:2011-09-15  
开发一年了,接触这样的难题。帮忙活跃一下,学习下。期待最终解决方案
0 请登录后投票
论坛首页 综合技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics