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

Answer 1

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

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

Answer 3

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:

1. Pick next point p from the list
2. 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)
3. If so, add 1 (or 2) to the squares counter.