CS Mines Flood Fill 问题 - Java 解决方案超时，而 Cpp 和 python 成功（性能改进）

问题描述 投票：0回答：1

致力于解决这个问题

https://mines20.kattis.com/problems/mines20.paintbucket

Java使用TreeSet的解决方案超时时间限制小于3秒

public class PaintBucketCSMinesSolution {

    public static void main(String[] args) throws IOException {
        // maintain distinct list of points that have been visited
        Set<int[]> exploredSet = new TreeSet<>(
                Comparator.comparingInt((int[] el) -> el[1]).thenComparingInt(el -> el[0]));
        int W;
        int H;
        int X;
        int Y;
        int[][] picture;
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(r.readLine());
        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        Y = Integer.parseInt(st.nextToken());
        picture = new int[H][W];
        for (int i = 0; i < H; i++) {
            st = new StringTokenizer(r.readLine());
            for (int j = 0; j < W; j++) {
                picture[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int color = picture[Y][X];

        Stack<int[]> toExploreStack = new Stack<>();

        toExploreStack.add(new int[] { X, Y });

        while (!toExploreStack.isEmpty()) {
            int[] point = toExploreStack.pop();
            int px = point[0];
            int py = point[1];
            // System.out.println(exploredSet.contains(point));
            boolean execute = true;

            if (exploredSet.contains(point)) {
                execute = false;
            }

            if (execute) {
                exploredSet.add(point);

                if (px > 0 && picture[py][px - 1] == color) {
                    toExploreStack.add(new int[] { px - 1, py });
                }

                if (px < (W - 1) && picture[py][px + 1] == color) {
                    toExploreStack.add(new int[] { px + 1, py });
                }

                if (py > 0 && picture[py - 1][px] == color) {
                    toExploreStack.add(new int[] { px, py - 1 });
                }

                if (py < (H - 1) && picture[py + 1][px] == color) {
                    toExploreStack.add(new int[] { px, py + 1 });
                }
            }

        }
        // exploredSet.sort(Comparator.comparingInt((int[] el) ->
        // el[1]).thenComparingInt(el -> el[0]));
        // Sorting HashSet using List

        for (int[] v : exploredSet) {
            System.out.println(v[0] + " " + v[1]);
        }

    }
}

Java HashSet解决方案，同样超时

package datastructures.algorithms;

import java.io.IOException;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class PaintBucketCSMinesSolution {

    public static void main(String[] args) throws IOException {
        // maintain distinct list of points that have been visited
//      Set<int[]> exploredSet = new TreeSet<>(
//              Comparator.comparingInt((int[] el) -> el[1]).thenComparingInt(el -> el[0]));
        Set<List<Integer>> exploredSet = new HashSet<>();
        int W;
        int H;
        int X;
        int Y;
        int[][] picture;
        Scanner sc = new Scanner(System.in);
        W = sc.nextInt();
        H = sc.nextInt();
        X = sc.nextInt();
        Y = sc.nextInt();
        picture = new int[H][W];
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                picture[i][j] = sc.nextInt();
            }
        }
        sc.close();
        int color = picture[Y][X];

        ArrayDeque<List<Integer>> toExploreStack = new ArrayDeque<>();

        toExploreStack.add(Arrays.asList(X, Y));

        while (!toExploreStack.isEmpty()) {
            List<Integer> point = toExploreStack.pop();
            int px = point.get(0);
            int py = point.get(1);
            // System.out.println(exploredSet.contains(point));
            boolean execute = true;

            if (exploredSet.contains(point)) {
                execute = false;
            }

            if (execute) {
                exploredSet.add(point);

                if (px > 0 && picture[py][px - 1] == color) {
                    toExploreStack.add(Arrays.asList(px - 1, py));
                }

                if (px < (W - 1) && picture[py][px + 1] == color) {
                    toExploreStack.add(Arrays.asList(px + 1, py));
                }

                if (py > 0 && picture[py - 1][px] == color) {
                    toExploreStack.add(Arrays.asList(px, py - 1));
                }

                if (py < (H - 1) && picture[py + 1][px] == color) {
                    toExploreStack.add(Arrays.asList(px, py + 1));
                }
            }

        }

        // Sorting HashSet using List

        // exploredSet.sort(Comparator.comparingInt((List<Integer> el) ->
        // el.get(1)).thenComparingInt(el -> el.get(0)));
        Comparator<List<Integer>> comp = Comparator.comparingInt((List<Integer> x) -> x.get(1))
                .thenComparingInt(x -> x.get(0));
        exploredSet.stream().sorted(comp).map(v -> v.get(0) + " " + v.get(1)).forEach(System.out::println);

    }
}

Java HashSet String解决方法也超时

package datastructures.algorithms;

import java.io.IOException;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class PaintBucketStringSolution {

    public static void main(String[] args) throws IOException {
        // maintain distinct list of points that have been visited
//      Set<int[]> exploredSet = new TreeSet<>(
//              Comparator.comparingInt((int[] el) -> el[1]).thenComparingInt(el -> el[0]));
        Set<String> exploredSet = new HashSet<>();
        int W;
        int H;
        int X;
        int Y;
        int[][] picture;
        Scanner sc = new Scanner(System.in);
        W = sc.nextInt();
        H = sc.nextInt();
        X = sc.nextInt();
        Y = sc.nextInt();
        picture = new int[H][W];
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                picture[i][j] = sc.nextInt();
            }
        }
        sc.close();
        int color = picture[Y][X];

        ArrayDeque<List<Integer>> toExploreStack = new ArrayDeque<>();

        toExploreStack.add(Arrays.asList(X, Y));

        while (!toExploreStack.isEmpty()) {
            List<Integer> point = toExploreStack.pop();

            int px = point.get(0);
            int py = point.get(1);
            // String.valueOf(
            String pointString = String.valueOf(px) + " " + String.valueOf(py);
            // System.out.println(exploredSet.contains(point));
            boolean execute = true;

            if (exploredSet.contains(pointString)) {
                execute = false;
            }

            if (execute) {
                exploredSet.add(pointString);

                if (px > 0 && picture[py][px - 1] == color) {
                    toExploreStack.add(Arrays.asList(px - 1, py));
                }

                if (px < (W - 1) && picture[py][px + 1] == color) {
                    toExploreStack.add(Arrays.asList(px + 1, py));
                }

                if (py > 0 && picture[py - 1][px] == color) {
                    toExploreStack.add(Arrays.asList(px, py - 1));
                }

                if (py < (H - 1) && picture[py + 1][px] == color) {
                    toExploreStack.add(Arrays.asList(px, py + 1));
                }
            }

        }

        // Sorting HashSet using List

        exploredSet.stream().sorted(Comparator.comparing(x -> {
            String[] s = x.split(" ");
            return s[1] + " " + s[0];
        })).forEach(System.out::println);

    }
}

虽然 python 中的解决方案在 2.65 秒内成功解决了所有测试用例

W, H,X,Y = map(int, input().split())

picture=[]

for y in range(H):
    picture.append([int(c) for c in input().split()])

#print(picture)
# implement a stack
to_explore = [(X , Y)]
explored=set()
color = picture[Y][X]
#print("color" , color)

while len(to_explore) >0:
    px, py = to_explore.pop()

    if(px, py) in explored:
        continue
    explored.add((px, py))

    if (px > 0 and picture[py][px - 1] == color) :
       to_explore.append( (px - 1, py ))

    if (px < (W - 1) and picture[py][px + 1] == color) :
        to_explore.append((px + 1, py ))


    if (py > 0 and picture[py - 1][px] == color) :
        to_explore.append( (px, py - 1) )

    if (py < (H - 1) and picture[py + 1][px] == color) :
        to_explore.append(( px, py + 1) )
        
for x,y in sorted(explored, key=lambda x: (x[1], x[0])):
    print(x, y)

CPP 解决方案在 2.05 秒内完成

#include <algorithm>
#include <array>
#include <iostream>
#include <set>
#include <stack>
#include <vector>

int main() {
    // comparison to sort the set naturally on inserting elements
    const auto compare = [](const std::array<int, 2> &lhs,
                            const std::array<int, 2> &rhs) {
        return lhs[1] < rhs[1] || (lhs[1] == rhs[1] && lhs[0] < rhs[0]);
    };

    // set to maintain unique elements as it is used for lookup to check if we have visited the node already
    std::set<std::array<int, 2>, decltype(compare)> exploredSet(compare);
    // std::set<std::array<int, 2>> exploredSet;
    int W;
    int H;
    int X;
    int Y;
    // std::vector<std::vector<int>> picture;
    std::cin >> W;
    std::cin >> H;
    std::cin >> X;
    std::cin >> Y;
    int picture[W][H];
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            std::cin >> picture[i][j];
        }
    }
    int color = picture[Y][X];

    std::stack<std::array<int, 2>> toExploreStack;
    toExploreStack.push({X, Y});

    while (!toExploreStack.empty()) {
        std::array<int, 2> point = toExploreStack.top();
        toExploreStack.pop();
        int px = point[0];
        int py = point[1];
        bool execute = true;

        // plain for loop was slow, this method is fast
        if (exploredSet.count(point) == 1) {
            execute = false;
        }

        if (execute) {
            exploredSet.insert(point);

            if (px > 0 && picture[py][px - 1] == color) {
                toExploreStack.push({px - 1, py});
            }

            if (px < (W - 1) && picture[py][px + 1] == color) {
                toExploreStack.push({px + 1, py});
            }

            if (py > 0 && picture[py - 1][px] == color) {
                toExploreStack.push({px, py - 1});
            }

            if (py < (H - 1) && picture[py + 1][px] == color) {
                toExploreStack.push({px, py + 1});
            }
        }
    }

    for (std::array<int, 2> v : exploredSet) {
        std::cout << v[0] << " " << v[1] << std::endl;
    }
}

请帮助优化Java解决方案。我的想法已经用完了。

已经试过了

  • HashMap 并在最后排序
  • HashSet最后排序

令人惊讶的是，在这种情况下，python 能够比 Java 实现更快地完成。

java algorithm performance hashset treeset
1个回答
0
投票

TreeSet
与自定义比较器的组合似乎有太多开销。 
HashSet
版本应该可以工作，并且与其他版本的逻辑相同。您只需要处理对象即可获得适当的
hashCode
。 您可以尝试将相关行更改为：

Set<List<Integer>> exploredSet = new HashSet<>();
...
if (exploredSet.contains(Arrays.asList(px, py))) {
...
exploredSet.add(Arrays.asList(px, py));
...
Comparator<List<Integer>> comp = Comparator.comparingInt((List<Integer> x) -> x.get(1)).thenComparingInt(x -> x.get(0));
exploredSet.stream()
        .sorted(comp)
        .map(v -> v.get(0) + " " + v.get(1))
        .forEach(System.out::println);

编辑

一般来说，如果 Python 解决方案在时限内，具有相同逻辑的等效 Java 版本也应该是。那为什么不呢？ “正确的哈希码”——这正是我的解决方案的问题……对不起，我是瞎子。 Java有一个非常简单的

hashCode
函数。对于坐标列表
X, Y
，它只是
X + 31*Y
。所以有很多碰撞。对于 
0 <= X, Y <= 999
，只有 31969 个不同的哈希码。这减慢了整个过程。使用字符串应该更快，并希望在时间限制内：

Set<String> exploredSet = new HashSet<>();
...
if (exploredSet.contains(px + " " + py)) {
...
exploredSet.add(px + " " + py);
...
exploredSet.stream()
        .sorted(Comparator.comparing(x -> {
            String[] s = x.split(" ");
            return s[1] + " " + s[0]; }))
        .forEach(System.out::println);

编辑2

这真的很奇怪。他们可能对 python 机器进行了拉皮条。好的，最后一次尝试使用布尔数组 

explored
而不是 Set 
exploredSet
。那应该快得多，但它没有回答为什么 HashSet 版本这么慢。

boolean[] explored = new boolean[H*W]; // <- put this line after the 2 for-loops
...
if (explored[py*H+px]) {
...
explored[py*H+px] = true;
...
int index = 0;
for(int y=0; y<H; y++){
    for(int x=0; x<W; x++){
        if(explored[index]){
            System.out.println(x + " " + y);
        }
        index++;
    }
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.