和风细雨

世上本无难事,心以为难,斯乃真难。苟不存一难之见于心,则运用之术自出。

使用LinkedHashMap进行分数排序

分数排序的特殊问题

在java中实现排序远比C/C++简单,我们只要让集合中元素对应的类实现Comparable接口,然后调用Collections.sort();方法即可.
这种方法对于排序存在许多相同元素的情况有些浪费,明显即使值相等,两个元素之间也要比较一下,这在现实中是没有意义的.
典型例子就是学生成绩统计的问题,例如高考中,满分是150,成千上万的学生成绩都在0-150之间,平均一个分数的人数成百上千,这时如果排序还用传统方法明显就浪费了.

进一步思考

成绩既然有固定的分数等级,我们可以把相同等级的成绩放在一起,以100分为满分计,共分一百个等级,来一个成绩就归入固定的档,要得到排序结果时可以从低档取到高档,取出来自然就是排序的结果.
接下来是确定数据结构的问题,档次-学生群这样的自然是key-value结构,但Map中的Hashtable和HashMap都不能保持插入时的顺序,虽然我们可以从固定的档次取名单,但这样略嫌不方便,我们需要更好的数据结构,它既以键值的形式存储数据,又能保持插入时的顺序.

LinkedHashMap横空出世

LinkedHashMap正是这样一个数据结构,它”在HashMap的基础上增加了一个双向链表,由此LinkedHashMap既能以哈希表的形式存储数据,又能保持查询时的顺序.”
下页就是进行排序用的类,它在构造实例时先创建好分数档次,加入学生成绩时自动归档,要取出排序的学生的成绩时只要按档次输出即可.

ScoreSorter类

package com.junglesong;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

/**
 * 学生分数排序类
 * 
@author: sitinspring(junglesong@gmail.com)
 * @date: 2008-3-4
 
*/

public class ScoreSorter{
    
/**
     * 学生成绩单
     
*/

    
private Map<Integer,List<Student>> scoreSheet;
    
    
/**
     * 满分分数
     
*/

    
private final int maxScore; 
    
    
/**
     * 构造函数
     * 
@param MaxScore: 满分分数
     
*/

    
public ScoreSorter(int MaxScore){
        
this.maxScore=MaxScore;
        scoreSheet
=new LinkedHashMap<Integer,List<Student>>();
        
        
for(int i=0;i<=maxScore;i++){
            List
<Student> ls=new ArrayList<Student>();
            scoreSheet.put(i, ls);
        }

    }

    
    
/**
     * 添加一个学生成绩
     * 
@param student
     
*/

    
public void addStudent(Student student){
        
int score=student.getScore();
        
if(student.getScore()>maxScore){
            
return;
        }

        
        List
<Student> ls=scoreSheet.get(score);
        ls.add(student);
    }

    
    
/**
     * 得到从低到高的学生成绩表
     *
     
*/

    @SuppressWarnings(
"unchecked")
    
public List<Student> getSortedScores(){
        List
<Student> retval=new ArrayList<Student>();
        
        Iterator it
=scoreSheet.values().iterator();

        
while(it.hasNext()){
            List
<Student> ls=(List<Student>)it.next();
            retval.addAll(ls);
        }

        
        
return retval;
    }

}

辅助类Student

package com.junglesong;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class Student implements Comparable{
    
private String name;
    
private int score;
    
    
public Student(String name,int score){
        
this.name=name;
        
this.score=score;
    }

    
    
public int compareTo(Object obj){
        Student another
=(Student)obj;        
        
return this.score-another.score;
    }

    
    
public String toString(){
        
return "学生姓名="+name+" 分数="+score;
    }

    
public String getName() {
        
return name;
    }


    
public void setName(String name) {
        
this.name = name;
    }


    
public int getScore() {
        
return score;
    }


    
public void setScore(int score) {
        
this.score = score;
    }

    
    
public static void main(String[] args){
        
//-----------老排序方案-----------
        /*TimeTest oldSortTest=new TimeTest();
        List<Student> scores=new ArrayList<Student>();
        
        Random random=new Random();
        for(int i=0;i<100000;i++){
            scores.add(new Student("学生"+i,random.nextInt(100)));
        }
        
        Collections.sort(scores);
        //for(Student student:scores){
        //    System.out.println(student);
        //}
        oldSortTest.end("老排序方案耗时");
*/

        
        
//-----------新排序方案-----------
        TimeTest newSortTest=new TimeTest();
        ScoreSorter sorter2
=new ScoreSorter(100);
        
        Random random
=new Random();
        
for(int i=0;i<1000;i++){
            sorter2.addStudent(
new Student("学生"+i,random.nextInt(100)));
        }

        
        List
<Student> ls=sorter2.getSortedScores();
        
//for(Student student:sorter2.getSortedScores()){
        
//    System.out.println(student);
        
//}
        newSortTest.end("新排序方案耗时");    
    }

}

 

与传统排序方案的比较

在元素个数远超等级个数即相同的元素很多时,这种方案在速度上稍高于传统方案,节省的时间主要在不比较同等级元素上.
这种方案能够按档次取出数据,这种优势是传统排序方案缺乏的.
传统方案普适性比此方案强.

http://www.blogjava.net/Files/junglesong/ScoreSorter20080304222012.rar

posted on 2008-03-04 21:06 和风细雨 阅读(3981) 评论(1)  编辑  收藏 所属分类: 算法

评论

# re: 使用LinkedHashMap进行分数排序 2008-08-02 11:28 天堂明月

代码我收下了,有机会一起讨论技术吧  回复  更多评论   


只有注册用户登录后才能发表评论。


网站导航: