Análisis de pantalones cortos del archivo binario y encontrar los puntos más cercanos y más lejanos -- java campo con performance campo con interview-questions campo con serialization campo con computational-geometry camp codereview Relacionados El problema

Parsing shorts from binary file and finding the closest and furthest points


5
vote

problema

Español

Hace unos meses me rechazaron en la entrevista técnica para una posición.

El problema que me dieron es lo siguiente:

de un archivo binario, analice dos pantalones cortos, X e Y y cree un objeto de punto con estas coordenadas.

Repita el proceso hasta que no haya más pantalones cortos para analizar. Desde todos esos puntos, devuelva los 10 puntos más cercanos al punto -200,300 y los puntos más lejanos del punto 1000,25.

¿Podría ayudarme a identificar lo que puedo hacer diferente para aumentar el rendimiento de mi programa?

También, por favor, dame alguna sugerencia general o punteros para mejorar mi código.

  public class Main {      private static final Point closest = new Point(-200, 300);     private static final Point furthest = new Point(1000, 25);     private static final int POINTS_IN_FILE = 10000000;      private static final Comparator<Point> closestComparator = new Comparator<Point>() {         @Override         public int compare(Point o1, Point o2) {             Double firstDistance = o1.distance(closest);             Double secondDistance = o2.distance(closest);              return - firstDistance.compareTo(secondDistance);         }     };      private static final Comparator<Point> furthestComparator = new Comparator<Point>() {         @Override         public int compare(Point o1, Point o2) {             Double firstDistance = o1.distance(furthest);             Double secondDistance = o2.distance(furthest);              return firstDistance.compareTo(secondDistance);         }     };      public static void main(String[] args) throws IOException {          String pathToFile;          for (String arg : args) {              pathToFile = arg;              try (DataInputStream stream = new DataInputStream(                     new BufferedInputStream(new FileInputStream(new File(pathToFile))))) {                  Point[] pointArray = new Point[POINTS_IN_FILE];                 readPointsIntoArray(pointArray, stream);                 calculateFirstPoints(pointArray, false, 10);                 calculateFirstPoints(pointArray, true, 20);             }         }     }      private static void calculateFirstPoints(Point[] pointArray, boolean furthest, int size) {         Comparator<Point> pointComparator = furthest? furthestComparator : closestComparator;         LimitedPriorityQueueWrapper<Point> pointWrapper = new LimitedPriorityQueueWrapper<>(size, pointComparator);         pointWrapper.bulkInsertToQueue(pointArray);         List<Point> resultList = pointWrapper.getElements();         printPoints(resultList);     }      private static void readPointsIntoArray(Point[] points, DataInputStream stream) {         int index = 0;         while (true) {             try {                 Point currentPoint = new Point(stream.readShort(), stream.readShort());                 points[index] = currentPoint;                 index++;             } catch (Exception e) {                 break;             }         }     }      private static void printPoints(List<Point> points) {         for (Point point : points) {             System.out.println(point.toString());         }     } }   

Esta es una clase auxiliar que creé con una cola de prioridad interna. Su propósito es insertar los puntos en el orden correcto, así que no tengo que ordenar la colección más adelante.

  public class LimitedPriorityQueueWrapper<T> {      private PriorityQueue<T> queue;     private int size;     private boolean sizeReached = false;      public LimitedPriorityQueueWrapper(int size, Comparator<T> comparator) {         this.queue = new PriorityQueue<T>(comparator);         this.size = size;     }      public void insertIntoQueue(T t) {         queue.add(t);         if (sizeReached) {             queue.poll();             return;         }         if (queue.size() >= size) {             sizeReached = true;         }     }      public void bulkInsertToQueue(T[] array) {         for (int i=0; i<array.length; i++) {             insertIntoQueue(array[i]);         }     }      public List<T> getElements() {         return new ArrayList<T>(queue);     }   }   

Todos los consejos que puedes darme serán muy apreciados.

Original en ingles

A few months ago I got rejected at the technical interview for a position.

The problem that they gave me is the following:

From a binary file, parse two shorts, x and y and build a Point object with these coordinates.

Repeat the process until there is no more shorts to parse. From all those points, return the 10 closest points to the point -200,300 and the furthest points from the point 1000,25.

Could you help me to identify what I can do different to increase the performance of my program?

Also, please give me any general suggestions or pointers to improve my code.

public class Main {      private static final Point closest = new Point(-200, 300);     private static final Point furthest = new Point(1000, 25);     private static final int POINTS_IN_FILE = 10000000;      private static final Comparator<Point> closestComparator = new Comparator<Point>() {         @Override         public int compare(Point o1, Point o2) {             Double firstDistance = o1.distance(closest);             Double secondDistance = o2.distance(closest);              return - firstDistance.compareTo(secondDistance);         }     };      private static final Comparator<Point> furthestComparator = new Comparator<Point>() {         @Override         public int compare(Point o1, Point o2) {             Double firstDistance = o1.distance(furthest);             Double secondDistance = o2.distance(furthest);              return firstDistance.compareTo(secondDistance);         }     };      public static void main(String[] args) throws IOException {          String pathToFile;          for (String arg : args) {              pathToFile = arg;              try (DataInputStream stream = new DataInputStream(                     new BufferedInputStream(new FileInputStream(new File(pathToFile))))) {                  Point[] pointArray = new Point[POINTS_IN_FILE];                 readPointsIntoArray(pointArray, stream);                 calculateFirstPoints(pointArray, false, 10);                 calculateFirstPoints(pointArray, true, 20);             }         }     }      private static void calculateFirstPoints(Point[] pointArray, boolean furthest, int size) {         Comparator<Point> pointComparator = furthest? furthestComparator : closestComparator;         LimitedPriorityQueueWrapper<Point> pointWrapper = new LimitedPriorityQueueWrapper<>(size, pointComparator);         pointWrapper.bulkInsertToQueue(pointArray);         List<Point> resultList = pointWrapper.getElements();         printPoints(resultList);     }      private static void readPointsIntoArray(Point[] points, DataInputStream stream) {         int index = 0;         while (true) {             try {                 Point currentPoint = new Point(stream.readShort(), stream.readShort());                 points[index] = currentPoint;                 index++;             } catch (Exception e) {                 break;             }         }     }      private static void printPoints(List<Point> points) {         for (Point point : points) {             System.out.println(point.toString());         }     } } 

This is a helper class that I created with an inner priority queue. Its purpose is to insert the points in the correct order so I don't have to sort the collection later.

public class LimitedPriorityQueueWrapper<T> {      private PriorityQueue<T> queue;     private int size;     private boolean sizeReached = false;      public LimitedPriorityQueueWrapper(int size, Comparator<T> comparator) {         this.queue = new PriorityQueue<T>(comparator);         this.size = size;     }      public void insertIntoQueue(T t) {         queue.add(t);         if (sizeReached) {             queue.poll();             return;         }         if (queue.size() >= size) {             sizeReached = true;         }     }      public void bulkInsertToQueue(T[] array) {         for (int i=0; i<array.length; i++) {             insertIntoQueue(array[i]);         }     }      public List<T> getElements() {         return new ArrayList<T>(queue);     }   } 

All the advice that you can give me will be very appreciated.

              
 
 

Lista de respuestas

8
 
vote

Dado que esto fue para una entrevista, se abstendrá de decir que Falta Javadoc.


   private static final Point closest = new Point(-200, 300);   

¡Eso es una violación de las directrices de estilo Java, las constantes deben denominarse Upper_Camelcase. Sin mencionar que el nombre podría ser mejor.

  private static final Point CLOSEST_POINT = new Point(-200, 300);   

  private static final int POINTS_IN_FILE = 10000000; ... Point[] pointArray = new Point[POINTS_IN_FILE];   

Estoy en la línea cinco y puedo decirle que le habría fallado en este punto. Tus especificaciones no dicen que hay 10 millones de puntos, ¿verdad? Estás asignando al menos 190 megabyte con esta declaración (acabo de probarlo) para una matriz que es superflua. Un List sería mucho más adecuado ya que puede crecer según sea necesario. Aún mejor sería dos 9988777665544334 S que solo sostienen 10 puntos cada uno, los cierran y los puntos más lejanos.

Aunque la especificación que publicó dice algo como "analizar todos los flotadores ... devolver el más cercano y más lejano", en realidad, combinaría estos dos pasos:

  1. LEA Point de la entrada.
  2. Compruebe si Point está más o cerrado que los diez puntos ya reunidos.
  3. Drop la "MENOS AJUSTE" Point de la lista.
  4. Agregar el nuevo Point .

De esta manera, su uso de memoria es aproximadamente para las instancias de 20 99887766555443339 , y solo está comparando cada 998877766655443310 contra 20 valores. Esto se puede acelerar al almacenar en caché el punto "más alejado" y "más cercano" por separado, porque entonces solo debe comparar cada lectura 99887766655443311 contra dos otros private static final Point CLOSEST_POINT = new Point(-200, 300); 2 , y solo si Más lejos o más cerca debe comparar contra los otros diez.


  private static final Point CLOSEST_POINT = new Point(-200, 300); 3  

su private static final Point CLOSEST_POINT = new Point(-200, 300); 4 no debe lanzar private static final Point CLOSEST_POINT = new Point(-200, 300); 5 S, debe manejarlos y fallar con gracia.


  private static final Point CLOSEST_POINT = new Point(-200, 300); 6  

Declare las variables donde se usan, en este caso dentro del bucle, para limitar su alcance.

  private static final Point CLOSEST_POINT = new Point(-200, 300); 7  

  private static final Point CLOSEST_POINT = new Point(-200, 300); 8  

No estás realizando ningún tipo de cheques aquí. ¿Qué pasa si el private static final Point CLOSEST_POINT = new Point(-200, 300); 9 está vacío? ¿Qué pasa si no es un camino válido? ¿Qué pasa si el archivo no existe?

  private static final int POINTS_IN_FILE = 10000000; ... Point[] pointArray = new Point[POINTS_IN_FILE]; 0  

  private static final int POINTS_IN_FILE = 10000000; ... Point[] pointArray = new Point[POINTS_IN_FILE]; 1  

No tengo idea de lo que estás haciendo aquí ...

¿Por qué no pasar el comparador "correcto" como parámetro? Deshazaría el private static final int POINTS_IN_FILE = 10000000; ... Point[] pointArray = new Point[POINTS_IN_FILE]; 2 y sería más expresivo.


  private static final int POINTS_IN_FILE = 10000000; ... Point[] pointArray = new Point[POINTS_IN_FILE]; 3  

Cada vez que escribe private static final int POINTS_IN_FILE = 10000000; ... Point[] pointArray = new Point[POINTS_IN_FILE]; 4 Te quiero, a partir de ahora, para levantar las manos del teclado, colóquelas en la parte posterior de la cabeza y piense al menos por un minuto sobre por qué solo Hizo eso y si pudiera haber otra forma de hacer esto. Observe cómo su código nunca verifica si hay demasiados shorts disponibles para la matriz para sujetar.

  private static final int POINTS_IN_FILE = 10000000; ... Point[] pointArray = new Point[POINTS_IN_FILE]; 5  

Alternativamente con un private static final int POINTS_IN_FILE = 10000000; ... Point[] pointArray = new Point[POINTS_IN_FILE]; 6 :

  private static final int POINTS_IN_FILE = 10000000; ... Point[] pointArray = new Point[POINTS_IN_FILE]; 7  

Idealmente, su código se vería algo así (pseudo-código):

  private static final int POINTS_IN_FILE = 10000000; ... Point[] pointArray = new Point[POINTS_IN_FILE]; 8  

o algo así. Usted encapsula toda la lógica requerida para leer, comparar y recopilar puntos en una clase de instancia que se puede reutilizar.

 

Given that this was for an interview I'll refrain from saying that Javadoc is missing.


 private static final Point closest = new Point(-200, 300); 

That's a violation of the Java Style Guidelines, constants are to be named UPPER_CAMELCASE. Not to mention that the name could be better.

private static final Point CLOSEST_POINT = new Point(-200, 300); 

private static final int POINTS_IN_FILE = 10000000; ... Point[] pointArray = new Point[POINTS_IN_FILE]; 

I'm just at line five and I can tell you that I would have failed you at this point. Your specs do not say that there are 10 million points, right? You're allocating at least 190 megabyte with this declaration (I just tried it) for an array which is superfluous. A List would be much better suited as it can grow as needed. Even better would be two Lists which only hold 10 points each, the closes and farthest points.

Even though the spec you posted says something like "parse all floats...return the closest and farthest" I'd actually combine these two steps:

  1. Read Point from input.
  2. Check if Point is further or closed than the already gathered ten points.
  3. Drop the "least fitting" Point from the list.
  4. Add the new Point.

This way your memory usage is roughly for 20 Point instances, and you are only comparing each Point against 20 other values. This can be further speed up by caching the "furthest" and "closest" point separately, because then you only must compare each read Point against two other Points, and only if it farther or closer you must compare against the other ten.


public static void main(String[] args) throws IOException { 

Your main should not throw Exceptions, it should handle them and fail gracefully.


String pathToFile; for (String arg : args) {      pathToFile = arg; 

Declare variables where they are used, in this case inside the loop, to limit its scope.

for (String arg : args) {      String pathToFile = arg; 

try (DataInputStream stream = new DataInputStream(new BufferedInputStream(new FileInputStream(new File(pathToFile))))) { 

You're not performing any sort of checks here. What if the arg is empty? What if it is not a valid path? What if the file does not exist?

for (String arg : args) {     if (arg != null && arg.length > 0) {         File file = new File(arg);         if (file.exists()) {             // Continue here with the logic.         }     } } 

private static void calculateFirstPoints(Point[] pointArray, boolean furthest, int size) {     Comparator<Point> pointComparator = furthest? furthestComparator : closestComparator;     LimitedPriorityQueueWrapper<Point> pointWrapper = new LimitedPriorityQueueWrapper<>(size, pointComparator);     pointWrapper.bulkInsertToQueue(pointArray);     List<Point> resultList = pointWrapper.getElements();     printPoints(resultList); } 

I have no idea what you're doing here...

Why not pass the "correct" comparator as parameter? Would get rid of the boolean and would be more expressive.


int index = 0; while (true) {     try {         Point currentPoint = new Point(stream.readShort(), stream.readShort());         points[index] = currentPoint;         index++;     } catch (Exception e) {         break;     } } 

Every time you write while(true) I want you, from now on, to lift your hands from the keyboard, place them on the back of your head and think at least for a minute about why you just did that and if there might be another way to do this. Note how your code never checks if there are too many shorts available for the array to hold.

try {     for (int index = 0; index < points.length; index++) {         points[index] = new Point(             stream.readShort(),             stream.readShort());     } } catch (IOException e) {     // Ignore the exception, we will assume that the stream     // ended and therefor we will stop reading. } 

Alternatively with a List:

try {     while(true) {         points.add(new Point(             stream.readShort(),             stream.readShort());     } } catch (IOException e) {     // Ignore the exception, we will assume that the stream     // ended and therefor we will stop reading. } 

Ideally, your code would look something like this (pseudo-code):

class PointFinder     List<Point> farthestPoints     List<Point> closestPoints     Point farthestPoint     Point closestPoint      PointFinder(farReferencePoint, nearReferencePoint)      void findPoints(InputStream)         Point point = getPointFromStream()         if (point < closestPoint)             if (compareWithClosestPoints(point)                 closesPoints.removeFarthest()                 closestPoints.add(point)         if (point > farthestPoint)             if (compareWithFarthestPoints(point)                 farthestPoints.removeClosest()                 farthestPoints.add(point)  class Main     void main(Args)         PointFinder pointFinder = new PointFinder(farReferencePoint, nearReferencePoint)          foreach arg             perform checks                 pointFinder.findPoints(InputStream from arg)                 print pointFinder.furthestPoints                 print pointFinder.closestPoints                 pointFinder.reset() 

Or something like this. You encapsulate all the logic required for reading, comparing and gathering points into an instance class which can be reused.

 
 
 
 
3
 
vote

Prueba de la unidad!

Hay algunos problemas con nuestro código que se puede encontrar con algunas pruebas de unidad. private static final int POINTS_IN_FILE = 10000000; ... Point[] pointArray = new Point[POINTS_IN_FILE]; 9 es una gran matriz utilizada para almacenar los puntos. El tamaño se fija, por lo que habrá algunos puntos y algunos nulos la mayoría de los tiempos (a menos que el archivo tenga igual o más puntos que el tamaño constante. Por cierto, si el archivo tiene más valores que su constante, algunos valores están siendo en silencio ignorado), revisando el código, tendrá problemas para procesar la matriz:

  List0  
 

Unit testing!

There are some problems with our code that can be found with some unit testing. pointArray is a huge array used to store the points. The size is fixed, so there will be some Points ans some nulls most of the time (Unless the file has equal or more points that the size constant. By the way, if the file has more values than your constant, some values are being silently ignored), reviewing the code, you are going to have problems processing the array:

private static void calculateFirstPoints(Point[] pointArray, boolean furthest, int size) {     Comparator<Point> pointComparator = furthest? furthestComparator : closestComparator;     LimitedPriorityQueueWrapper<Point> pointWrapper = new LimitedPriorityQueueWrapper<>(size, pointComparator);     pointWrapper.bulkInsertToQueue(pointArray); // <-- Inserting all elements, nulls included.      List<Point> resultList = pointWrapper.getElements();     printPoints(resultList); }  public void bulkInsertToQueue(T[] array) {     for (int i=0; i<array.length; i++) {         insertIntoQueue(array[i]); <-- Insert each element in the Priority Queue (nulls included)     }  public void insertIntoQueue(T t) {     queue.add(t); <-- Adding elements, PriorityQueue doesn't admit nulls and throws a NullPointerException     if (sizeReached) {         queue.poll();         return;     }     if (queue.size() >= size) {         sizeReached = true;     } } 
 
 

Relacionados problema

10  Cálculo de ángulos y distancias  ( Calculating angles and distances ) 
Estoy ejecutando una simulación con 250 agentes interactivos y tengo algunas funciones que se llaman una y otra vez. Incluso con precomputación de todas las d...

2  Fórmula Haversine en SQL  ( Haversine formula in sql ) 
Esta es una implementación de la haversine fórmula en Microsoft Transact SQL. ¿Cómo puedo simplificar la función? en1 Aquí hay una prueba de la func...

1  Encuentra triángulos de la línea  ( Find triangles from line ) 
Tengo algunas líneas que forman triángulos. Me gustaría desafiar la forma más rápida de encontrar todos los triángulos. En particular, el código debe tom...

4  Ray → Plano y Ray → Intersección Quad  ( Ray%e2%86%92plane and ray%e2%86%92quad intersection ) 
Esto verifica la intersección entre un 123451 y un 123452 y entre un 99887776655443313 y un 99887766555443114 (en 3d): 123455 Por favor, analice...

1  Computación de vectores de la base del espacio tangente para una malla arbitraria  ( Computing tangent space basis vectors for an arbitrary mesh ) 
Esto es más como una parte y una solicitud que una pregunta. Convidí el código de Eric Lengyel, que calcula las tangentes de una malla con el fin de la textur...

5  Encuentra el centro de n cuadrados que juntos construyen un rectángulo  ( Find the center of n squares which together build a rectangle ) 
Tengo un rectángulo con tamaño greplace() { if [ "${#}" != 3 ]; then echo "Usage: greplace file_pattern search_pattern replacement" return 1 else...

7  Algoritmo Ramer-Douglas-Peucker  ( Ramer douglas peucker algorithm ) 
Ramer-Douglas-Peucker es un gran algoritmo para reducir la cantidad de muestras en un rastro determinado, y también para mantener su forma general (tanto como...

8  Graham Scan convex Hull Algorithm  ( Graham scan convex hull algorithm ) 
Estoy empezando a aprender Haskell. He implementado el Graham Scan algoritmo para detectar el casco convexo después del libro real de Haskell. Estoy busca...

17  Algoritmo shamos-Hoey para verificar la auto-intersección de una forma cerrada  ( Shamos hoey algorithm for checking the self intersection of a closed shape ) 
Implementé el algoritmo Shamos-Hoey para verificar si una forma cerrada es autoinformada. ¿Este algoritmo está bien en términos de rendimiento? Array#inclu...

6  Encuentra el área superpuesta de octágonos  ( Find overlapping area of octagons ) 
Aquí está mi declaración de problema: Hay una matriz de octágonos, por ejemplo, 4 octágonos en una fila y 3 de estas filas. Así que 4 columnas y 3 filas de ...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos