0

ボードゲームで動きを並べ替えるための次のコードがあります。高度に最適化できるように見えます。

    private List<Move> sortMoves(List<Move> moves, int depth)
    {
        List<Move> sorted = new ArrayList<Move>();

        if (moves.size() == 0)
            return sorted;

        List<Move> primary = new ArrayList<Move>();
        List<Move> rest = new ArrayList<Move>();

        for(int i = 0; i < moves.size(); i++)
        {
            if (killers.primary[depth] != null && moves.get(i).equals(killers.primary[depth]))
                primary.add(moves.get(i));          

            else
                rest.add(moves.get(i));
        }

        sorted.addAll(primary);
        sorted.addAll(rest);

        return sorted;
    }

上記へのより良い、より効率的な方法はありますか（つまり、2つのリストを交差させ、ソートされたリストを返します）？

注：この関数の目的は、移動リストで見つかったキラー移動（プライマリ）を削除してから、最初にキラー移動を含む新しいリストを返し、次に元の移動リストのリストを返すことです。

4

2 に答える 2

2

リストをすばやく並べ替えるには

Collections.sort(リスト リスト);

また

Collections.sort(List list,Comparator c)

于 2013-03-19T14:36:45.387 に答える
1

大きすぎない場合moves、現在の実装は問題ないように見えます。その複雑さは O(n) です。ここで唯一の欠点は、3 つの余分なリストによるスペースの複雑さです。primary、restおよびsorted。

を使用すると、スペースの複雑さをいくらか節約できますCollections.sort(List<T> list, Comparator<? super T> c)。

private void sortMoves(final List<Move> moves, final int depth)
{
    Collections.sort(moves, new Comparator<Move>() {
        @Override
        public int compare(Move o1, Move o2) {

            if(killers.primary[depth] != null && moves.get(i).equals(killers.primary[depth])) {

                return 0;
            } else {

                return 1;
            }
        }
    });       
}

これは余分なスペースを使用しませんが、時間の複雑さは O(nlog(n)) です。さらに、その実装は簡潔です。

更新:以下は、余分なスペースの複雑さと O(n) 時間の複雑さのない別のエレガントなソリューションです。

private void sortMoves(final List<Move> moves, final int depth)
{

    int i = 0;
    int j = moves.size() - 1;

    while(i < j) {

        while(equalsKillersPrimary(moves.get(i), depth))
            i++;

        while(!equalsKillersPrimary(moves.get(j), depth))
            j--;

        swap(moves, i, j);
    }
}

private boolean equalsKillersPrimary(Move move, int depth) {

    return killers.primary[depth] != null && move.equals(killers.primary[depth]);
}

簡潔にするために の実装を省略しswap()ました。指定されたインデックスの要素を交換するだけです。

于 2013-03-19T15:00:54.440 に答える