-1

カスタム順序付けを使用してコレクションをソートするための Java コンパレーターを実装するための (時間とスペースの両方の効率の点で) 最良の方法は何ですか。たとえば、次の順序で配列を並べ替えたいとします。

RWQOJMVAHBSGZXNTCIEKUPDYFL

期待どおりに動作する次の Java コードがありますが、同じことを行う効率的な方法が他にあるかどうかはわかりません。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.lang.Math;

public class DiffSort {

    private static String order = "RWQOJMVAHBSGZXNTCIEKUPDYFL";

    // sort with comparator
    public static Comparator<String> diffNaturalOrder = new Comparator<String>() {
        public int compare(String v, String w) {
            int diff = 0, iter = 0;
            Integer index1, index2;
            Integer len1 = v.length();
            Integer len2 = w.length();
            int len = Math.min(len1, len2); // lesser of 2 strings

            for(int i=0; i<len; i++) {
                index1 = order.indexOf(v.charAt(i));
                index2 = order.indexOf(w.charAt(i));
                // if both chars are absent in order string, use natural ordering
                if(index1 == -1 && index2 == -1)
                    diff = new Character(v.charAt(i)).compareTo(new Character(w.charAt(i)));
                else if(index1 == -1 && index2 > 0)
                    diff = 1;
                else if(index1 > 0 && index2 == -1)
                    diff = -1;
                else
                    diff = index1.compareTo(index2);
                // break if we found mismatch
                if(diff != 0) break;
            }

            // return smaller string first in sort
            if(diff == 0)
                diff = len1.compareTo(len2);
            return diff;
        }
    };

    // test client
    public static void main(String[] args) {
        List<String> list = new ArrayList<String>();
        list.add("ABCE1!4");
        list.add("ABCE1!7");
        list.add("!SDF");
        list.add("TRWESF!");
        Collections.sort(list, DiffSort.diffNaturalOrder);

        // print sorted array
        for(String s:list)
            System.out.println(s);
    }
}

/* 出力 */

ABCE1!4

ABCE1!7

トルウェス！

!自衛隊

4

4 に答える 4

5

のすべての文字をordera Map<Character, Integer>(整数は の文字の位置に対応するorder)に入れてから、 useforの代わりに -loop に入れます。order.indexOf(c)map.get(c)

このマップはかなり簡単に設定できます。

private static final Map<Character, Integer> map = 
                                new HashMap<Character, Integer>(order.length());

static {
    for (int i = 0; i < order.length(); i++)
        map.put(order.charAt(i), i);
}
于 2013-08-05T20:33:03.263 に答える
2

私がさらに行うことは、char からの位置の計算をキャッシュすることです。

最初の w は、マップにチェックインする前に文字が等しいことを比較します。

次に、map に char の各組み合わせを格納します。

（左右）

左が早い場合は 1 を返し、右が早い場合は -1 を返し、左が右の場合は 0 を返します。

または、char 配列を作成し、char の位置に順序を格納することもできます。

public final class CustomAlphabetComparator implements Comparator<String> {

        private char order[] = new char[1<<16];


        public CustomAlphabetComparator (String alphabet) {
            if (alphabet == null) throw new IllegalArgumentException("Input must not be null");

            char index = 0;

            for(char c : alphabet.toCharArray()) {
                order[c] = index++;
            }
        }


        @Override
        public int compare(String o1, String o2) {

            if(o1 == o2) return 0; //We check the references

            if(o1 == null && o2 == null) return  0;
            if(o1 != null && o2 == null) return  1;
            if(o1 == null && o2 != null) return -1;

            if(o1.equals(o2)) return 0; //We check that are equal

            char[] c1 = o1.toCharArray();
            char[] c2 = o2.toCharArray();

            int shortest = c1.length < c2.length ? c1.length : c2.length;
            int result = 0;

            for(int i = 0; result == 0 & i < shortest; i++ ) {

                result = order[c1[i]] - order[c2[i]];

            }

            return result;
        }

    }
于 2013-08-05T20:37:44.310 に答える
0

英大文字のみの効率的な Comparator を次に示します (拡張することはできますが、制限がないわけではありません)。

public static Comparator<String> diffNaturalOrder = new Comparator<String>() {
    private int[] order = new int[] {7, 9, 16, 22, 18, 24, 11, 8, 17, 4, 19, 25, 5, 14, 3, 21, 2, 0, 10, 15, 20, 6, 1, 13, 23, 12};
    public int compare(String v, String w) {
        int diff = 0;
        int len = Math.min(v.length(), w.length()); // lesser of 2 strings
        int o1, o2;
        for(int i=0; i<len; i++) {
            o1 = order[v.charAt(i)-65];
            o2 = order[w.charAt(i)-65];
            diff = o1 - o2;
            // break if we found mismatch
            if(diff != 0) break;
        }
        if (diff == 0) {
            diff = v.length() - w.length();
        }
        return diff;
    }
};

indexOfまたはではなくMap<Character, Integer>、これは char (65 未満) の整数値を使用して、順序付けデータを含む配列にインデックスを付けます。配列は次のように生成できます。

private static void generateArray() {
    String order = "RWQOJMVAHBSGZXNTCIEKUPDYFL";
    int[] chars = new int[26];
    int i = 0;
    for (char c : order.toCharArray()) {
        chars[c-65] = i++;
    }
    System.out.println(Arrays.toString(chars));
}
于 2013-08-05T20:50:34.413 に答える
0

明らかにあなたが持っているコードは機能しますが、覚えておくべきことの1つは、 String.indexOf(ch) が探しているものが見つかるまで文字列を1文字ずつ調べることです。文字列が「アルファベット」の終わり近くにある場合、多くの不要なループが発生します。

順序を に保存し、HashMap<Character, Integer>そこからインデックス情報を一定時間で取得します。文字列全体をループするよりも高速である必要があります (比較しているすべての文字に対して!)...

于 2013-08-05T20:38:05.707 に答える