A
A
Alexander Dorofeev2015-08-31 13:30:55
Java
Alexander Dorofeev, 2015-08-31 13:30:55

How to speed up filling HashMap?

I have a coordinate system (X,Y axes). I am given 4 numbers: x1,x2,y1,y2. These numbers are the vertices of a square -
the top right is x1,y1 and the bottom left is x2,y2.
You need to fill any array or collection with a matrix with 1 and 0. Where 1 is a square at this point, 0 is empty. Below is an example:

000000000
111111000
111111000
111111000
000000000

Indexes or Keys are X and Y coordinates.
I do it like this:
private Map<Pair<Integer, Integer>, Integer> calculateRectangleSquare(int x1, int x2, int y1, int y2) {

        int minY = Math.min(y1, y2);
        int minX = Math.min(x1, x2);
        int maxY = Math.max(y1, y2);
        int maxX = Math.max(x1, x2);
        Map<Pair<Integer, Integer>, Integer> rectSquare = new HashMap<Pair<Integer, Integer>,Integer>();
        for (int i = minX; i < maxX; i++) {
            for (int j = minY; j < maxY; j++) {
                Pair<Integer, Integer> key = new Pair<Integer, Integer>(i, j);
                rectSquare.put(key, true);
            }
        }
        return rectSquare;
    }

But the execution time grows exponentially! If the maximum x and y are equal to 10 or 100, then there is no problem!
However, it will never count 10000 at all. What algorithm can be used to improve the running time?
I tried to implement through a two-dimensional array, but I need to be able to work with negative
coordinates, but I don’t understand how to shift.

Answer the question

In order to leave comments, you need to log in

1 answer(s)
R
relgames, 2015-08-31
@relgames

Why Map?
Use a two-dimensional array int[][]
Then loop over the rows (first index) and fill through Arrays.fill

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question