java - 简单练习的算法速度

Question

=> 去最后看看 Edit2 :)

抱歉，我英语说得不太好..:)

问题很简单。我有一个包含 10000 点的 file.txt。 我必须计算可能的正方形的数量。

例如:[-1,-1][2,1][4,-2][1,-4]是一个正方形

我用java做了一个算法，但是有一个大问题...... 为了执行它，我需要15小时!!!

我会给你我的代码，如果你认为我可以优化它，请告诉我如何优化! :)

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

处理.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;
    }
}

我的程序在Processing.java中的generateSquare()函数中停留了15小时

非常感谢您的帮助!

编辑:我需要降低复杂性 = 1,000,000,000,000 我该怎么做？

EDIT2:感谢@BarrySW19，我们减少了执行时间:现在 5000 毫秒 但我需要减少 200-500ms，有人有主意吗？ 我会给你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

检查一个值是否包含在 Set 中的时间复杂度为 O(1)，而检查一个值是否包含在数组列表中的时间复杂度为 O(n)。

因此，加快速度的一种方法是使用 Set 而不是 ArrayList

要使用 set，您需要重写 hashCode 和 equals 方法:

将以下内容添加到您的 Point 类

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;

 }


}

在类处理中更改:

private ArrayList<Point> points;

至:

private HashSet<Point> points;

然后将您的方法 presentPoint 更改为:

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