This is an automated email from the ASF dual-hosted git repository.
baunsgaard pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/systemds.git
The following commit(s) were added to refs/heads/main by this push:
new f19713820c [SYSTEMDS-3456] MatrixBlock Equals
f19713820c is described below
commit f19713820c46606fd4d77869cb2a0577c9ae5326
Author: baunsgaard <[email protected]>
AuthorDate: Wed Oct 26 14:09:43 2022 +0200
[SYSTEMDS-3456] MatrixBlock Equals
This commit contains a basic library for comparing equality of matrices.
I have designed it to support an very small epsilon per default, but if
wanted this epsilon can be increased.
There is a specialization contained for Dense Matrices, but specialization
for sparse matrices is missing, and instead fall back to a generic
quickGetValue implementation.
The implementation supports comparing Compressed - Sparse - Dense matrices,
but is only efficiently implemented for Dense.
Closes #1712
---
.../org/apache/sysds/runtime/data/DenseBlock.java | 42 +++
.../sysds/runtime/matrix/data/LibMatrixEquals.java | 205 +++++++++++++++
.../sysds/runtime/matrix/data/MatrixBlock.java | 28 +-
.../sysds/test/component/matrix/EqualsTest.java | 291 +++++++++++++++++++++
4 files changed, 564 insertions(+), 2 deletions(-)
diff --git a/src/main/java/org/apache/sysds/runtime/data/DenseBlock.java
b/src/main/java/org/apache/sysds/runtime/data/DenseBlock.java
index 0b7158cf81..bd0a888b2f 100644
--- a/src/main/java/org/apache/sysds/runtime/data/DenseBlock.java
+++ b/src/main/java/org/apache/sysds/runtime/data/DenseBlock.java
@@ -663,6 +663,48 @@ public abstract class DenseBlock implements Serializable
return false;
}
+ @Override
+ public boolean equals(Object o) {
+ if(o instanceof DenseBlock)
+ return equals((DenseBlock) o, Double.MIN_NORMAL * 1024);
+ return false;
+ }
+
+ /**
+ * Verify if the values in this dense block is equivalent to that dense
block, not taking into account the dimensions
+ * of the contained values. Note in some cases one or the other block
is allocated bigger than the other, so the
+ * values compared is only the values of the smaller block.
+ *
+ * @param o Other block
+ * @param eps Epsilon allowed
+ * @return If the blocs are equivalent.
+ */
+ public boolean equals(DenseBlock o, double eps) {
+ if(isContiguous() && o.isContiguous())
+ return contiguousEquals(o, eps);
+ return genericEquals(o, eps);
+ }
+
+ private boolean contiguousEquals(DenseBlock o, double eps) {
+ final double[] va = values(0);
+ final double[] vb = o.values(0);
+ final int len = Math.min(va.length, vb.length);
+ for(int i = 0; i < len; i++)
+ if(Math.abs(va[i] - vb[i]) > eps)
+ return false;
+ return true;
+ }
+
+ private boolean genericEquals(DenseBlock o, double eps) {
+ final int nRows = getDim(0);
+ final int nCols = getDim(1);
+ for(int i = 0; i < nRows; i++)
+ for(int j = 0; j < nCols; j++)
+ if(Math.abs(get(i, j) - o.get(i, j)) > eps)
+ return false;
+ return true;
+ }
+
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
diff --git
a/src/main/java/org/apache/sysds/runtime/matrix/data/LibMatrixEquals.java
b/src/main/java/org/apache/sysds/runtime/matrix/data/LibMatrixEquals.java
new file mode 100644
index 0000000000..1862ff8a4e
--- /dev/null
+++ b/src/main/java/org/apache/sysds/runtime/matrix/data/LibMatrixEquals.java
@@ -0,0 +1,205 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.runtime.matrix.data;
+
+import org.apache.commons.logging.Log;
+import org.apache.commons.logging.LogFactory;
+
+/**
+ *
+ * <p>
+ * Equals library for MatrixBLocks:
+ * </p>
+ *
+ * <p>
+ * The implementations adhere to the properties of equals of:
+ * </p>
+ *
+ * <ul>
+ * <li>Reflective</li>
+ * <li>Symmetric</li>
+ * <li>Transitive</li>
+ * <li>Consistent</li>
+ * </ul>
+ *
+ */
+public class LibMatrixEquals {
+
+ /** Logger for Equals library */
+ private static final Log LOG =
LogFactory.getLog(LibMatrixEquals.class.getName());
+
+ /** first block */
+ private final MatrixBlock a;
+ /** second block */
+ private final MatrixBlock b;
+ /** Epsilon */
+ private final double eps;
+
+ /**
+ * Private instance of a comparison, constructed to reduce the
arguments to method calls.
+ *
+ * @param a first block
+ * @param b second block
+ */
+ private LibMatrixEquals(MatrixBlock a, MatrixBlock b) {
+ this.a = a;
+ this.b = b;
+ this.eps = Double.MIN_VALUE * 1024;
+ }
+
+ /**
+ * Private instance of a comparison, constructed to reduce the
arguments to method calls.
+ *
+ * @param a first block
+ * @param b second block
+ * @param eps epsilon allowed
+ */
+ private LibMatrixEquals(MatrixBlock a, MatrixBlock b, double eps) {
+ this.a = a;
+ this.b = b;
+ this.eps = eps;
+ }
+
+ /**
+ * <p>
+ * Analyze if the two matrix blocks are equivalent, this functions even
if the underlying allocation and data
+ * structure varies.
+ * </p>
+ *
+ * <p>
+ * The implementations adhere to the properties of equals of:
+ * </p>
+ *
+ * <ul>
+ * <li>Reflective</li>
+ * <li>Symmetric</li>
+ * <li>Transitive</li>
+ * <li>Consistent</li>
+ * </ul>
+ *
+ * @param a Matrix Block a to compare
+ * @param b Matrix Block b to compare
+ * @return If the block are equivalent.
+ */
+ public static boolean equals(MatrixBlock a, MatrixBlock b) {
+ // Same object
+ if(a == b)
+ return true;
+ return new LibMatrixEquals(a, b).exec();
+ }
+
+ /**
+ * <p>
+ * Analyze if the two matrix blocks are equivalent, this functions even
if the underlying allocation and data
+ * structure varies.
+ * </p>
+ *
+ * <p>
+ * The implementations adhere to the properties of equals of:
+ * </p>
+ *
+ * <ul>
+ * <li>Reflective</li>
+ * <li>Symmetric</li>
+ * <li>Transitive</li>
+ * <li>Consistent</li>
+ * </ul>
+ *
+ * @param a Matrix Block a to compare
+ * @param b Matrix Block b to compare
+ * @param eps Epsilon to allow between values
+ * @return If the block are equivalent.
+ */
+ public static boolean equals(MatrixBlock a, MatrixBlock b, double eps) {
+ // Same object
+ if(a == b)
+ return true;
+ return new LibMatrixEquals(a, b, eps).exec();
+ }
+
+ /**
+ * Execute the comparison
+ *
+ * @return if the blocks are equivalent
+ */
+ private boolean exec() {
+ if(isMetadataDifferent())
+ return false;
+ Boolean empty = isEmpty();
+ if(empty != null)
+ return empty;
+
+ if(a.denseBlock != null && b.denseBlock != null)
+ return a.denseBlock.equals(b.denseBlock, eps);
+ return genericEquals();
+ }
+
+ /**
+ * Compare metadata, and return true if metadata is different
+ *
+ * @param a MatrixBlock a
+ * @param b MatrixBlock b
+ * @return If the metadata was comparable
+ */
+ private boolean isMetadataDifferent() {
+ boolean diff = false;
+
+ diff |= a.getNumRows() != b.getNumRows();
+ diff |= a.getNumColumns() != b.getNumColumns();
+ final long nnzA = a.getNonZeros();
+ final long nnzB = b.getNonZeros();
+ diff |= nnzA != -1 && nnzB != -1 && nnzA != nnzB;
+
+ return diff;
+ }
+
+ /**
+ * Empty metadata check. to verify if the content is empty and such.
+ *
+ * @return Boolean that is not null if something was found otherwise
null.
+ */
+ private Boolean isEmpty() {
+ final boolean emptyA = a.isEmpty();
+ final boolean emptyB = b.isEmpty();
+ // empty cases!
+ if(emptyA != emptyB)
+ return false;
+ else if(emptyA)
+ return true;
+ return null;
+ }
+
+ /**
+ * Generic implementation to cover all cases. But it is slow in most.
+ *
+ * @return if the matrices are equivalent.
+ */
+ private boolean genericEquals() {
+ LOG.warn("Using generic equals, potential optimizations are
possible");
+ final int rows = a.getNumRows();
+ final int cols = a.getNumColumns();
+
+ for(int i = 0; i < rows; i++)
+ for(int j = 0; j < cols; j++)
+ if(Math.abs(a.quickGetValue(i, j) -
b.quickGetValue(i, j)) > eps)
+ return false;
+ return true;
+ }
+}
diff --git
a/src/main/java/org/apache/sysds/runtime/matrix/data/MatrixBlock.java
b/src/main/java/org/apache/sysds/runtime/matrix/data/MatrixBlock.java
index 07c8f3031f..7da4acae46 100644
--- a/src/main/java/org/apache/sysds/runtime/matrix/data/MatrixBlock.java
+++ b/src/main/java/org/apache/sysds/runtime/matrix/data/MatrixBlock.java
@@ -5867,9 +5867,33 @@ public class MatrixBlock extends MatrixValue implements
CacheBlock, Externalizab
@Override
public final boolean equals(Object arg0) {
- throw new RuntimeException("equals should never be called for
matrix blocks.");
+ if(arg0 instanceof MatrixBlock)
+ return LibMatrixEquals.equals(this, (MatrixBlock) arg0);
+ return false;
}
-
+
+ /**
+ * Analyze if the matrixBlocks are equivalent, the comparsion supports
if the differnet sides are differently
+ * allocated such as sparse and dense.
+ *
+ * <p>
+ * The implementations adhere to the properties of equals of:
+ * </p>
+ *
+ * <ul>
+ * <li>Reflective</li>
+ * <li>Symmetric</li>
+ * <li>Transitive</li>
+ * <li>Consistent</li>
+ * </ul>
+ *
+ * @param arg0 MatrixBlock to compare
+ * @return If the matrices are equivalent
+ */
+ public final boolean equals(MatrixBlock arg0) {
+ return LibMatrixEquals.equals(this, arg0);
+ }
+
@Override
public final int hashCode() {
throw new RuntimeException("HashCode should never be called for
matrix blocks.");
diff --git
a/src/test/java/org/apache/sysds/test/component/matrix/EqualsTest.java
b/src/test/java/org/apache/sysds/test/component/matrix/EqualsTest.java
new file mode 100644
index 0000000000..36fe9914da
--- /dev/null
+++ b/src/test/java/org/apache/sysds/test/component/matrix/EqualsTest.java
@@ -0,0 +1,291 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.sysds.test.component.matrix;
+
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import org.apache.sysds.runtime.matrix.data.LibMatrixEquals;
+import org.apache.sysds.runtime.matrix.data.MatrixBlock;
+import org.apache.sysds.test.TestUtils;
+import org.junit.Test;
+
+public class EqualsTest {
+
+ @Test
+ public void sameObject() {
+ MatrixBlock mb = new MatrixBlock();
+ assertTrue(mb.equals(mb));
+ }
+
+ @Test
+ public void sameObject2() {
+ MatrixBlock mb = new MatrixBlock(10, 10, -2.0);
+ assertTrue(mb.equals(mb));
+ }
+
+ @Test
+ public void sameObjectInterface() {
+ MatrixBlock mb = new MatrixBlock(10, 10, -2.0);
+ assertTrue(LibMatrixEquals.equals(mb, mb));
+ }
+
+ @Test
+ public void sameObjectInterface2() {
+ MatrixBlock mb = new MatrixBlock(10, 10, -2.0);
+ assertTrue(LibMatrixEquals.equals(mb, mb, 1.0));
+ }
+
+ @Test
+ public void sameIfConstructedEqual_Empty() {
+ MatrixBlock mb1 = new MatrixBlock();
+ MatrixBlock mb2 = new MatrixBlock();
+ assertTrue(mb1.equals(mb2));
+ assertTrue(mb2.equals(mb1));
+ }
+
+ @Test
+ public void sameIfConstructedEqual_CastToObject() {
+ MatrixBlock mb1 = new MatrixBlock();
+ MatrixBlock mb2 = new MatrixBlock();
+ assertTrue(mb1.equals((Object) mb2));
+ assertTrue(mb2.equals((Object) mb1));
+ }
+
+ @Test
+ public void oneIsEmpty() {
+ MatrixBlock empty = new MatrixBlock(10, 10, 0.0);
+ MatrixBlock full = new MatrixBlock(10, 10, 1.0);
+
+ assertFalse(empty.equals(full));
+ assertFalse(full.equals(empty));
+ }
+
+ @Test
+ public void diffRows() {
+
+ MatrixBlock empty = new MatrixBlock(11, 10, 0.0);
+ MatrixBlock empty2 = new MatrixBlock(10, 10, 0.0);
+
+ assertFalse(empty.equals(empty2));
+ assertFalse(empty2.equals(empty));
+ }
+
+ @Test
+ public void diffCols() {
+
+ MatrixBlock empty = new MatrixBlock(10, 10, 0.0);
+ MatrixBlock empty2 = new MatrixBlock(10, 11, 0.0);
+
+ assertFalse(empty.equals(empty2));
+ assertFalse(empty2.equals(empty));
+ }
+
+ @Test
+ public void diffRowsAndCols() {
+
+ MatrixBlock empty = new MatrixBlock(13, 10, 0.0);
+ MatrixBlock empty2 = new MatrixBlock(10, 11, 0.0);
+
+ assertFalse(empty.equals(empty2));
+ assertFalse(empty2.equals(empty));
+ }
+
+ @Test
+ public void diffNNZ() {
+
+ MatrixBlock m1 = new MatrixBlock(10, 10, 0.0);
+ MatrixBlock m2 = new MatrixBlock(10, 10, 0.0);
+
+ m1.setValue(1, 1, 3);
+ m1.setValue(1, 2, 3);
+
+ m2.setValue(1, 1, 3);
+ m2.setValue(1, 2, 3);
+ m2.setValue(1, 3, 3);
+
+ assertFalse(m1.equals(m2));
+ assertFalse(m2.equals(m1));
+ }
+
+ @Test
+ public void unknownNNZ_m1() {
+
+ MatrixBlock m1 = new MatrixBlock(10, 10, 0.0);
+ MatrixBlock m2 = new MatrixBlock(10, 10, 0.0);
+
+ m1.setValue(1, 1, 3);
+ m1.setValue(1, 2, 3);
+
+ m1.setNonZeros(-1);
+
+ m2.setValue(1, 1, 3);
+ m2.setValue(1, 2, 3);
+ m2.setValue(1, 3, 3);
+
+ assertFalse(m1.equals(m2));
+ assertFalse(m2.equals(m1));
+ }
+
+ @Test
+ public void unknownNNZ_m2() {
+
+ MatrixBlock m1 = new MatrixBlock(10, 10, 0.0);
+ MatrixBlock m2 = new MatrixBlock(10, 10, 0.0);
+
+ m1.setValue(1, 1, 3);
+ m1.setValue(1, 2, 3);
+
+ m2.setValue(1, 1, 3);
+ m2.setValue(1, 2, 3);
+ m2.setValue(1, 3, 3);
+
+ m2.setNonZeros(-1);
+
+ assertFalse(m1.equals(m2));
+ assertFalse(m2.equals(m1));
+ }
+
+ @Test
+ public void unknownNNZboth() {
+
+ MatrixBlock m1 = new MatrixBlock(10, 10, 0.0);
+ MatrixBlock m2 = new MatrixBlock(10, 10, 0.0);
+
+ m1.setValue(1, 1, 3);
+ m1.setValue(1, 2, 3);
+
+ m1.setNonZeros(-1);
+
+ m2.setValue(1, 1, 3);
+ m2.setValue(1, 2, 3);
+ m2.setValue(1, 3, 3);
+
+ m2.setNonZeros(-1);
+
+ assertFalse(m1.equals(m2));
+ assertFalse(m2.equals(m1));
+ }
+
+ @Test
+ public void unknownNNZEmptyBoth() {
+
+ MatrixBlock m1 = new MatrixBlock(10, 10, 0.0);
+ MatrixBlock m2 = new MatrixBlock(10, 10, 0.0);
+
+ m1.setNonZeros(-1);
+ m2.setNonZeros(-1);
+
+ assertTrue(m1.equals(m2));
+ assertTrue(m2.equals(m1));
+ }
+
+ @Test
+ public void unknownNNZEmptyOne() {
+
+ MatrixBlock m1 = new MatrixBlock(10, 10, 0.0);
+ MatrixBlock m2 = new MatrixBlock(10, 10, 0.0);
+
+ m1.setNonZeros(-1);
+
+ assertTrue(m1.equals(m2));
+ assertTrue(m2.equals(m1));
+ }
+
+ @Test
+ public void unknownNNZEmptyOneFull() {
+
+ MatrixBlock m1 = new MatrixBlock(10, 10, 0.0);
+ MatrixBlock m2 = new MatrixBlock(10, 10, 1.0);
+
+ m2.setNonZeros(-1);
+
+ assertFalse(m1.equals(m2));
+ assertFalse(m2.equals(m1));
+ }
+
+ @Test
+ public void equivalentWithVeryVerySmallEps() {
+ MatrixBlock m1 = new MatrixBlock(10, 10, 1.0 + Double.MIN_VALUE
* 10);
+ MatrixBlock m2 = new MatrixBlock(10, 10, 1.0);
+ assertTrue(m1.equals(m2));
+ assertTrue(m2.equals(m1));
+ }
+
+ @Test
+ public void equivalentWithEpsSet() {
+ MatrixBlock m1 = new MatrixBlock(10, 10, 1.0 + 1.0);
+ MatrixBlock m2 = new MatrixBlock(10, 10, 1.0);
+ assertTrue(LibMatrixEquals.equals(m1, m2, 1.0));
+ assertTrue(LibMatrixEquals.equals(m2, m1, 1.0));
+ }
+
+ @Test
+ public void notEquivalentWithEpsSet() {
+ MatrixBlock m1 = new MatrixBlock(10, 10, 1.0 + 1.0);
+ MatrixBlock m2 = new MatrixBlock(10, 10, 1.0);
+ assertFalse(LibMatrixEquals.equals(m1, m2, 0.9999));
+ assertFalse(LibMatrixEquals.equals(m2, m1, 0.9999));
+ }
+
+ @Test
+ public void testSparse() {
+
+ MatrixBlock m1 = TestUtils.generateTestMatrixBlock(100, 1000,
0, 100, 0.05, 231);
+ MatrixBlock m2 = TestUtils.generateTestMatrixBlock(100, 1000,
0, 100, 0.05, 231);
+ assertTrue(LibMatrixEquals.equals(m1, m2, 0.00000001));
+ assertTrue(LibMatrixEquals.equals(m2, m1, 0.00000001));
+ }
+
+ @Test
+ public void testSparseOneForcedDense() {
+
+ MatrixBlock m1 = TestUtils.generateTestMatrixBlock(100, 100, 0,
100, 0.05, 231);
+ MatrixBlock m2 = TestUtils.generateTestMatrixBlock(100, 100, 0,
100, 0.05, 231);
+ m1.sparseToDense();
+ assertTrue(LibMatrixEquals.equals(m1, m2, 0.00000001));
+ assertTrue(LibMatrixEquals.equals(m2, m1, 0.00000001));
+ }
+
+ @Test
+ public void testSparseOneForcedDenseNotEquivalent() {
+
+ MatrixBlock m1 = TestUtils.generateTestMatrixBlock(100, 100, 0,
100, 0.05, 231);
+ MatrixBlock m2 = TestUtils.generateTestMatrixBlock(100, 100, 0,
100, 0.05, 231);
+
+ m1.getSparseBlock().get(13).values()[2] = 1324;
+ m2.sparseToDense();
+
+ assertFalse(LibMatrixEquals.equals(m1, m2, 0.00000001));
+ assertFalse(LibMatrixEquals.equals(m2, m1, 0.00000001));
+ }
+
+ @Test
+ public void testSparseNotEquivalent() {
+
+ MatrixBlock m1 = TestUtils.generateTestMatrixBlock(100, 1000,
0, 100, 0.05, 231);
+ MatrixBlock m2 = TestUtils.generateTestMatrixBlock(100, 1000,
0, 100, 0.05, 231);
+
+ m1.getSparseBlock().get(13).values()[2] = 1324;
+
+ assertFalse(LibMatrixEquals.equals(m1, m2, 0.00000001));
+ assertFalse(LibMatrixEquals.equals(m2, m1, 0.00000001));
+ }
+}
