Comparando cada elemento de una lista a todos los demás elementos de la misma lista -- java camp codereview Relacionados El problema

Comparing each element of a list to all other elements of the same list


1
vote

problema

Español

Para obtener una lista de treeDataGroups con 5 TreeDataGroup El objeto contiene un objeto máximo 100 dataAndVar y 100 dataNotVar . La ejecución de removeFullyUnexpectedData toma 11466 ms. Me gustaría reducir eso y conozco la única forma de reducir el algoritmo adoptado y la forma en que escribo el código. El parámetro treeDataGroups contiene elementos ordenados. ¿Alguien puede sugerir cómo puedo mejorar este algoritmo? Mi objetivo es reducir este tiempo de ejecución incluso solo por unos segundos.

Lo que estoy tratando de hacer es:

Tengo lista de objetos VG (es un objeto 99887776655544337 ), digamos:

Tengo 5 elementos VG en mi lTree LISTA: VG0 , 99887766555443310 , 99887766555443311 , TreeDataGroup2 , TreeDataGroup3 Objetos. Cada objeto contiene una lista de cadenas 998877766655443314 y 99887776655443315 . El método Permite verificar si TreeDataGroup7 (el segundo parámetro de TreeDataGroup8 ) contiene 99887776655443319 , que es el primero Parámetro del treeDataGroup0 Función.

Saber que treeDataGroup1 (El primer parámetro del treeDataGroup2 puede ser nulo o vacío y treeDataGroup3 (el segundo parámetro de la < Código> treeDataGroup4 Función ) También puede ser nulo o vacío. Entonces, si treeDataGroup5 es nulo o vacío, el método 1 devuelve verdadero, de su contrato si 99887776655443326 es nulo o vacío, devolvemos falso. De lo contrario, necesito verificar si treeDataGroup7 contiene todos los elementos de treeDataGroup8 . Necesito comparar cada elemento de mi lista, con todos los demás elementos de mi lista, excepto al propio elemento actual.

y si el elemento actual si es diferente del otro elemento:

Si comienzo desde el final de mi lista:

Digamos, para treeDataGroup9 y dataAndVar0 :

  • para x igual a 4, necesito comparar dataAndVar1 y dataAndVar32 - & gt; Compruebe si dataAndVar3 contiene dataAndVar4 , luego verifique si 99887776655443335 contiene 99887776655443336 . Si ambas condiciones son verdaderas, entonces quito dataAndVar7 de la lista dataAndVar8 .
  • Si el elemento actual es dataAndVar9 , necesito verificar si el 998877766554433340 Lista de cadena contiene todo 99887776655443341 Lista de cadena (para eso necesito Para verificar si ambas listas no son nulas o vacías, ya que expliqué anteriormente). En caso afirmativo (VERDADERO), tendré que verificar si el 998877766554433422 Lista de cadenas contiene todos 99887776655443343 listas de cadenas. Para eso, debo verificar si ambas listas no son nulas o vacías, ya que expliqué anteriormente). En caso afirmativo (VERDADERO), necesito eliminar dataNotVar4 de MI dataNotVar5 Lista.
  • luego x igual a 3, necesito comparar dataNotVar6 y dataNotVar7 - & gt; & gt; Compruebe si dataNotVar8 contiene dataAndVar49 Luego verifique si 99887766555443350 contiene 99887776655443351 . Si ambas condiciones son verdaderas, entonces elimino removeFullyUnexpectedData2 de removeFullyUnexpectedData3 .

  removeFullyUnexpectedData4  
Original en ingles

For a list of treeDataGroups with 5 TreeDataGroup objects, each treeDataGroup object contains a maximum 100 dataAndVar and 100 dataNotVar. The execution of removeFullyUnexpectedData takes 11466 ms. I would like to reduce that and I know the only way to reduce that the adopted algorithm and the way that I write the code. The treeDataGroups parameter contains sorted elements. Can someone suggest how I can improve this algorithm? My goal is to reduce this execution time even just for few seconds only.

What I am trying to do is:

I have list of VG object (it is a TreeDataGroup object), let us say:

I have 5 elements VG in my lTree list: VG0, VG1, VG2, VG3, VG4 objects. Each object contains an andVar String list and a notVar String list. The firstListIsCompletelyContainedInMainList method allows to check if list2 (the second parameter of firstListIsCompletelyContainedInMainList function) contains list1, which is the first parameter of the firstListIsCompletelyContainedInMainList function.

Know that list1 (the first parameter of the firstListIsCompletelyContainedInMainList function) can be null or empty and list2 (the second parameter of the firstListIsCompletelyContainedInMainList function) as well can be null or empty. So if list1 is null or empty, method 1 returns true, else if list2is null or empty, we return false. Otherwise, I need to check if list2 contains all elements of list1. I need to compare each element of my list, with all other elements of my list except to the current element itself.

And if the current element if different from the other element:

If I start from the end of my list:

Let us say, for VG4 and VG3:

  • For x equal to 4, I need to compare VG4 and VG3 --> check if VG4.andVar contains VG3.andVar, then check if VG3.notVar contains VG4.notVar. If both conditions are true, then I remove VG4 from the treeDataGroups list.
  • If the current element is VG4, I need to check if the VG4.andVar string list contains all VG3.andVar string list (for that I need to check if both lists are not null or empty as I explained above)). If yes (true), I will need to check if the VG3.notVar string list contains all VG4.notVar string lists. For that, I need to check if both lists are not null or empty as I explained above)). If yes (true), I need to remove VG4 from my treeDataGroups list.
  • Then x equal to 3, I need to compare VG3 and VG4 --> check if VG3.andVar contains VG4.andVar then check if VG4.notVar contains VG3.notVar. If both conditions are true, then I remove VG3 from treeDataGroupslist.

Then x equal to 2 I need to compare (VG2 and VG3).....      x equal to 2 I need to compare (VG2 and VG4) Then x equal to 1 I need to compare (VG1 and VG2)      x equal to 1 I need to compare (VG1 and VG3)      x equal to 1 I need to compare (VG1 and VG4) Then x equal to 0 I need to compare (VG0 and VG1)      x equal to 0 I need to compare (VG0 and VG2)      x equal to 0 I need to compare (VG0 and VG3)      x equal to 0 I need to compare (VG0 and VG4)  public List<TreeDataGroup> removeFullyUnexpectedData(List<TreeDataGroup> treeDataGroups) {     for (int x = treeDataGroups.size()-1; x >= 0; x--) {         TreeDataGroup treeDg1 = treeDataGroups.get(x);         for (int y = treeDataGroups.size()-1; y >= 0; y--) {             if (y != x) {                 TreeDataGroup treeDg2 = treeDataGroups.get(y);                 //treeDg1.getDataAndVar and treeDg1.getDataNotVar are a list of String                 if (firstListIsCompletelyContainedInMainList(treeDg2.getDataAndVar(), treeDg1.getDataAndVar) {                     if (firstListIsCompletelyContainedInMainList(treeDg1.getDataNotVar(), treeDg2.getDataNotVar) {                         treeDataGroups.remove(x);                         break;                     }                 }             }         }      }     return treeDataGroups; }   // Are the items in the search list completely contained in the main list...  public static boolean firstListIsCompletelyContainedInMainList(List<String> list1, List<String> list2) {     if (isStringListNullOrEmpty(list1)) {         return true;     }     if (isStringListNullOrEmpty(list2)) {         return false;     }     for (String item : list1) {         if (!list2.contains(item)) {             return false;         }     }     return true; }  public static boolean isStringListNullOrEmpty(List<String> stringList) {     if ((stringList == null || stringList.isEmpty())) {         return true;     } else {         return false;     } } 
  
     
     

Lista de respuestas

3
 
vote
  • getData es no mejor que doStuff() como el nombre de una función. getDataNotVar y getDataAndVar son solo un poco mejores, y son inútiles para mí, ya que no sé qué 9988776655544339 o 99887766555443310 Eres return decodedHeader.Equals(BasicAuthenticationKey); 1 ting. : P

  • return decodedHeader.Equals(BasicAuthenticationKey); 2 está reinventando la rueda. Las colecciones tienen un método 99887766655443313 . Usa eso.

      return decodedHeader.Equals(BasicAuthenticationKey); 4  

    pero podemos hacerlo mejor.

    Está utilizando un tipo subóptimo para el tipo de operación que está haciendo aquí. Si rellena los elementos en un return decodedHeader.Equals(BasicAuthenticationKey); 5 , y compruebe con eso, su cheque va de O (NM) a O (N + M).

      return decodedHeader.Equals(BasicAuthenticationKey); 6  
  • Idealmente, estaría usando return decodedHeader.Equals(BasicAuthenticationKey); 7 en lugar de return decodedHeader.Equals(BasicAuthenticationKey); 8 de todos modos, si esta es la operación principal que está realizando en estas "Listas". Sin embargo, no puedo decir si esa es una buena idea en su caso particular, sin embargo, como no ha mostrado nada más que lo está haciendo.

  • Cuando está devolviendo los resultados de las pruebas condicionales, hágalo directamente. No digas return decodedHeader.Equals(BasicAuthenticationKey); 9 . SOLO public interface DbProc { public SqlCommand GetCommand(); } public class MyProc : DbProc { private SqlCommand _cmd; public const string COMMAND_TEXT = "spc_MyProc"; public const string PARAM1 = "@Param1"; public const string PARAM2 = "@Param2"; public MyProc(int param1, string param2) { _cmd = new SqlCommand(COMMAND_TEXT); _cmd.CommandType = CommandType.StoredProcedure; _cmd.Parameters.AddWithValue(PARAM1, param1); _cmd.Parameters.AddWithValue(PARAM2, param2); } public SqlCommand GetCommand() { return _cmd; } } public class Db { public DataTable ExecuteProc(DbProc proc) { SqlCommand cmd = proc.GetCommand(); ConfigureCommand(cmd); // execute the command into a data table return result; } // Set the common settings for all commands private void ConfigureCommand(SqlCommand cmd) { cmd.CommandTimeout = 10000; } } 0 .

      public interface DbProc {     public SqlCommand GetCommand(); }  public class MyProc : DbProc {     private SqlCommand _cmd;      public const string COMMAND_TEXT = "spc_MyProc";     public const string PARAM1 = "@Param1";     public const string PARAM2 = "@Param2";              public MyProc(int param1, string param2)     {         _cmd = new SqlCommand(COMMAND_TEXT);         _cmd.CommandType = CommandType.StoredProcedure;         _cmd.Parameters.AddWithValue(PARAM1, param1);         _cmd.Parameters.AddWithValue(PARAM2, param2);     }      public SqlCommand GetCommand()     {         return _cmd;     } }  public class Db {     public DataTable ExecuteProc(DbProc proc)     {         SqlCommand cmd = proc.GetCommand();         ConfigureCommand(cmd);         // execute the command into a data table         return result;     }      // Set the common settings for all commands     private void ConfigureCommand(SqlCommand cmd)     {         cmd.CommandTimeout = 10000;                 } } 1  
  • Idealmente, sin embargo, lo haría, así que public interface DbProc { public SqlCommand GetCommand(); } public class MyProc : DbProc { private SqlCommand _cmd; public const string COMMAND_TEXT = "spc_MyProc"; public const string PARAM1 = "@Param1"; public const string PARAM2 = "@Param2"; public MyProc(int param1, string param2) { _cmd = new SqlCommand(COMMAND_TEXT); _cmd.CommandType = CommandType.StoredProcedure; _cmd.Parameters.AddWithValue(PARAM1, param1); _cmd.Parameters.AddWithValue(PARAM2, param2); } public SqlCommand GetCommand() { return _cmd; } } public class Db { public DataTable ExecuteProc(DbProc proc) { SqlCommand cmd = proc.GetCommand(); ConfigureCommand(cmd); // execute the command into a data table return result; } // Set the common settings for all commands private void ConfigureCommand(SqlCommand cmd) { cmd.CommandTimeout = 10000; } } 22 99887766555443323 Siempre devuelva una colección vacía en lugar de public interface DbProc { public SqlCommand GetCommand(); } public class MyProc : DbProc { private SqlCommand _cmd; public const string COMMAND_TEXT = "spc_MyProc"; public const string PARAM1 = "@Param1"; public const string PARAM2 = "@Param2"; public MyProc(int param1, string param2) { _cmd = new SqlCommand(COMMAND_TEXT); _cmd.CommandType = CommandType.StoredProcedure; _cmd.Parameters.AddWithValue(PARAM1, param1); _cmd.Parameters.AddWithValue(PARAM2, param2); } public SqlCommand GetCommand() { return _cmd; } } public class Db { public DataTable ExecuteProc(DbProc proc) { SqlCommand cmd = proc.GetCommand(); ConfigureCommand(cmd); // execute the command into a data table return result; } // Set the common settings for all commands private void ConfigureCommand(SqlCommand cmd) { cmd.CommandTimeout = 10000; } } 4 . (Se siente un poco hinky cuando no sabe si tiene un objeto o no). Una vez que haga eso, esta función puede desaparecer completamente ... Como puede los cheques nulos en public interface DbProc { public SqlCommand GetCommand(); } public class MyProc : DbProc { private SqlCommand _cmd; public const string COMMAND_TEXT = "spc_MyProc"; public const string PARAM1 = "@Param1"; public const string PARAM2 = "@Param2"; public MyProc(int param1, string param2) { _cmd = new SqlCommand(COMMAND_TEXT); _cmd.CommandType = CommandType.StoredProcedure; _cmd.Parameters.AddWithValue(PARAM1, param1); _cmd.Parameters.AddWithValue(PARAM2, param2); } public SqlCommand GetCommand() { return _cmd; } } public class Db { public DataTable ExecuteProc(DbProc proc) { SqlCommand cmd = proc.GetCommand(); ConfigureCommand(cmd); // execute the command into a data table return result; } // Set the common settings for all commands private void ConfigureCommand(SqlCommand cmd) { cmd.CommandTimeout = 10000; } } 5 . (Podría mantener un 99887776655443326655443326 Verifique si está intentando optimizar, pero cualquier ahorre que no valga la pena el código extra. Si le importa, míralo.)

  • Por cierto, tus nombres son extremadamente lados. Tal vez eso es solo una cosa de Java. : P pero public interface DbProc { public SqlCommand GetCommand(); } public class MyProc : DbProc { private SqlCommand _cmd; public const string COMMAND_TEXT = "spc_MyProc"; public const string PARAM1 = "@Param1"; public const string PARAM2 = "@Param2"; public MyProc(int param1, string param2) { _cmd = new SqlCommand(COMMAND_TEXT); _cmd.CommandType = CommandType.StoredProcedure; _cmd.Parameters.AddWithValue(PARAM1, param1); _cmd.Parameters.AddWithValue(PARAM2, param2); } public SqlCommand GetCommand() { return _cmd; } } public class Db { public DataTable ExecuteProc(DbProc proc) { SqlCommand cmd = proc.GetCommand(); ConfigureCommand(cmd); // execute the command into a data table return result; } // Set the common settings for all commands private void ConfigureCommand(SqlCommand cmd) { cmd.CommandTimeout = 10000; } } 7 podría ser reemplazado por, digamos, public interface DbProc { public SqlCommand GetCommand(); } public class MyProc : DbProc { private SqlCommand _cmd; public const string COMMAND_TEXT = "spc_MyProc"; public const string PARAM1 = "@Param1"; public const string PARAM2 = "@Param2"; public MyProc(int param1, string param2) { _cmd = new SqlCommand(COMMAND_TEXT); _cmd.CommandType = CommandType.StoredProcedure; _cmd.Parameters.AddWithValue(PARAM1, param1); _cmd.Parameters.AddWithValue(PARAM2, param2); } public SqlCommand GetCommand() { return _cmd; } } public class Db { public DataTable ExecuteProc(DbProc proc) { SqlCommand cmd = proc.GetCommand(); ConfigureCommand(cmd); // execute the command into a data table return result; } // Set the common settings for all commands private void ConfigureCommand(SqlCommand cmd) { cmd.CommandTimeout = 10000; } } 8 Si cambia public interface DbProc { public SqlCommand GetCommand(); } public class MyProc : DbProc { private SqlCommand _cmd; public const string COMMAND_TEXT = "spc_MyProc"; public const string PARAM1 = "@Param1"; public const string PARAM2 = "@Param2"; public MyProc(int param1, string param2) { _cmd = new SqlCommand(COMMAND_TEXT); _cmd.CommandType = CommandType.StoredProcedure; _cmd.Parameters.AddWithValue(PARAM1, param1); _cmd.Parameters.AddWithValue(PARAM2, param2); } public SqlCommand GetCommand() { return _cmd; } } public class Db { public DataTable ExecuteProc(DbProc proc) { SqlCommand cmd = proc.GetCommand(); ConfigureCommand(cmd); // execute the command into a data table return result; } // Set the common settings for all commands private void ConfigureCommand(SqlCommand cmd) { cmd.CommandTimeout = 10000; } } 9 y 99887766555443330 alrededor.

 
  • getData is no better than doStuff() as the name of a function. getDataNotVar and getDataAndVar are only slightly better, and are useless to me, as i don't know what Data or Var you're getting. :P

  • firstListIsCompletelyContainedInMainList is reinventing the wheel. Collections have a containsAll method. Use that.

    public static boolean firstListIsCompletelyContainedInMainList(List<String> list1, List<String> list2) {     if (isStringListNullOrEmpty(list1)) return true;     if (isStringListNullOrEmpty(list1)) return false;     return list2.containsAll(list1); } 

    But we can do better.

    You're using a suboptimal type for the type of operation you're doing here. If you stuff the items into a HashSet<String>, and check against that, your check goes from O(NM) to O(N+M).

    public static boolean firstListIsCompletelyContainedInMainList(List<String> list1, List<String> list2) {     if (isStringListNullOrEmpty(list1)) return true;     if (isStringListNullOrEmpty(list1)) return false;      Set<String> mainContents = new HashSet<>(list2);     return mainContents.containsAll(list1); } 
  • Ideally, you'd be using Set<String> rather than List<String> anyway, if this is the main operation you're performing on these "lists". I can't say whether that's a good idea in your particular case, though, as you haven't shown anything else you're doing.

  • When you're returning the results of conditional tests, do it directly. Don't say if (x) return true; else return false;. Just return x;.

    public static boolean isStringListNullOrEmpty(List<String> stringList) {     return (stringList == null || stringList.isEmpty()); } 
  • Ideally, though, you'd make it so getDataAndVar() and getDataNotVar() always return an empty collection rather than null. (It feels a bit hinky when you don't know whether you have an object or not.) Once you do that, this function can go away entirely...as can the null checks in firstListIsCompletelyContainedInMainList. (You might keep an .isEmpty() check if you're trying to optimize, but any savings might not be worth the extra code. If you care, measure it.)

  • By the way, your names are extremely wordy. Maybe that's just a Java thing. :P But firstListIsCompletelyContainedInMainList could be replaced by, say, listContainsList if you swap list1 and list2 around.

 
 
         
         
0
 
vote

En primer lugar, permítanme señalar que eliminar elementos de una lista que está iterando es bastante peligrosa en general.

El bucle externo en sí no es un problema, ya que está pasando por los índices que comienzan al final e ir al inicio. Eliminar el elemento en el índice actual no tiene ningún efecto en los índices que se manejarán en las siguientes iteraciones.

Sin embargo, cuando anidamos 2 para los bucles iterando sobre todos los elementos que nos convertimíamos en problemas.

Digamos que tiene la lista {A, B, C, D}. Ignoramos comparando D a D. A continuación, comparamos D a C y concluyamos que C se puede eliminar. A continuación, comparamos D a B y la conclusión de B puede ser eliminada. Finalmente comparar D a A y no hacer nada. Ahora, la siguiente X será 2. Pero desde que eliminamos B y C de nuestra lista, la función list.get(2) lanzará una excepción indexOutofboundsexception.

Parece que intentó resolver este problema utilizando una declaración 99887766655443311 para saltar fuera del bucle interno 9988777665544332 Siempre que quite un elemento. Pero esto ha introducido un nuevo error.

Digamos en la misma lista que está comparando C a D y concluya que D se puede eliminar. Ahora sale del bucle interno y continúe con B. Pero al hacerlo se saltó comparando C a B y comparando C a a.


Entonces, ¿qué podemos hacer para resolver esto correctamente? En lugar de eliminar directamente los VG de la lista, deberíamos marcar los VG's para eliminar en la primera pasada.

Luego, una vez finalizado el exterior para el bucle, pasamos a todos los VG marcados nuevamente y elimíntelos de forma segura de la lista.

También podemos simplificar un poco los bucles si compruebamos que contiene ambas maneras a la vez. El código se verá así:

  List<TreeDataGroup> markedForRemoval = new ArrayList<>(); for (int x = treeDataGroups.size()-1; x >= 0; x--) {     TreeDataGroup treeDg1 = treeDataGroups.get(x);     //**important** notice the y>x instead of y>=0     for (int y = treeDataGroups.size()-1; y > x; y--) {         TreeDataGroup treeDg2 = treeDataGroups.get(y);         if (treeDg1 fully contains treeDg2) {             markedForRemoval.add(treeDg2);         }         if (treeDg2 fully contains treeDg1) {             markedForRemoval.add(treeDg1);         }      } }  for(TreeDataGroup group : markedForRemoval){     treeDataGroups.remove(group); }   

Si entendí su explicación inicial correctamente, las listas dentro de los DataGrups están ordenados. Así que creo que podemos hacer ambos cheques al mismo tiempo con algo como esto: (Descargo de responsabilidad: no probé este código, es posible que tenga que corregirlo para que funcione). Tenga en cuenta que también estoy asumiendo que las listas no son nulas, pero el valor predeterminado en una lista vacía como @chao sugirió en su respuesta.

  private void markGroupForRemoval(TreeDataGroup group1, TreeDataGroup group2, List<TreeDataGroup> markedGroups){     boolean markg1 = true;     boolean markg2 = true;      int i1 = 0;     int i2 = 0;     while(i1 < group1.getDataAndVar().length                  && i2 < group2.getDataAndVar().length                  && (markg1 || markg2)){         if(group1.getDataAndVar().get(i1) == group2.getDataAndVar().get(i2)){             i1++;             i2++;         } else if(group1.getDataAndVar().get(i1) < group2.getDataAndVar().get(i2)){ //note, you should change this to a string comparison I believe             //group 1 contains an element that group2 does not.             markg1 = false;             i1 ++;         } else {             //group 2 contains an element that group1 does not.             markg2 = false;             i2 ++;         }     }      //do the same thing for getDataNotVar, but mark the oposite.     i1 = 0;     i2 = 0;     while(i1 < group1.getDataNotVar().length                  && i2 < group2.getDataNotVar getDataNotVar().length                  && (markg1 || markg2)){         if(group1.getDataNotVar().get(i1) == group2.getDataNotVar().get(i2)){             i1++;             i2++;         } else if(group1.getDataNotVar().get(i1) < group2.getDataNotVar().get(i2)){ //note, you should change this to a string comparison I believe             //group 1 contains a not-element that group2 does not.             markg2 = false;             i1 ++;         } else {             //group 1 contains a not-element that group2 does not.             markg1 = false;             i2 ++;         }     }      if(markg1){         markedGroups.add(group1);     }     if(markg2){         markedGroups.add(group2);     } }   

Aviso aquí que tan pronto como estuvimos marcados con ambos grupos tan necesarios (por lo que tanto Markg1 como Markg2 son falsos), renunciamos a la bucle while temprano.

Si puede hacer que esto funcione, debe acelerar las cosas un poco (o mucho, si la salida temprana mientras la verificación ocurre de manera rápida). Deberá al menos reemplazar el < con la verificación de comparación correcta. (StringcomParitor?). Tal vez el grupo2.getdataandvar (). La longitud debe ser group2.getdataandvar (). Tamaño () en su lugar. Y revise la lógica porque podría haber cambiado los casos por accidente.

Si está familiarizado con la sanción de fusión, este algoritmo debe ser relativamente fácil de entender.


Editar: según sugerencia por @chao, ahora estamos comparando VG's incluso si ya están marcados para su eliminación. Dado que los controles en sí son bastante caros, es mejor evitar eso.

Mi primera solución para esto sería algo así:

  List<TreeDataGroup> markedForRemoval = new ArrayList<>(); for (int x = treeDataGroups.size()-1; x >= 0; x--) {     TreeDataGroup treeDg1 = treeDataGroups.get(x);     for (int y = treeDataGroups.size()-1; y > x; y--) {         TreeDataGroup treeDg2 = treeDataGroups.get(y);         if(marmarkedForRemoval.contains(treeDG2) {             continue;         }         markGroupForRemoval(treeDG1, treeDG2, markedForRemoval);         if(markedForRemoval.contains(treeDG1){             break;         }     } }   

Donde el cheque para TreeDG2 hace que salte a saltarse solo en el bucle interno (si salíamos del bucle, obtenemos las mismas verificaciones que faltan antes). Y la verificación de TreeDG1 justo después de que la marca significa que, dado que el VG del bucle externo está marcado, no hay razón para continuar revisando ese contra el resto del bucle interno.

Pero podemos hacerlo un poco mejor que esto. ¿Recuerdas que dije que la eliminación en un solo para el bucle es seguro? Usemos ese hecho y coloque la eliminación dentro del exterior para el bucle:

  List<TreeDataGroup> markedForRemoval = new ArrayList<>(); for (int x = treeDataGroups.size()-1; x >= 0; x--) {     TreeDataGroup treeDg1 = treeDataGroups.get(x);     for (int y = treeDataGroups.size()-1; y > x; y--) {         TreeDataGroup treeDg2 = treeDataGroups.get(y);         markGroupForRemoval(treeDG1, treeDG2, markedForRemoval);         if(markedForRemoval.contains(treeDG1){             break;         }     }     for(TreeDataGroup tdg : markedForRemoval){         treeDataGroups.remove(tdg);     }     markedForRemoval.clear(); }   

Ahora estamos seguros de que revisemos todas las combinaciones, pero sin hacer ningún control innecesario.

Sin embargo, hice un error gracias al comentario de @ Chao. Si los 2 VG son exactamente los mismos, ambos se marcarán para la eliminación. Esto no es lo que queremos. Entonces, vamos a solucionar esto al final del método 9988776665544338

      if(markg1){         markedGroups.add(group1);         return; //important. If both are equal, we shouldn't remove them both.     }     if(markg2){         markedGroups.add(group2);     } }   
 

First of all, let me point out that removing elements from a list that you're iterating over is pretty dangerous in general.

The outer loop itself isn't a problem, since you're going over the indices starting at the end and going to the start. Removing the item at the current index doesn't have any effect on the indices that will be handled in the next iterations.

However, when we nest 2 for loops iterating over all the elements we would run into problems.

Let's say you have the list {A,B,C,D}. We ignore comparing D to D. Next we compare D to C and conclude that C can be removed. Next we compare D to B and conclude B can be removed. Finally compare D to A and do nothing. Now the next x will be 2. But since we removed B and C from our list the function list.get(2) will throw an IndexOutOfBoundsException.

It seems you tried to solve this problem by using a break statement to jump out of the inner for loop whenever you remove an item. But this has introduced a new mistake.

Let's say in the same list you are comparing C to D and conclude that D can be removed. You now break out of the inner loop and continue with B. But by doing so you skipped comparing C to B and comparing C to A.


So then what can we do to solve this correctly? Instead of directly removing the VG's from the list we should just mark the VG's for removal in the first pass.

Then after the outer for loop has ended, we loop over all the marked VG's again and safely remove them from the list.

We can also simplify the loops a little bit if we check the contains both ways at once. The code will look like this:

List<TreeDataGroup> markedForRemoval = new ArrayList<>(); for (int x = treeDataGroups.size()-1; x >= 0; x--) {     TreeDataGroup treeDg1 = treeDataGroups.get(x);     //**important** notice the y>x instead of y>=0     for (int y = treeDataGroups.size()-1; y > x; y--) {         TreeDataGroup treeDg2 = treeDataGroups.get(y);         if (treeDg1 fully contains treeDg2) {             markedForRemoval.add(treeDg2);         }         if (treeDg2 fully contains treeDg1) {             markedForRemoval.add(treeDg1);         }      } }  for(TreeDataGroup group : markedForRemoval){     treeDataGroups.remove(group); } 

If I understood your initial explanation correctly the lists inside the datagroups are sorted. So I think we can do both checks at the same time with something like this: (disclaimer: I did not test this code, you might have to correct it to get it to work). Note that I'm also assuming the lists are non-null but default to an empty list like @cHao suggested in his answer.

private void markGroupForRemoval(TreeDataGroup group1, TreeDataGroup group2, List<TreeDataGroup> markedGroups){     boolean markg1 = true;     boolean markg2 = true;      int i1 = 0;     int i2 = 0;     while(i1 < group1.getDataAndVar().length                  && i2 < group2.getDataAndVar().length                  && (markg1 || markg2)){         if(group1.getDataAndVar().get(i1) == group2.getDataAndVar().get(i2)){             i1++;             i2++;         } else if(group1.getDataAndVar().get(i1) < group2.getDataAndVar().get(i2)){ //note, you should change this to a string comparison I believe             //group 1 contains an element that group2 does not.             markg1 = false;             i1 ++;         } else {             //group 2 contains an element that group1 does not.             markg2 = false;             i2 ++;         }     }      //do the same thing for getDataNotVar, but mark the oposite.     i1 = 0;     i2 = 0;     while(i1 < group1.getDataNotVar().length                  && i2 < group2.getDataNotVar getDataNotVar().length                  && (markg1 || markg2)){         if(group1.getDataNotVar().get(i1) == group2.getDataNotVar().get(i2)){             i1++;             i2++;         } else if(group1.getDataNotVar().get(i1) < group2.getDataNotVar().get(i2)){ //note, you should change this to a string comparison I believe             //group 1 contains a not-element that group2 does not.             markg2 = false;             i1 ++;         } else {             //group 1 contains a not-element that group2 does not.             markg1 = false;             i2 ++;         }     }      if(markg1){         markedGroups.add(group1);     }     if(markg2){         markedGroups.add(group2);     } } 

Notice here that as soon as we marked both groups as still needed (so both markg1 and markg2 are false) then we quit the while loop early.

If you can get this to work it should speed things up a bit (or a lot, if the early exit while checking happens fast consistently). You'll need to at least replace the < with the correct comparison check. (StringComparitor?). Maybe group2.getDataAndVar().length should be group2.getDataAndVar().size() instead. And check the logic because I might have switched the cases around by accident.

If you're familiar with merge sort this algorithm should be relatively easy to understand.


EDIT: as per suggestion by @cHao, we're now comparing VG's even if they're already marked for removal. Since the checks themselves are rather expensive it's better to avoid that.

My first solution for this would be something like this:

List<TreeDataGroup> markedForRemoval = new ArrayList<>(); for (int x = treeDataGroups.size()-1; x >= 0; x--) {     TreeDataGroup treeDg1 = treeDataGroups.get(x);     for (int y = treeDataGroups.size()-1; y > x; y--) {         TreeDataGroup treeDg2 = treeDataGroups.get(y);         if(marmarkedForRemoval.contains(treeDG2) {             continue;         }         markGroupForRemoval(treeDG1, treeDG2, markedForRemoval);         if(markedForRemoval.contains(treeDG1){             break;         }     } } 

Where the check for treeDG2 results in skipping that one in the inner loop only (if we would break out of the loop we get the same missing checks like before). And the check for treeDG1 right after the marking means that since the VG of the outer loop is marked, there's no reason to continue checking that one against the rest of the inner loop.

But we can actually do a little better than this. Remember that I said that removing in a single for loop is safe? Let's use that fact and place the removal inside the outer for loop:

List<TreeDataGroup> markedForRemoval = new ArrayList<>(); for (int x = treeDataGroups.size()-1; x >= 0; x--) {     TreeDataGroup treeDg1 = treeDataGroups.get(x);     for (int y = treeDataGroups.size()-1; y > x; y--) {         TreeDataGroup treeDg2 = treeDataGroups.get(y);         markGroupForRemoval(treeDG1, treeDG2, markedForRemoval);         if(markedForRemoval.contains(treeDG1){             break;         }     }     for(TreeDataGroup tdg : markedForRemoval){         treeDataGroups.remove(tdg);     }     markedForRemoval.clear(); } 

Now we're sure that we check all combinations but without doing any unnecessary checks.

I did however spot a mistake thanks to @cHao's comment. If the 2 VG's are exactly the same, both will be marked for removal. This is not what we want. So let's fix this at the end of the markGroupForRemoval method

    if(markg1){         markedGroups.add(group1);         return; //important. If both are equal, we shouldn't remove them both.     }     if(markg2){         markedGroups.add(group2);     } } 
 
 
         
         

Relacionados problema

2  Solucionador de rompecabezas de rascacielos en Java [cerrado]  ( Skyscraper puzzle solver in java ) 
cerrado. Esta pregunta es off-topic . Actualmente no está aceptando respuestas. ¿Quieres ...

6  Encontrar el siguiente palíndromo de una cadena de números  ( Finding the next palindrome of a number string ) 
Aquí está el problema: Un entero positivo se llama palíndromo si su representación en el El sistema decimal es el mismo cuando se lee de izquierda a dere...

34  Clon a todo color del juego de la vida de Conway, con una GUI decente  ( Full color clone of conways game of life with a decent gui ) 
Escribí esto para aprender Javafx, y como excusa para volver a hacer el juego de la vida. Esta es la gui más compleja que he escrito, así que me gustaría come...

2  Eliminación de un nodo en un árbol de búsqueda binario  ( Deletion of a node in a binary search tree ) 
Estoy buscando ver si mi implementación del método de eliminación / eliminación en un árbol de búsqueda binario es suficiente, legible y se ejecuta en un tiem...

8  Simple GCD Utility en Java  ( Simple gcd utility in java ) 
i anteriormente discutido El rendimiento se refiere a diferentes algoritmos GCD. Escribí una simple clase de Java que implementa el algoritmo binario GCD. E...

5  Encuentre el próximo número Prime - Control de flujo de los bucles anidados 'para `  ( Find the next prime number flow control of nested for loops ) 
Este código funciona perfectamente, pero me molesta. Tener un bucle etiquetado y anidado Bucle, con un Enumerable<T>.Empty()0 Declaración, y un 9988777665...

1  Compruebe si dos cadenas son permutación entre sí  ( Check if two strings are permutation of each other ) 
private String sort(String word) { char[] content = word.toCharArray(); Arrays.sort(content); return new String(content); } private boolea...

2  Fusionar la implementación de Sort Java  ( Merge sort java implementation ) 
¿Puede alguien revisar mi implementación de tipo de fusión en Java? ¿Es bueno / malo y puede mejorarse más? public class MyMergeSort { private int [] d...

17  Implementación vectorial (física)  ( Vector physics implementation ) 
Recientemente comencé a aprender Java, y decidí implementar un sistema de vectores básico para otro sistema de partículas que estaba construyendo. join()9 ...

5  Memoria / Performance of Merge Sort Code  ( Memory performance of merge sort code ) 
Escribí un código de tipo de combinación para un poco de bocadillo nocturno. Lo he puesto trabajando, pero solo estaba mirando a aprender si me faltaba algo e...




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