svn commit: r1367227 - /commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/linear/SimplexTableau.java

[tn...@apache.org]

Author: tn
Date: Mon Jul 30 19:07:05 2012
New Revision: 1367227

URL: http://svn.apache.org/viewvc?rev=1367227&view=rev
Log:
Use a TreeSet instead of an ArrayList when dropping columns after phase 1 of the simplex solver to improve performance.

Modified:
    commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/linear/SimplexTableau.java

Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/linear/SimplexTableau.java
URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/linear/SimplexTableau.java?rev=1367227&r1=1367226&r2=1367227&view=diff
==============================================================================
--- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/linear/SimplexTableau.java (original)
+++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/optimization/linear/SimplexTableau.java Mon Jul 30 19:07:05 2012
@@ -26,6 +26,7 @@ import java.util.Collection;
 import java.util.HashSet;
 import java.util.List;
 import java.util.Set;
+import java.util.TreeSet;
 
 import org.apache.commons.math3.linear.Array2DRowRealMatrix;
 import org.apache.commons.math3.linear.MatrixUtils;
@@ -333,7 +334,7 @@ class SimplexTableau implements Serializ
             return;
         }
 
-        List<Integer> columnsToDrop = new ArrayList<Integer>();
+        Set<Integer> columnsToDrop = new TreeSet<Integer>();
         columnsToDrop.add(0);
 
         // positive cost non-artificial variables
@@ -346,24 +347,26 @@ class SimplexTableau implements Serializ
 
         // non-basic artificial variables
         for (int i = 0; i < getNumArtificialVariables(); i++) {
-          int col = i + getArtificialVariableOffset();
-          if (getBasicRow(col) == null) {
-            columnsToDrop.add(col);
-          }
+            int col = i + getArtificialVariableOffset();
+            if (getBasicRow(col) == null) {
+                columnsToDrop.add(col);
+            }
         }
 
         double[][] matrix = new double[getHeight() - 1][getWidth() - columnsToDrop.size()];
         for (int i = 1; i < getHeight(); i++) {
-          int col = 0;
-          for (int j = 0; j < getWidth(); j++) {
-            if (!columnsToDrop.contains(j)) {
-              matrix[i - 1][col++] = tableau.getEntry(i, j);
+            int col = 0;
+            for (int j = 0; j < getWidth(); j++) {
+                if (!columnsToDrop.contains(j)) {
+                    matrix[i - 1][col++] = tableau.getEntry(i, j);
+                }
             }
-          }
         }
 
-        for (int i = columnsToDrop.size() - 1; i >= 0; i--) {
-          columnLabels.remove((int) columnsToDrop.get(i));
+        // remove the columns in reverse order so the indices are correct
+        Integer[] drop = columnsToDrop.toArray(new Integer[columnsToDrop.size()]);
+        for (int i = drop.length - 1; i >= 0; i--) {
+            columnLabels.remove((int) drop[i]);
         }
 
         this.tableau = new Array2DRowRealMatrix(matrix);