- Notifications
You must be signed in to change notification settings - Fork1.9k
Open
Description
In the function Matrix.add (see code below), the innermost for-loop is unneeded (notice that the iteratori is not used at all). Removing this for-loop can reduce the time complexity from cubic to quadratic, in relation to the width of the matrix. I have tried removing it, and all tests still pass.
The exact same problem is apparent in Matrix.subtract.
These functions can be found in the filesrc\com\jwetherell\algorithms\data_structures\Matrix.java
publicMatrix<T>add(Matrix<T>input) {Matrix<T>output =newMatrix<T>(this.rows,this.cols);if ((this.cols !=input.cols) || (this.rows !=input.rows))returnoutput;for (intr =0;r <output.rows;r++) {for (intc =0;c <output.cols;c++) {for (inti =0;i <cols;i++) {Tm1 =this.get(r,c);Tm2 =input.get(r,c);Tresult;/* TODO: This is ugly and how to handle number overflow? */if (m1instanceofBigDecimal ||m2instanceofBigDecimal) {BigDecimalresult2 = ((BigDecimal)m1).add((BigDecimal)m2);result = (T)result2; }elseif (m1instanceofBigInteger ||m2instanceofBigInteger) {BigIntegerresult2 = ((BigInteger)m1).add((BigInteger)m2);result = (T)result2; }elseif (m1instanceofLong ||m2instanceofLong) {Longresult2 = (m1.longValue() +m2.longValue());result = (T)result2; }elseif (m1instanceofDouble ||m2instanceofDouble) {Doubleresult2 = (m1.doubleValue() +m2.doubleValue());result = (T)result2; }elseif (m1instanceofFloat ||m2instanceofFloat) {Floatresult2 = (m1.floatValue() +m2.floatValue());result = (T)result2; }else {// IntegerIntegerresult2 = (m1.intValue() +m2.intValue());result = (T)result2; }output.set(r,c,result); } } }returnoutput;}
Metadata
Metadata
Assignees
Labels
No labels