データの整列 in Java DouKaku?

(x, y) の座標情報を以下の2種類の方法で整列する機能を実現してください。

(x, y) の辞書順(まず x で昇順に整列して、x が同じデータに対して y で昇順に整列する)
(0, 0) からの距離の昇順

データの表現方法はタプルなり構造体/オブジェクトなり各自で適当に選んで下さい。

Javaらしく、Comparatorを実装しました。

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

public class Sample163 {
    public static void main(String[] args) {
        Random random = new Random();
        List<Point> list = new ArrayList<Point>();
        for (int index = 0, count = 10; index < count; index++) {
            list.add(new Point(random.nextInt(10), random.nextInt(10)));
        }

        System.out.print("original  : ");
        System.out.println(list.toString());

        Collections.sort(list, new DictionaryComparator());
        System.out.print("dictionary: ");
        System.out.println(list.toString());

        Collections.sort(list, new DistanceComparator());
        System.out.print("distance  : ");
        System.out.println(list.toString());
    }
}

class Point {
    public final int x;
    public final int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override public String toString() {
        return "(" + x + "," + y + ")";
    }
}

class DictionaryComparator implements Comparator<Point> {
    @Override
    public int compare(Point o1, Point o2) {
        int result = Integer.valueOf(o1.x).compareTo(o2.x);
        if (result == 0) {
            result = Integer.valueOf(o1.y).compareTo(o2.y);
        }
        return result;
    }
}

class DistanceComparator implements Comparator<Point> {
    @Override
    public int compare(Point o1, Point o2) {
        return Integer.valueOf(o1.x * o1.x + o1.y * o1.y).compareTo(o2.x * o2.x + o2.y * o2.y);
    }
}

このソートのためだけにトップレベルにクラスを定義するのが納得いかないで，ローカルクラスを使いました．無名クラスを使用しなかったのは，ぱっとみてどう動作するかをクラス名に示したかったからです．

import java.awt.Point;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;


public class Sample163 {

    public static void main(String[] args) {
        Random random = new Random();
        List<Point> list = new ArrayList<Point>();
        for (int index = 0, count = 10; index < count; index++) {
            list.add(new Point(random.nextInt(10), random.nextInt(10)));
        }
        
        System.out.print("original : ");
        System.out.println(toString(list));
        
        class XYComparator implements Comparator<Point> {
            @Override
            public int compare(Point p1, Point p2) {
                int result = compareTo(p1.x, p2.x);
                if( result == 0 ) {
                    result = compareTo(p1.y, p2.y);
                }
                return result;
            }
        }
        
        Collections.sort(list, new XYComparator());
        System.out.print("xyorder : ");
        System.out.println(toString(list));
        
        class DistanceComparator implements Comparator<Point> {
            @Override
            public int compare(Point p1, Point p2) {
                return compareTo(length(p1), length(p2));
            }
            
            // ベクトルではないのでlengthではないですが，
            // 良い名前が思いつかないのでlengthにしました．
            public int length(Point p1) {
                return p1.x * p1.x + p1.y * p1.y;
            }
        }
        
        Collections.sort(list, new DistanceComparator());
        System.out.print("distance : ");
        System.out.println(toString(list));
    }
    
    public static int compareTo(int i1, int i2) {
        return Integer.valueOf(i1).compareTo(i2);
    }
    
    public static String toString(Point p) {
        return "(" + p.x + "," + p.y + ")";
    }
    
    public static String toString(List<Point> list) {
        StringBuilder builder = new StringBuilder();
        builder.append("{");
        for (Point point : list) {
            builder.append(toString(point));
            builder.append(",");
        }
        builder.delete(builder.length()-1, builder.length());
        builder.append("}");
        return builder.toString();
    }

}

使う時の手軽さを考えるとこのくらいかなと思っています．
一般によく使われる大小関係があるならば，
Comparable の実装も加えたほうがいいかもしれません．

13, 20行目はオーバーフローなどが起こるかも知れないので，
もう少しまじめに書いたほうがよさそうです．


$ javac Point.java
$ java Point
[(0,1), (1,1), (1,0), (1,2), (2,0), (0,0), (2,1), (0,2), (2,2)]
[(0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)]
[(0,0), (0,1), (1,0), (1,1), (0,2), (2,0), (1,2), (2,1), (2,2)]

// Point.java

import java.util.*;

class Point {
    public int x, y;
    
    public Point(int x, int y){
        this.x = x;  this.y = y;
    }
    
    public static final Comparator<Point> CMP_LEXICO = 
        new Comparator<Point>(){
            public int compare(Point p, Point q){
                return p.x == q.x ? p.y - q.y : p.x - q.x;
            }
        };
    
    public static final Comparator<Point> CMP_DIST =
        new Comparator<Point>(){
            public int compare(Point p, Point q){
                return (p.x * p.x + p.y * p.y) - (q.x * q.x + q.y * q.y);
            }
        };
    
    public String toString(){
        return "(" + x + "," + y + ")";
    }
    
    // for test
    public static void main(String argv[]){
        List<Point> points = new ArrayList<Point>();
        
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                Point pt = new Point(i,j);
                points.add(pt);
            }
        }
        
        Collections.shuffle(points);
        System.out.println(points);
        
        Collections.sort(points, Point.CMP_LEXICO);
        System.out.println(points);
        
        Collections.sort(points, Point.CMP_DIST);
        System.out.println(points);
    }
}

DouKaku?

データの整列

Posted feedbacks - Java

Index

Feed

Other

Link

Pathtraq