使用Union-find的降雨挑战解决方案

Question

我试图根据200_success♦(降雨挑战)的建议，实施一种解决降雨挑战的方案。

问题陈述一组农民有一些海拔数据，我们将帮助他们了解降雨是如何流过农田的。我们将土地表示为一个二维的高度阵列，并使用以下模型，基于水下坡的想法:如果一个细胞的四个相邻细胞都有较高的高度，我们称这个细胞为水槽；水聚集在水槽中。否则，水会流向海拔最低的邻近细胞。如果一个单元不是接收器，您可以假设它有一个唯一的最低邻居，并且这个邻居将低于单元格。直接或间接流入同一水槽的细胞据说是同一盆地的一部分。你的挑战是把地图划分成盆地。特别是，给定一个海拔图，您的代码应该将地图划分为盆地，并按降序输出盆地的大小。假设高程图是正方形的。输入将以一个整数开始，S，地图的高度(和宽度)。下一条S线将分别包含一排地图，每一行都带有S整数--这一行中的加高单元格。有些农民有小块地，如下面的例子，而有些人则有较大的地块。然而，在任何情况下，农民都不会拥有超过S= 5000的一块土地。您的代码应该输出一个按降序排列的盆地大小的空格分隔列表。(忽略尾随空格。)下面是几个例子：A，B，A，A，用A‘s标记的盆地是:a还有C的A、B、B、A、B、C、B、C、B、B、C、B、B、3 3 3 5 5 2 1盆地，用A，B，C标记的是:A，B，C，A，B，B，C是:A，B，C是:A，B，C，是:A，B，C是:A，B，C

代码是用java编写的。如果有人能复习的话那就太好了。

class Topography {

    int[][] elevationData;
    Cell[][] map;
    List<Basin> basinList;

    Topography(int[][] elevationData) {

        this.elevationData = elevationData;
        this.basinList = new ArrayList<Basin>();
        this.map = new Cell[elevationData.length][elevationData.length];
    }

    private class Cell {

        int altitude;
        Basin basin;

        Cell(int altitude) {

            this.altitude = altitude;
            this.basin = new Basin(this);
        }
    }

    private class Basin {

        Cell sinkCell;
        HashSet<Cell> memberCells;

        Basin(Cell sinkCell) {

            this.sinkCell = sinkCell;
            this.memberCells = new HashSet<Cell>();
            this.memberCells.add(sinkCell);
        }

    }

    private class BasinComparator implements Comparator<Basin> {

        public int compare(Basin basin1, Basin basin2) {

            if( basin1.memberCells.size() < basin2.memberCells.size() )
                return 1;

            else if( basin1.memberCells.size() > basin2.memberCells.size() )
                return -1;

            else 
                return 0;
        }
    }

    private void createTopography() {

        Cell tmpCell;
        for(int i=0; i<elevationData.length; i++) {

            for(int j=0; j<elevationData.length; j++) {

                tmpCell = new Cell(elevationData[i][j]);
                map[i][j] = tmpCell;
                basinList.add(tmpCell.basin);

            }
        }
    }

    private Cell findSink(Cell cell) {

        if(cell == null)
            return null;

        if(cell != cell.basin.sinkCell) {
            cell.basin.sinkCell = findSink(cell.basin.sinkCell);
        }

        return cell;
    }

    private void union(Cell cellX, Cell cellY) {

        Cell sinkX = findSink(cellX);
        Cell sinkY = findSink(cellY);

        if(sinkX == null || sinkY == null || sinkX == sinkY)
            return;

        if(sinkX.altitude > sinkY.altitude) {
            sinkY.basin.memberCells.addAll(sinkX.basin.memberCells);
            basinList.remove(sinkX.basin);
            sinkX.basin = sinkY.basin;
        } else {
            sinkX.basin.memberCells.addAll(sinkY.basin.memberCells);
            basinList.remove(sinkY.basin);
            sinkY.basin = sinkX.basin;
        }
    }

    void printBasinLength() {

        createTopography();

        for(int i=0; i<map.length; i++) {

            for(int j=0; j<map.length; j++) {

                Cell current_cell = map[i][j];
                Cell minNeighbor = findMinimumNeighbor(i, j, current_cell);

                if(minNeighbor != current_cell) {

                    union(minNeighbor, current_cell);
                }
            }
        }

        Collections.sort(basinList, new BasinComparator());

        for(Basin basin: basinList)
            System.out.print(basin.memberCells.size()+ " ");

    }

    private Cell findMinimumNeighbor(int i, int j, Cell current_cell) {

        Cell min = current_cell;

        if(i>0){

            if(map[i-1][j].altitude < min.altitude)
                min = map[i-1][j];

        }

        if(i<map.length-1){

            if(map[i+1][j].altitude < min.altitude)
                min = map[i+1][j];

        }

        if(j>0) {

            if(map[i][j-1].altitude < min.altitude)
                min = map[i][j-1];

        }

        if(j<map.length-1){

            if(map[i][j+1].altitude < min.altitude)
                min = map[i][j+1];
        }

        return min;
    }

}

Answer 1

有趣的问题！这看上去很不错。

尽管如此，总有一些东西需要改进..。;)

格式

1.空白空间

你似乎有很多的空白，很多时候没有特定的意义。

我能理解空格，把一段代码切成子动作(如果可能的话，提取方法会更好)。但是为什么所有的线都跳到了ifs，fors和方法定义之后？这就是缩进的目的。因此，您的行跳转看起来是多余的，它们会防止出现大量代码块，并且会引发大量滚动。

2.缺少括号.

在使用括号和不使用括号之间交替使用。强烈建议在任何地方使用括号。IDE会将它们插入ou，即使它们的存在不需要读取代码，但在编辑代码时也会有所帮助，因为添加一个else子句的指令是非常明显的。

对于此规则，我使用的一个例外情况是，我不添加else if系列中的括号以使缩进易于管理：

if(conditionA) {
    // Do something, in either a one-liner is in brackets
} else if {
    // Do something else
}

3. Javadoc

它在哪里?

拥有它总是很好，而且真的很容易。当你回到你的代码，发现它是Javadoc‘’ed，然后想“好样”:D

4.嵌套ifs

if(i>0){
    if(map[i-1][j].altitude < min.altitude)
        min = map[i-1][j];
}

这相当于：

if(i > 0 && if(map[i-1][j].altitude < min.altitude) {
    min = map[i-1][j];
}

但最后一次剪裁的凹痕较小，而且较短。如果你想留出空间做几个内部的假设，打破如果条件是好的，但这显然不是在这里。

此外，对于轮询相邻单元格，您可能需要筛选像[[0, -1], [0, 1], [-1, 0], [1, 0]]这样的偏移数组，并创建一个通用的checkBound(int i, int j)方法。这是很容易扩展的，例如对8个连接的细胞。

Architecture

1.外部Comparators

为什么要将比较器外部化？你认为你有时会使用不同的比较器吗？我怀疑，这是一门高度专业化的课程。您应该让Basin实现Comparable<Basin>。

2.单一责任

printBasinLength从调用createTopography开始。然后继续把盆地结合起来。等等，这不是交易的一部分！根据它的名称(在没有Javadoc的情况下)，它应该只打印一些东西，而不是计算它。如果它已经被计算了呢？

你应该把计算、呈现和打印分开。您已经完成了部分工作，您只需要将printBasinLength分解为逻辑组件：

• 将该createTopography()调用从
• 移动这些for...for...union调用，并将它们放入一个新的void mergeBasins()‘业务’方法中
• 移动sortBasinsBySurface()方法中的排序
• 在String getRepresentation()方法中将版画分解为连接盆地的调用
• 永远不要在业务方法中使用System.out。在main()最后一步移动它。如果没有，使用该框架的任何人都将在控制台上获得这些打印，而不需要对其进行任何控制。

然后做一个：

public String splitTopologyInBasins(){
    createTopography();
    sortBasinsBySurface();
    mergeBasins()
    return getRepresentation();
}

算法

你选择：

• 每个单元格立即实例化一个对象
• 然后在每个单元格中进行一次传递：
  • 然后你会发现它的最低邻居
  • 通过：对他们的汇进行联合
    • 两个人都想找到他们的水槽

安装所有细胞的成本是不必要的，它们可能是懒洋洋地生成的。懒惰的许多改进：

• 在已知单元格中流动的单元格只剩下很少的工作:只要复制完数据，接收器就会是相同的。
• 因为正在流动的细胞不是汇，它们不需要在一开始就为它们生成一个盆地，然后通过联合将其删除。

我宁愿从任何地方都没有单元格开始，并使用递归函数在返回它们的汇的过程中创建一组单元格，并且只在我到达的时候为它们创建一个盆地(除非接收器单元已经存在，或者遇到了以前存在的单元，那么每个人都继承了该盆地)。在双for-循环中，您只需跳过任何已经生成的单元格。这大大减少了流域(和清单)和合并的数量。