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;
    }

有没有更好，更有效的方法（即相交两个列表并返回一个排序列表）？

注意：该函数的目标是删除移动列表中的杀手移动（主要），然后返回一个新列表，其中首先是杀手移动，然后是原始移动列表中的列表。

4

2 回答 2

2

快速排序列表尝试

Collections.sort(列表列表);

或者

Collections.sort(List list,Comparator c)

于 2013-03-19T14:36:45.387 回答
1

如果你moves不是太大，当前的实现看起来还可以。它的复杂度是 O(n)。唯一的缺点是由于三个额外的列表即空间复杂度。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 回答