Algorithm speed for an simple exercice

Question

=> Go to see Edit2 at the end :)

I am sorry but I don't speak English very well.. :)

The problem is simple. I have a file.txt with 10000 points. And I have to count the number of possible square.

For example : [-1,-1][2,1][4,-2][1,-4] is a square

I made an algorithm in java but there is a big problem... To execute it, I need 15hours !!!

I will give you my code, and if you think I can optimize it please tell me how ! :)

Main.java

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;

import elements.*;

public class Main
{
    public static void main(String[] parameters)
    {
        try
        {
            //String nameFile = parameters[0];
            FileInputStream fileInputStream = new FileInputStream(new File("exercice4.txt"));
            Processing processing = new Processing();
            processing.read(fileInputStream);
            processing.maxLenght();
            //processing.changeTest();
            processing.generateSquare();
            try 
            {
                FileWriter fileWriter = new FileWriter(new File("Square.txt"));
                processing.write(fileWriter);
                fileWriter.close();
            } 
            catch (IOException exception) 
            {
                System.out.println("Erreur lors de l'écriture dans le fichier");
            }
            System.out.println(processing.countSquare());
            System.out.println("Fin");
            try 
            {
                fileInputStream.close();
            } 
            catch (IOException exception) 
            {
                System.out.println("Une erreur s'est produite lors de la fermeture de l'InputStream");
            }
        }
        catch(FileNotFoundException exeption)
        {
            System.out.println("Le nom de fichier placé en paramètre est incorrect");
        }
    }
}

Processing.java

package elements;
import java.util.ArrayList;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.nio.file.*;

import elements.*;

public class Processing
{
    private ArrayList<Point> points;
    private ArrayList<Square> squares;
    private int maxY;
    private int maxX;
    private int minX;

    public Processing()
    {
        this.points = new ArrayList<Point>();
        this.squares = new ArrayList<Square>();
        this.maxX = 0;
        this.maxY = 0;
        this.minX = 0;
    }

    public void read(FileInputStream f)
    {
        int readReturn;
        int X = 0;
        int Y = 0;
        String string = "";
        try
        {
            while ((readReturn = f.read()) != -1)
            {
                if(readReturn-48 == -38)
                {
                    Y = Integer.parseInt(string);
                    Point point = new Point(X,Y);
                    if(!presentPoint(point))
                    {
                        points.add(point);
                    }
                    string = "";
                }
                else if(readReturn-48 == -16)
                {
                    X = Integer.parseInt(string);
                    string = "";
                }
                else if(readReturn-48 == -3)
                {
                    string += "-";
                }
                else
                {
                    string += Integer.toString(readReturn-48);
                }
            }
        }
        catch(IOException exception)
        {
            System.out.println("Probleme lors de la lecture du fichier");
        }
    }

    public void maxLenght()
    {
        Point reference = points.get(0);
        int maxX = reference.getX();
        int minX = reference.getX();
        int maxY = reference.getY();
        int minY = reference.getY();
        for(Point point : points)
        {
            if(point.getX() < minX)
            {
                minX = point.getX();
            }
            else if(point.getX() > maxX)
            {
                maxX = point.getX();
            }

            if(point.getY() < minY)
            {
                minY = point.getY();
            }
            else if(point.getY() > maxY)
            {
                maxY = point.getY();
            }
        }

        this.maxX = maxX;
        this.maxY = maxY;
        this.minX = minX;
    }

    public boolean samePoint(Point point1, Point point2)
    {
        boolean same = false;
        if(point1.getX() == point2.getX() && point1.getY() == point2.getY())
        {
            same = true;
        }
        return same;
    }

    public boolean presentPoint(Point newPoint)
    {
        boolean present = false;
        int counter = 0;
        Point point;
        while(present == false && counter < points.size())
        {
            point = this.points.get(counter);
            if(samePoint(point, newPoint))
            {
                present = true;
            }
            counter++;
        }
        return present;
    }

    public boolean presentPoint(Point botomRight, Point topLeft, Point topRight)
    {
        boolean present = false;
        boolean botomRightPresent = false;
        boolean topLeftPresent = false;
        boolean topRightPresent = false;
        int counter = 0;
        Point point;
        while(present == false && counter < points.size())
        {
            point = this.points.get(counter);
            if(samePoint(point, botomRight))
            {
                botomRightPresent = true;
            }
            if(samePoint(point, topLeft))
            {
                topLeftPresent = true;
            }
            if(samePoint(point, topRight))
            {
                topRightPresent = true;
            }
            if(botomRightPresent && topLeftPresent && topRightPresent)
            {
                present = true;
            }
            counter++;
        }
        return present;
    }

    public void generateSquare()
    {
        Point testBotomRight;
        Point testTopLeft;
        Point testTopRight;
        int counter = 0;
        for(Point point : this.points)
        {
            System.out.println(counter);
            counter++;
            for(int j = 0; j < this.maxY-point.getY(); j++)
            {
                for(int i = 1; i < this.maxX-point.getX(); i++)
                {
                    if(verifiyBoundary(i, j, point))
                    {
                        testBotomRight = new Point(point.getX()+i, point.getY()+j);
                        testTopLeft = new Point(point.getX()-j, point.getY()+i);
                        testTopRight = new Point(point.getX()+i-j, point.getY()+i+j);
                        if(presentPoint(testBotomRight, testTopLeft, testTopRight))
                        {
                            Square square = new Square(point, testBotomRight, testTopLeft, testTopRight);
                            this.squares.add(square);
                            System.out.println(point.display());
                            System.out.println(testBotomRight.display());
                            System.out.println(testTopLeft.display());
                            System.out.println(testTopRight.display());
                            System.out.println("");
                        }
                    }
                }
            }
        }
    }

    public boolean verifiyBoundary(int i, int j, Point point)
    {
        boolean verify = true;
        if(point.getX() + i + j > this.maxY)
        {
            verify = false;
        }
        if(point.getX() - j < this.minX)
        {
            verify = false;
        }
        return verify;
    }

    public String countSquare()
    {
        String nbSquare = "";
        nbSquare += Integer.toString(this.squares.size());
        return nbSquare;
    }

    public void changeTest()
    {
        Point point = points.get(9);
        point.setX(0);
        point.setY(0);

        point = points.get(100);
        point.setX(0);
        point.setY(2);

        point = points.get(1000);
        point.setX(2);
        point.setY(2);

        point = points.get(1886);
        point.setX(2);
        point.setY(0);
    }

    public void write(FileWriter fileWriter)
    {
        for(Square square : squares)
        {
            try 
            {
                fileWriter.write(square.getVertexBottomLeft().display() + square.getVertexBottomRight().display() + square.getVertexTopRight().display() + square.getVertexTopLeft().display() + "\r\n");
            } 
            catch (IOException e) 
            {
                System.out.println("Erreur lors de l'écriture des carrés");
            }
        }
    }
}

Point.java

package elements;

public class Point 
{
    private int X;
    private int Y;

    public Point(int X, int Y)
    {
        this.X = X;
        this.Y = Y;
    }

    public int getX()
    {
        return this.X;
    }

    public int getY()
    {
        return this.Y;
    }

    public void setX(int X)
    {
        this.X = X;
    }

    public void setY(int Y)
    {
        this.Y = Y;
    }

    public String display()
    {
        return ("[" + Integer.toString(this.X) + "," + Integer.toString(this.Y) + "]");
    }
}

Square.java

package elements;

public class Square
{
    private Point vertexBottomLeft;
    private Point vertexBottomRight;
    private Point vertexTopLeft;
    private Point vertexTopRight;

    public Square()
    {
        this.vertexBottomLeft = null;
        this.vertexBottomRight = null;
        this.vertexTopLeft = null;
        this.vertexTopRight = null;
    }

    public Square(Point vertexBottomLeft, Point vertexBottomRight, Point vertexTopLeft, Point vertexTopRight)
    {
        this.vertexBottomLeft = vertexBottomLeft;
        this.vertexBottomRight = vertexBottomRight;
        this.vertexTopLeft = vertexTopLeft;
        this.vertexTopRight = vertexTopRight;
    }

    public Point getVertexBottomLeft()
    {
        return this.vertexBottomLeft;
    }

    public Point getVertexBottomRight()
    {
        return this.vertexBottomRight;
    }

    public Point getVertexTopLeft()
    {
        return this.vertexTopLeft;
    }

    public Point getVertexTopRight()
    {
        return this.vertexTopRight;
    }
}

My programme stay 15h in the function generateSquare() in Processing.java

Thank you very much for your help !

Edit : I need to reduce the complexity = 1,000,000,000,000 how can I do that?

EDIT2 : Thanks to @BarrySW19 we reduce execution time : 5000ms now But I need to reduce at 200-500ms, somebody have an idea? I will give you the new code of Processing.java

package elements;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;

public class Processing
{
    private Set<Point> points;
    private List<Square> squares;
    private int maxY;
    private int maxX;
    private int minX;

    public Processing()
    {
        this.points = new HashSet<Point>();
        this.squares = new ArrayList<Square>();
        this.maxX = 0;
        this.maxY = 0;
        this.minX = 0;
    }

    /*
     * Fonction de lecture du fichier input qui stocke les points dans une structure de données adaptée
     * Ici la structure choisi de stockage de données est un hashSet.
     * param : InputStream lié au fichier dans lequel lire les données
     * 
     *  Suivant les valeur des entiers retournés on détecte un retour chariot (sauvegarde du point)
     *  ou un espace (saisie terminée de l'abscisse)
     */
    public void read(FileInputStream f)
    {
        int readReturn;
        int X = 0;
        int Y = 0;
        String string = "";
        try
        {
            while ((readReturn = f.read()) != -1)
            {
                if(readReturn-48 == -38)
                {
                    Y = Integer.parseInt(string);
                    Point point = new Point(X,Y);
                    if(!presentPoint(point))
                    {
                        points.add(point);
                    }
                    string = "";
                }
                else if(readReturn-48 == -16)
                {
                    X = Integer.parseInt(string);
                    string = "";
                }
                else if(readReturn-48 == -3)
                {
                    string += "-";
                }
                else
                {
                    string += Integer.toString(readReturn-48);
                }
            }
        }
        catch(IOException exception)
        {
            System.out.println("Probleme lors de la lecture du fichier");
        }
    }

    /*
     * Fonction qui sauvegarde les abscisses et ordonnés minimum et maximum des points présents
     * Ceci servira à l'optimisation du programme
     */
    public void maxLenght()
    {
        int maxX = -10000;
        int minX = 10000;
        int maxY = -10000;
        int minY = 10000;
        for(Point point : points)
        {
            if(point.getX() < minX)
            {
                minX = point.getX();
            }
            else if(point.getX() > maxX)
            {
                maxX = point.getX();
            }

            if(point.getY() < minY)
            {
                minY = point.getY();
            }
            else if(point.getY() > maxY)
            {
                maxY = point.getY();
            }
        }

        this.maxX = maxX;
        this.maxY = maxY;
        this.minX = minX;
    }

    /*
     * A l'aide de la réécriture de la fonction hashCode() et equals() cette fonction nous renvoie si un objet est présent dans le hashSet
     */
    public boolean presentPoint(Point newPoint)
    {
        return this.points.contains(newPoint);
    }

    /*
     * A l'aide de la réécriture de la fonction hashCode() et equals() cette fonction nous renvoie si un objet est présent dans le hashSet
     */
    public boolean presentPoint(Point botomRight, Point topLeft, Point topRight)
    {
        return (this.points.contains(botomRight) && this.points.contains(topRight) && this.points.contains(topLeft));
    }

    public void generateSquare() 
    {
        for(Point p: points) 
        {
            // Trouve tous les points pouvant servir de coin topRight
            Set<Point> pointsUpAndRight = points.stream().filter(p2 -> p2.getX() > p.getX() && p2.getY() >= p.getY()).collect(Collectors.toSet());
            for(Point p2: pointsUpAndRight) 
            {
                // calcul les vecteurs de trasformation
                int[] transform = new int[] { p2.getX() - p.getX(), p2.getY() - p.getY() };
                if(p.getY()+transform[0] <= this.maxY && p.getX()-transform[1] >= this.minX)
                {
                    // génère les 2 points manquants
                    Point p3 = new Point(p2.getX() - transform[1], p2.getY() + transform[0]);
                    Point p4 = new Point(p3.getX() - transform[0], p3.getY() - transform[1]);
                    if(points.contains(p3) && points.contains(p4)) 
                    {
                        Square s = new Square(p, p3, p2, p4);
                        squares.add(s);
                    }
                }
            }
        }
    }

    /*
     * Fonction de basique qui répond au problème de comptage de carré
     */
    public String countSquare()
    {
        String nbSquare = "";
        nbSquare += Integer.toString(this.squares.size());
        return nbSquare;
    }

    /*
     * Cette fonctionalité suplémentaire permet de stocker dans un fichier .txt les carrés présents parmi la liste de points
     */
    public void write(FileWriter fileWriter)
    {
        for(Square square : squares)
        {
            try 
            {
                fileWriter.write(square.getVertexBottomLeft().display() + square.getVertexBottomRight().display() + square.getVertexTopRight().display() + square.getVertexTopLeft().display() + " est un carré valide " + "\r\n");
            } 
            catch (IOException e) 
            {
                System.out.println("Erreur lors de l'écriture des carrés");
            }
        }
    }
}

How about you explain (in two sentences) what your algorithm is? It's great that you shared your code, but it would speed things up — shapiro yaacov
– shapiro yaacov, Commented Oct 27, 2015 at 11:34
I'm voting to migrate this question to codereview.stackexchange.com — StackFlowed
– StackFlowed, Commented Oct 27, 2015 at 11:37
Do you need to count the possible number of squares or 'generate' them ? — darthvading
– darthvading, Commented Oct 27, 2015 at 11:38
hmmm, well considering your code , the time complexity is O(n^3) == 1,000,000,000,000 iterations. so 15hrs is about right (if not more) — nafas
– nafas, Commented Oct 27, 2015 at 11:44
At the very least, presentPoint() is needlessly slow - define hashCode() and equals() for Point, use Set<Point> for the existing points and points.contains(myPoint) to check existence. — Jiri Tousek
– Jiri Tousek, Commented Oct 27, 2015 at 11:53

nafas · Accepted Answer · 2015-10-27 13:14:36Z

2

To check a value is contained in a Set has time complexity of O(1) while checking a value that contains in an array list has time complexity of O(n).

so one way to speed things up is to use Set rather than ArrayList

To use set you need to Override hashCode and equals methods:

add the following to your Point class

class Point{
...
 int hashCode=-1;


 @Override 
 public int hashCode(){
   if(hashCode==-1){
     hashCode=Objects.hash(x,y);
   }

   return hashCode;

 }

 @Override
 public boolean equals(Object o){
  if(o instanceOf this.getClass()){
   Point p=(Point) o;
   return p.x==x && p.y==y;
  }
  return false;

 }


}

in class Processing change:

private ArrayList<Point> points;

to:

private HashSet<Point> points;

then change your method presentPoint into something like:

public boolean presentPoint(Point p ){
 return points.contains(p);  
}


public boolean presentPoint(Point p1,Point p2,Point p3 ){
 return points.contains(p1) && points.contains(p2) && points.contains(p3);  
}

edited Oct 27, 2015 at 13:14

answered Oct 27, 2015 at 12:23

nafas

5,4533 gold badges34 silver badges59 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Damien Frances Over a year ago

Now it is very fast but it non-functioning ahah All Square are not seen now.. I just did that you said

nafas Over a year ago

@DamienFrances mate, I missed an = sign in hashCode function, i've edited it now

Damien Frances Over a year ago

no problem i saw it ;) but it is the algorithm which are false because all square are not seen..

nafas Over a year ago

hmm, strange, the logic is exactly as it was before. except one thing, that Set, doesn't allow duplicates, so two same points are not allowed in the set

Damien Frances Over a year ago

why when I debug at the first iteration the first point is : x = -38; y = 217 whereas normaly it is : x = 123; y = -825 as you can see on the picture posted..

|

BarrySW19 · Accepted Answer · 2015-10-27 19:47:16Z

2

EDIT: Changed solution to find squares rotated in any direction.

Ok, this is my stab at a solution - it should have O(N^2) performance. Firstly, I've replaced the List of points with a Set which automatically de-duplicates the set of points and also makes checking whether a point exists much faster (you need to implement equals() and hashCode() on the Point class for this to work).

Next, when checking for squares the first thing I do is build a Set of all points which are up and right of the current point (i.e. they could form the edge 0

In pseudo-code:

for each Point
   for each Point up and right of this
      calculate the other two points of the square
      if those points exists
         add the square to the answers
      end-if
   end-loop
end-loop

My version of the Processing class (just the important method) which implements this is:

import static java.util.stream.Collectors.toSet;

public class Processing {
    private Set<Point> points = new HashSet<>();
    private List<Square> squares = new ArrayList<>();

    public void generateSquare() {
        for(Point p: points) {
            // Find other points which could form a left-hand edge
            Set<Point> pointsUpAndRight = points.stream()
                    .filter(p2 -> p2.getX() >= p.getX() && p2.getY() > p.getY())
                    .collect(toSet());
            for(Point p2: pointsUpAndRight) {
                int[] transform = new int[] { p2.getX() - p.getX(), p2.getY() - p.getY() };
                Point p3 = new Point(p2.getX() + transform[1], p2.getY() - transform[0]);
                Point p4 = new Point(p3.getX() - transform[0], p3.getY() - transform[1]);
                if(points.contains(p3) && points.contains(p4)) {
                    Square s = new Square(p, p3, p2, p4);
                    squares.add(s);
                }
            }
        }
    }
}

edited Oct 27, 2015 at 19:47

answered Oct 27, 2015 at 12:56

BarrySW19

3,81715 silver badges26 bronze badges

10 Comments

Damien Frances Over a year ago

Thank you very much for your help but there is an error :/ What is groupingBy? Eclipse said that method is undefined

Damien Frances Over a year ago

Imagine there is a problem because he tells me that there are 0 squares finally.. :/

BarrySW19 Over a year ago

groupingBy should be statically imported as "import static java.util.stream.Collectors.groupingBy". "pointsAbove" will be a set of all points vertically above the current point on the Y-axis.

Damien Frances Over a year ago

I understood your code !! ahah But there is a problem :/ I will explain you and maybe you'll can resolve it :) I think code is good for square which have example point (0,0) (0,2) (2,0), (2,2) But square which have : (-1,-1) (2,1) (4,-2) (1,-4) is not seen by your algo.. Do you understand? My english is very bad ^^

BarrySW19 Over a year ago

Ah, I didn't realise it had to find squares rotated like that... hmm, will try and think of the best solution.

|

Community · Accepted Answer · 2017-05-23 12:15:42Z

1

Damien, the problem is that you spend a lot of time iterating through the List. Try to introduce data structure with quicker search, for example, Map with two keys.

If you have structure like

SpacialMap<Integer, Integer, Point>

you can perform fast Point existence check by its coordinates, so the computational complexity will drop to O(n^2) at least.

Look at this thread to get a hint, how to implement multikey maps: How to implement a Map with multiple keys?

EDIT: To improve further, the resulting algorithm can look like this:

Pick next point p from the list
For every point p1 such that p.y == p1.y && p.x < p1.x check if there are two more points present to complete the square (note that if you array is not sorted initially there could be two possible squares for each two points on the same ordinate)
If so, add 1 (or 2) to the squares counter.

edited May 23, 2017 at 12:15

CommunityBot

11 silver badge

answered Oct 27, 2015 at 12:02

ngund

951 gold badge1 silver badge9 bronze badges

6 Comments

Damien Frances Over a year ago

Thank you very much I will study this for the moment :) If somebody have an other idea don't hesitate and tell me :)

Pankaj Vaidya Over a year ago

Can you share a few lines of input please? (pouvez-vous quelques lignes de input sil vous plait)

Damien Frances Over a year ago

@ngund To do this I need to make two maps but I can't have co-ordinates with two maps.. It is not possible or I don't see how can I use it..

Damien Frances Over a year ago

@PankajVaidya I screened my input on the question :)

Pankaj Vaidya Over a year ago

Let me put it another way, what is ur input form? 1) 4 points per line? 2) All points on the same line? If yes, then do we count nested squares?

|

Collectives™ on Stack Overflow

Algorithm speed for an simple exercice

3 Answers 3

7 Comments

10 Comments

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

7 Comments

10 Comments

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related