This is an automated email from the ASF dual-hosted git repository. leerho pushed a commit to branch Renaming in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-java.git
commit 83b9de91c5c3ced74e3fe13c8fa09d869afe2fa2 Author: Lee Rhodes <[email protected]> AuthorDate: Sat Jun 6 18:26:06 2020 -0700 The use of "key" had multiple meanings. In some places it meant the user supplied key and other places it meant the hash of the user key. This was very confusing. This has been fixed. Similarly "keys_" meant a compact array of hashes and in other places a hash table. The arrays keys_ and summaries_ in Sketch<S> had overloaded uses. These two arrays were moved down a level to the CompactSketch and the QuickSelectSketch to eliminate this confusion. In the process of correcting this renaming and separation of uses, I uncovered numerous questionable codings that could easily have caused bugs. Certainly these confusions made the code harder to maintain and understand. --- .../java/org/apache/datasketches/tuple/AnotB.java | 243 ++++++++++++--------- .../apache/datasketches/tuple/CompactSketch.java | 61 ++++-- .../java/org/apache/datasketches/tuple/Filter.java | 2 +- .../apache/datasketches/tuple/Intersection.java | 111 +++++----- .../datasketches/tuple/QuickSelectSketch.java | 159 ++++++++------ .../java/org/apache/datasketches/tuple/Sketch.java | 24 +- .../apache/datasketches/tuple/SketchIterator.java | 37 +++- .../org/apache/datasketches/tuple/Summary.java | 2 +- .../datasketches/tuple/SummarySetOperations.java | 4 +- .../java/org/apache/datasketches/tuple/Union.java | 69 +++--- .../apache/datasketches/tuple/UpdatableSketch.java | 8 +- .../tuple/adouble/DoubleSummarySetOperations.java | 2 +- .../aninteger/IntegerSummarySetOperations.java | 2 +- .../tuple/adouble/AdoubleIntersectionTest.java | 2 + 14 files changed, 413 insertions(+), 313 deletions(-) diff --git a/src/main/java/org/apache/datasketches/tuple/AnotB.java b/src/main/java/org/apache/datasketches/tuple/AnotB.java index daef6d1..c10b096 100644 --- a/src/main/java/org/apache/datasketches/tuple/AnotB.java +++ b/src/main/java/org/apache/datasketches/tuple/AnotB.java @@ -38,8 +38,8 @@ import org.apache.datasketches.theta.HashIterator; public final class AnotB<S extends Summary> { private boolean empty_ = true; private long thetaLong_ = Long.MAX_VALUE; - private long[] keys_ = null; //always in compact form, not necessarily sorted - private S[] summaries_ = null; //always in compact form, not necessarily sorted + private long[] hashArr_ = null; //always in compact form, not necessarily sorted + private S[] summaryArr_ = null; //always in compact form, not necessarily sorted private int count_ = 0; /** @@ -65,8 +65,8 @@ public final class AnotB<S extends Summary> { final CompactSketch<S> cskA = (skA instanceof CompactSketch) ? (CompactSketch<S>)skA : ((QuickSelectSketch<S>)skA).compact(); - keys_ = cskA.keys_; - summaries_ = cskA.summaries_; + hashArr_ = cskA.getHashArr(); + summaryArr_ = cskA.getSummaryArr(); count_ = cskA.getRetainedEntries(); } @@ -83,31 +83,41 @@ public final class AnotB<S extends Summary> { //skB is not empty final long thetaLongB = skB.getThetaLong(); thetaLong_ = Math.min(thetaLong_, thetaLongB); - //Build hashtable and removes keys of skB >= theta + + //Build hashtable and removes hashes of skB >= theta final int countB = skB.getRetainedEntries(); - final long[] hashTableKeysB = convertToHashTable(skB.keys_, countB, thetaLong_); + CompactSketch<S> cskB = null; + QuickSelectSketch<S> qskB = null; + final long[] hashTableB; + if (skB instanceof CompactSketch) { + cskB = (CompactSketch<S>) skB; + hashTableB = convertToHashTable(cskB.getHashArr(), countB, thetaLong_); + } else { + qskB = (QuickSelectSketch<S>) skB; + hashTableB = convertToHashTable(qskB.getHashTable(), countB, thetaLong_); + } //build temporary arrays of skA - final long[] tmpKeysA = new long[count_]; - final S[] tmpSummariesA = - (S[]) Array.newInstance(summaries_.getClass().getComponentType(), count_); + final long[] tmpHashArrA = new long[count_]; + final Class<S> summaryType = (Class<S>) summaryArr_.getClass().getComponentType(); + final S[] tmpSummaryArrA = (S[]) Array.newInstance(summaryType, count_); //search for non matches and build temp arrays int nonMatches = 0; for (int i = 0; i < count_; i++) { - final long key = keys_[i]; - if ((key != 0) && (key < thetaLong_)) { //skips keys of A >= theta + final long hash = hashArr_[i]; + if ((hash != 0) && (hash < thetaLong_)) { //skips hashes of A >= theta final int index = - HashOperations.hashSearch(hashTableKeysB, simpleIntLog2(hashTableKeysB.length), key); + HashOperations.hashSearch(hashTableB, simpleIntLog2(hashTableB.length), hash); if (index == -1) { - tmpKeysA[nonMatches] = key; - tmpSummariesA[nonMatches] = summaries_[i]; + tmpHashArrA[nonMatches] = hash; + tmpSummaryArrA[nonMatches] = summaryArr_[i]; nonMatches++; } } } - keys_ = Arrays.copyOfRange(tmpKeysA, 0, nonMatches); - summaries_ = Arrays.copyOfRange(tmpSummariesA, 0, nonMatches); + hashArr_ = Arrays.copyOfRange(tmpHashArrA, 0, nonMatches); + summaryArr_ = Arrays.copyOfRange(tmpSummaryArrA, 0, nonMatches); count_ = nonMatches; } @@ -124,32 +134,32 @@ public final class AnotB<S extends Summary> { //skB is not empty final long thetaLongB = skB.getThetaLong(); thetaLong_ = Math.min(thetaLong_, thetaLongB); - //Build hashtable and removes keys of skB >= theta + //Build hashtable and removes hashes of skB >= theta final int countB = skB.getRetainedEntries(); - final long[] hashTableKeysB = + final long[] hashTableB = convertToHashTable(extractThetaHashArray(skB, countB), countB, thetaLong_); //build temporary arrays of skA - final long[] tmpKeysA = new long[count_]; - final S[] tmpSummariesA = - (S[]) Array.newInstance(summaries_.getClass().getComponentType(), count_); + final long[] tmpHashArrA = new long[count_]; + final Class<S> summaryType = (Class<S>) summaryArr_.getClass().getComponentType(); + final S[] tmpSummaryArrA = (S[]) Array.newInstance(summaryType, count_); //search for non matches and build temp arrays int nonMatches = 0; for (int i = 0; i < count_; i++) { - final long key = keys_[i]; - if ((key > 0) && (key < thetaLong_)) { //skips keys of A >= theta + final long hash = hashArr_[i]; + if ((hash > 0) && (hash < thetaLong_)) { //skips hashes of A >= theta final int index = - HashOperations.hashSearch(hashTableKeysB, simpleIntLog2(hashTableKeysB.length), key); + HashOperations.hashSearch(hashTableB, simpleIntLog2(hashTableB.length), hash); if (index == -1) { - tmpKeysA[nonMatches] = key; - tmpSummariesA[nonMatches] = summaries_[i]; + tmpHashArrA[nonMatches] = hash; + tmpSummaryArrA[nonMatches] = summaryArr_[i]; nonMatches++; } } } - keys_ = Arrays.copyOfRange(tmpKeysA, 0, nonMatches); - summaries_ = Arrays.copyOfRange(tmpSummariesA, 0, nonMatches); + hashArr_ = Arrays.copyOfRange(tmpHashArrA, 0, nonMatches); + summaryArr_ = Arrays.copyOfRange(tmpSummaryArrA, 0, nonMatches); count_ = nonMatches; } @@ -182,44 +192,55 @@ public final class AnotB<S extends Summary> { final CompactSketch<S> cskA = (skA instanceof CompactSketch) ? (CompactSketch<S>)skA : ((QuickSelectSketch<S>)skA).compact(); - final long[] keysA = cskA.keys_; - final S[] summariesA = cskA.summaries_; + final long[] hashArrA = cskA.getHashArr(); + final S[] summaryArrA = cskA.getSummaryArr(); final int countA = cskA.getRetainedEntries(); if (skB.isEmpty()) { - return new CompactSketch<>(keysA, summariesA, thetaLongA, empty); + return new CompactSketch<>(hashArrA, summaryArrA, thetaLongA, empty); } //skB is not empty final long thetaLongB = skB.getThetaLong(); final long thetaLong = Math.min(thetaLongA, thetaLongB); - //Build hashtable and removes keys of skB >= theta final int countB = skB.getRetainedEntries(); - final long[] hashTableKeysB = - convertToHashTable(skB.keys_, countB, thetaLong); + // + CompactSketch<S> cskB = null; + QuickSelectSketch<S> qskB = null; + + //Build/rebuild hashtable and removes hashes of skB >= thetaLong + final long[] hashTableB; + if (skB instanceof CompactSketch) { + cskB = (CompactSketch<S>) skB; + hashTableB = convertToHashTable(cskB.getHashArr(), countB, thetaLong); + } else { + qskB = (QuickSelectSketch<S>) skB; + hashTableB = convertToHashTable(qskB.getHashTable(), countB, thetaLong); + cskB = qskB.compact(); + } //build temporary arrays of skA - final long[] tmpKeysA = new long[countA]; - final S[] tmpSummariesA = - (S[]) Array.newInstance(summariesA.getClass().getComponentType(), countA); + final long[] tmpHashArrA = new long[countA]; + final Class<S> summaryType = (Class<S>) summaryArrA.getClass().getComponentType(); + final S[] tmpSummaryArrA = (S[]) Array.newInstance(summaryType, countA); //search for non matches and build temp arrays int nonMatches = 0; for (int i = 0; i < countA; i++) { - final long key = keysA[i]; - if ((key != 0) && (key < thetaLong)) { //skips keys of A >= theta + final long hash = hashArrA[i]; + if ((hash != 0) && (hash < thetaLong)) { //skips hashes of A >= theta final int index = - HashOperations.hashSearch(hashTableKeysB, simpleIntLog2(hashTableKeysB.length), key); + HashOperations.hashSearch(hashTableB, simpleIntLog2(hashTableB.length), hash); if (index == -1) { - tmpKeysA[nonMatches] = key; - tmpSummariesA[nonMatches] = summariesA[i]; + tmpHashArrA[nonMatches] = hash; + tmpSummaryArrA[nonMatches] = summaryArrA[i]; nonMatches++; } } } - final long[] keys = Arrays.copyOfRange(tmpKeysA, 0, nonMatches); - final S[] summaries = Arrays.copyOfRange(tmpSummariesA, 0, nonMatches); + final long[] hashArrOut = Arrays.copyOfRange(tmpHashArrA, 0, nonMatches); + final S[] summaryArrOut = Arrays.copyOfRange(tmpSummaryArrA, 0, nonMatches); final CompactSketch<S> result = - new CompactSketch<>(keys, summaries, thetaLong, empty); + new CompactSketch<>(hashArrOut, summaryArrOut, thetaLong, empty); return result; } @@ -252,44 +273,45 @@ public final class AnotB<S extends Summary> { final CompactSketch<S> cskA = (skA instanceof CompactSketch) ? (CompactSketch<S>)skA : ((QuickSelectSketch<S>)skA).compact(); - final long[] keysA = cskA.keys_; - final S[] summariesA = cskA.summaries_; + final long[] hashArrA = cskA.getHashArr(); + final S[] summaryArrA = cskA.getSummaryArr(); final int countA = cskA.getRetainedEntries(); if (skB.isEmpty()) { - return new CompactSketch<>(keysA, summariesA, thetaLongA, empty); + return new CompactSketch<>(hashArrA, summaryArrA, thetaLongA, empty); } //skB is not empty final long thetaLongB = skB.getThetaLong(); final long thetaLong = Math.min(thetaLongA, thetaLongB); - //Build hashtable and removes keys of skB >= theta final int countB = skB.getRetainedEntries(); - final long[] hashTableKeysB = + + //Build/rebuild hashtable and removes hashes of skB >= thetaLong + final long[] hashTableB = //this works for all theta sketches convertToHashTable(extractThetaHashArray(skB, countB), countB, thetaLong); - //build temporary arrays of skA - final long[] tmpKeysA = new long[countA]; - final S[] tmpSummariesA = - (S[]) Array.newInstance(summariesA.getClass().getComponentType(), countA); + //build temporary arrays of skA for matching + final long[] tmpHashArrA = new long[countA]; + final Class<S> summaryType = (Class<S>) summaryArrA.getClass().getComponentType(); + final S[] tmpSummaryArrA = (S[]) Array.newInstance(summaryType, countA); //search for non matches and build temp arrays int nonMatches = 0; for (int i = 0; i < countA; i++) { - final long key = keysA[i]; - if ((key != 0) && (key < thetaLong)) { //skips keys of A >= theta + final long hash = hashArrA[i]; + if ((hash != 0) && (hash < thetaLong)) { //skips hashes of A >= theta final int index = - HashOperations.hashSearch(hashTableKeysB, simpleIntLog2(hashTableKeysB.length), key); + HashOperations.hashSearch(hashTableB, simpleIntLog2(hashTableB.length), hash); if (index == -1) { - tmpKeysA[nonMatches] = key; - tmpSummariesA[nonMatches] = summariesA[i]; + tmpHashArrA[nonMatches] = hash; + tmpSummaryArrA[nonMatches] = summaryArrA[i]; nonMatches++; } } } - final long[] keys = Arrays.copyOfRange(tmpKeysA, 0, nonMatches); - final S[] summaries = Arrays.copyOfRange(tmpSummariesA, 0, nonMatches); + final long[] hashArr = Arrays.copyOfRange(tmpHashArrA, 0, nonMatches); + final S[] summaryArr = Arrays.copyOfRange(tmpSummaryArrA, 0, nonMatches); final CompactSketch<S> result = - new CompactSketch<>(keys, summaries, thetaLong, empty); + new CompactSketch<>(hashArr, summaryArr, thetaLong, empty); return result; } @@ -303,8 +325,8 @@ public final class AnotB<S extends Summary> { return new CompactSketch<>(null, null, thetaLong_, empty_); } final CompactSketch<S> result = - new CompactSketch<>(Arrays.copyOfRange(keys_, 0, count_), - Arrays.copyOfRange(summaries_, 0, count_), thetaLong_, empty_); + new CompactSketch<>(Arrays.copyOfRange(hashArr_, 0, count_), + Arrays.copyOfRange(summaryArr_, 0, count_), thetaLong_, empty_); if (reset) { reset(); } return result; } @@ -315,8 +337,8 @@ public final class AnotB<S extends Summary> { public void reset() { empty_ = true; thetaLong_ = Long.MAX_VALUE; - keys_ = null; - summaries_ = null; + hashArr_ = null; + summaryArr_ = null; count_ = 0; } @@ -333,14 +355,14 @@ public final class AnotB<S extends Summary> { return hashArr; } - private static long[] convertToHashTable(final long[] keysArr, final int count, final long thetaLong) { + private static long[] convertToHashTable(final long[] hashArr, final int count, final long thetaLong) { final int size = Math.max( ceilingPowerOf2((int) Math.ceil(count / REBUILD_THRESHOLD)), 1 << MIN_LG_NOM_LONGS ); final long[] hashTable = new long[size]; HashOperations.hashArrayInsert( - keysArr, hashTable, Integer.numberOfTrailingZeros(size), thetaLong); + hashArr, hashTable, Integer.numberOfTrailingZeros(size), thetaLong); return hashTable; } @@ -353,41 +375,58 @@ public final class AnotB<S extends Summary> { * without calling getResult() will discard the result of previous update() by this method. * The result is obtained by calling getResult(); * - * @param a The incoming sketch for the first argument - * @param b The incoming sketch for the second argument + * @param skA The incoming sketch for the first argument + * @param skB The incoming sketch for the second argument * @deprecated After release 2.0.0. Instead please use {@link #aNotB(Sketch, Sketch)} * or a combination of {@link #setA(Sketch)} and * {@link #notB(Sketch)} with {@link #getResult(boolean)}. */ @SuppressWarnings("unchecked") @Deprecated - public void update(final Sketch<S> a, final Sketch<S> b) { - if (a != null) { empty_ = a.isEmpty(); } //stays this way even if we end up with no result entries - final long thetaA = a == null ? Long.MAX_VALUE : a.getThetaLong(); - final long thetaB = b == null ? Long.MAX_VALUE : b.getThetaLong(); + public void update(final Sketch<S> skA, final Sketch<S> skB) { + if (skA != null) { empty_ = skA.isEmpty(); } //stays this way even if we end up with no result entries + final long thetaA = skA == null ? Long.MAX_VALUE : skA.getThetaLong(); + final long thetaB = skB == null ? Long.MAX_VALUE : skB.getThetaLong(); thetaLong_ = Math.min(thetaA, thetaB); - if ((a == null) || (a.getRetainedEntries() == 0)) { return; } - if ((b == null) || (b.getRetainedEntries() == 0)) { - loadCompactedArrays(a); - } else { - final long[] hashTable; - if (b instanceof CompactSketch) { - hashTable = convertToHashTable(b.keys_, b.getRetainedEntries(), thetaLong_); + if ((skA == null) || (skA.getRetainedEntries() == 0)) { return; } + if ((skB == null) || (skB.getRetainedEntries() == 0)) { + loadCompactedArrays(skA); + } + //neither A or B is null nor with zero entries + else { + final long[] hashTableB; + final int count = skB.getRetainedEntries(); + + CompactSketch<S> csk = null; + QuickSelectSketch<S> qsk = null; + final int lgHashTableSize; + final Class<S> summaryType; + + if (skB instanceof CompactSketch) { + csk = (CompactSketch<S>) skB; + hashTableB = convertToHashTable(csk.getHashArr(), count, thetaLong_); + summaryType = (Class<S>) csk.getSummaryArr().getClass().getComponentType(); + lgHashTableSize = Integer.numberOfTrailingZeros(hashTableB.length); } else { - hashTable = b.keys_; + qsk = (QuickSelectSketch<S>) skB; + hashTableB = convertToHashTable(qsk.getHashTable(), count, thetaLong_); + summaryType = (Class<S>) qsk.getSummaryTable().getClass().getComponentType(); + lgHashTableSize = Integer.numberOfTrailingZeros(hashTableB.length); } - final int lgHashTableSize = Integer.numberOfTrailingZeros(hashTable.length); - final int noMatchSize = a.getRetainedEntries(); - keys_ = new long[noMatchSize]; - summaries_ = (S[]) Array.newInstance(a.summaries_.getClass().getComponentType(), noMatchSize); - for (int i = 0; i < a.keys_.length; i++) { - if ((a.keys_[i] != 0) && (a.keys_[i] < thetaLong_)) { - final int index = HashOperations.hashSearch(hashTable, lgHashTableSize, a.keys_[i]); - if (index == -1) { - keys_[count_] = a.keys_[i]; - summaries_[count_] = a.summaries_[i]; - count_++; - } + //scan A, search B + final SketchIterator<S> itrA = skA.iterator(); + final int noMatchSize = skA.getRetainedEntries(); + hashArr_ = new long[noMatchSize]; + summaryArr_ = (S[]) Array.newInstance(summaryType, noMatchSize); + while (itrA.next()) { + final long hash = itrA.getHash(); + final S summary = itrA.getSummary(); + if ((hash <= 0) || (hash >= thetaLong_)) { continue; } + final int index = HashOperations.hashSearch(hashTableB, lgHashTableSize, hash); + if (index == -1) { + hashArr_[count_] = hash; + summaryArr_[count_] = summary; + count_++; } } } @@ -407,8 +446,8 @@ public final class AnotB<S extends Summary> { return new CompactSketch<>(null, null, thetaLong_, empty_); } final CompactSketch<S> result = - new CompactSketch<>(Arrays.copyOfRange(keys_, 0, count_), - Arrays.copyOfRange(summaries_, 0, count_), thetaLong_, empty_); + new CompactSketch<>(Arrays.copyOfRange(hashArr_, 0, count_), + Arrays.copyOfRange(summaryArr_, 0, count_), thetaLong_, empty_); reset(); return result; } @@ -419,13 +458,15 @@ public final class AnotB<S extends Summary> { * @param sketch the given sketch to extract arrays from. */ private void loadCompactedArrays(final Sketch<S> sketch) { + final CompactSketch<S> csk; if (sketch instanceof CompactSketch) { - keys_ = sketch.keys_.clone(); - summaries_ = sketch.summaries_.clone(); + csk = (CompactSketch<S>)sketch; + hashArr_ = csk.getHashArr().clone(); + summaryArr_ = csk.getSummaryArr().clone(); } else { // assuming only two types: CompactSketch and QuickSelectSketch - final CompactSketch<S> compact = ((QuickSelectSketch<S>)sketch).compact(); - keys_ = compact.keys_; - summaries_ = compact.summaries_; + csk = ((QuickSelectSketch<S>)sketch).compact(); + hashArr_ = csk.getHashArr(); + summaryArr_ = csk.getSummaryArr(); } count_ = sketch.getRetainedEntries(); } diff --git a/src/main/java/org/apache/datasketches/tuple/CompactSketch.java b/src/main/java/org/apache/datasketches/tuple/CompactSketch.java index e7a4a92..1d55515 100644 --- a/src/main/java/org/apache/datasketches/tuple/CompactSketch.java +++ b/src/main/java/org/apache/datasketches/tuple/CompactSketch.java @@ -40,14 +40,23 @@ import org.apache.datasketches.memory.Memory; public class CompactSketch<S extends Summary> extends Sketch<S> { private static final byte serialVersionWithSummaryClassNameUID = 1; private static final byte serialVersionUID = 2; + private long[] hashArr_; + private S[] summaryArr_; private enum Flags { IS_BIG_ENDIAN, IS_EMPTY, HAS_ENTRIES, IS_THETA_INCLUDED } - CompactSketch(final long[] keys, final S[] summaries, final long theta, final boolean isEmpty) { - keys_ = keys; - summaries_ = summaries; - theta_ = theta; - isEmpty_ = isEmpty; + /** + * Create a CompactSketch from correct components + * @param hashArr compacted hash array + * @param summaryArr compacted summary array + * @param thetaLong long value of theta + * @param isEmpty empty flag + */ + CompactSketch(final long[] hashArr, final S[] summaryArr, final long thetaLong, final boolean empty) { + hashArr_ = hashArr; + summaryArr_ = summaryArr; + thetaLong_ = thetaLong; + empty_ = empty; } /** @@ -74,13 +83,13 @@ public class CompactSketch<S extends Summary> extends Sketch<S> { if (isBigEndian ^ ByteOrder.nativeOrder().equals(ByteOrder.BIG_ENDIAN)) { throw new SketchesArgumentException("Byte order mismatch"); } - isEmpty_ = (flags & (1 << Flags.IS_EMPTY.ordinal())) > 0; + empty_ = (flags & (1 << Flags.IS_EMPTY.ordinal())) > 0; final boolean isThetaIncluded = (flags & (1 << Flags.IS_THETA_INCLUDED.ordinal())) > 0; if (isThetaIncluded) { - theta_ = mem.getLong(offset); + thetaLong_ = mem.getLong(offset); offset += Long.BYTES; } else { - theta_ = Long.MAX_VALUE; + thetaLong_ = Long.MAX_VALUE; } final boolean hasEntries = (flags & (1 << Flags.HAS_ENTRIES.ordinal())) > 0; if (hasEntries) { @@ -93,27 +102,36 @@ public class CompactSketch<S extends Summary> extends Sketch<S> { if (version == serialVersionWithSummaryClassNameUID) { offset += classNameLength; } - keys_ = new long[count]; + hashArr_ = new long[count]; for (int i = 0; i < count; i++) { - keys_[i] = mem.getLong(offset); + hashArr_[i] = mem.getLong(offset); offset += Long.BYTES; } for (int i = 0; i < count; i++) { final Memory memRegion = mem.region(offset, mem.getCapacity() - offset); final DeserializeResult<S> result = deserializer.heapifySummary(memRegion); final S summary = result.getObject(); + final Class<S> summaryType = (Class<S>) result.getObject().getClass(); offset += result.getSize(); - if (summaries_ == null) { - summaries_ = (S[]) Array.newInstance(summary.getClass(), count); + if (summaryArr_ == null) { + summaryArr_ = (S[]) Array.newInstance(summaryType, count); } - summaries_[i] = summary; + summaryArr_[i] = summary; } } } + long[] getHashArr() { + return hashArr_; + } + + S[] getSummaryArr() { + return summaryArr_; + } + @Override public int getRetainedEntries() { - return keys_ == null ? 0 : keys_.length; + return hashArr_ == null ? 0 : hashArr_.length; } // Layout of first 8 bytes: @@ -130,7 +148,7 @@ public class CompactSketch<S extends Summary> extends Sketch<S> { if (count > 0) { summariesBytes = new byte[count][]; for (int i = 0; i < count; i++) { - summariesBytes[i] = summaries_[i].toByteArray(); + summariesBytes[i] = summaryArr_[i].toByteArray(); summariesBytesLength += summariesBytes[i].length; } } @@ -141,7 +159,7 @@ public class CompactSketch<S extends Summary> extends Sketch<S> { + Byte.BYTES // family id + Byte.BYTES // sketch type + Byte.BYTES; // flags - final boolean isThetaIncluded = theta_ < Long.MAX_VALUE; + final boolean isThetaIncluded = thetaLong_ < Long.MAX_VALUE; if (isThetaIncluded) { sizeBytes += Long.BYTES; // theta } @@ -159,19 +177,19 @@ public class CompactSketch<S extends Summary> extends Sketch<S> { final boolean isBigEndian = ByteOrder.nativeOrder().equals(ByteOrder.BIG_ENDIAN); bytes[offset++] = (byte) ( (isBigEndian ? 1 << Flags.IS_BIG_ENDIAN.ordinal() : 0) - | (isEmpty_ ? 1 << Flags.IS_EMPTY.ordinal() : 0) + | (empty_ ? 1 << Flags.IS_EMPTY.ordinal() : 0) | (count > 0 ? 1 << Flags.HAS_ENTRIES.ordinal() : 0) | (isThetaIncluded ? 1 << Flags.IS_THETA_INCLUDED.ordinal() : 0) ); if (isThetaIncluded) { - ByteArrayUtil.putLongLE(bytes, offset, theta_); + ByteArrayUtil.putLongLE(bytes, offset, thetaLong_); offset += Long.BYTES; } if (count > 0) { ByteArrayUtil.putIntLE(bytes, offset, getRetainedEntries()); offset += Integer.BYTES; for (int i = 0; i < count; i++) { - ByteArrayUtil.putLongLE(bytes, offset, keys_[i]); + ByteArrayUtil.putLongLE(bytes, offset, hashArr_[i]); offset += Long.BYTES; } for (int i = 0; i < count; i++) { @@ -182,4 +200,9 @@ public class CompactSketch<S extends Summary> extends Sketch<S> { return bytes; } + @Override + public SketchIterator<S> iterator() { + return new SketchIterator<>(hashArr_, summaryArr_); + } + } diff --git a/src/main/java/org/apache/datasketches/tuple/Filter.java b/src/main/java/org/apache/datasketches/tuple/Filter.java index 5f7b096..727d4d5 100644 --- a/src/main/java/org/apache/datasketches/tuple/Filter.java +++ b/src/main/java/org/apache/datasketches/tuple/Filter.java @@ -59,7 +59,7 @@ public class Filter<T extends Summary> { while (it.next()) { final T summary = it.getSummary(); if (predicate.test(summary)) { - sketch.insert(it.getKey(), (T)summary.copy()); + sketch.insert(it.getHash(), (T)summary.copy()); } } diff --git a/src/main/java/org/apache/datasketches/tuple/Intersection.java b/src/main/java/org/apache/datasketches/tuple/Intersection.java index b4a9457..a88223b 100644 --- a/src/main/java/org/apache/datasketches/tuple/Intersection.java +++ b/src/main/java/org/apache/datasketches/tuple/Intersection.java @@ -98,28 +98,29 @@ public class Intersection<S extends Summary> { //Match nextSketch data with local instance data, filtering by theta final int maxMatchSize = min(hashTables_.count_, nextSketch.getRetainedEntries()); - final long[] matchKeys = new long[maxMatchSize]; + final long[] matchHashArr = new long[maxMatchSize]; S[] matchSummaries = null; int matchCount = 0; final SketchIterator<S> it = nextSketch.iterator(); + final Class<S> summaryType = (Class<S>) hashTables_.summaryTable_.getClass().getComponentType(); while (it.next()) { - final long key = it.getKey(); - if (key >= thetaLong_) { continue; } - final int index = hashSearch(hashTables_.keys_, hashTables_.lgTableSize_, key); + final long hash = it.getHash(); + if (hash >= thetaLong_) { continue; } + final int index = hashSearch(hashTables_.hashTable_, hashTables_.lgTableSize_, hash); if (index < 0) { continue; } //Copy the intersecting items from local hashTables_ - // sequentially into local matchKeys_ and matchSummaries_ - final S mySummary = hashTables_.summaries_[index]; + // sequentially into local matchHashArr_ and matchSummaries_ + final S mySummary = hashTables_.summaryTable_[index]; if (matchSummaries == null) { - matchSummaries = (S[]) Array.newInstance(mySummary.getClass(), maxMatchSize); + matchSummaries = (S[]) Array.newInstance(summaryType, maxMatchSize); } - matchKeys[matchCount] = key; + matchHashArr[matchCount] = hash; matchSummaries[matchCount] = summarySetOps_.intersection(mySummary, it.getSummary()); matchCount++; } - hashTables_.fromArrays(matchKeys, matchSummaries, matchCount); + hashTables_.fromArrays(matchHashArr, matchSummaries, matchCount); } } @@ -160,28 +161,29 @@ public class Intersection<S extends Summary> { //Match nextSketch data with local instance data, filtering by theta final int maxMatchSize = min(hashTables_.count_, nextSketch.getRetainedEntries()); - final long[] matchKeys = new long[maxMatchSize]; + final long[] matchHashArr = new long[maxMatchSize]; S[] matchSummaries = null; int matchCount = 0; final org.apache.datasketches.theta.HashIterator it = sketchIn.iterator(); + final Class<S> summaryType = (Class<S>) hashTables_.summaryTable_.getClass().getComponentType(); while (it.next()) { - final long key = it.get(); - if (key >= thetaLong_) { continue; } - final int index = hashSearch(hashTables_.keys_, hashTables_.lgTableSize_, key); + final long hash = it.get(); + if (hash >= thetaLong_) { continue; } + final int index = hashSearch(hashTables_.hashTable_, hashTables_.lgTableSize_, hash); if (index < 0) { continue; } //Copy the intersecting items from local hashTables_ - // sequentially into local matchKeys_ and matchSummaries_ - final S mySummary = hashTables_.summaries_[index]; + // sequentially into local matchHashArr and matchSummaries + final S mySummary = hashTables_.summaryTable_[index]; if (matchSummaries == null) { - matchSummaries = (S[]) Array.newInstance(mySummary.getClass(), maxMatchSize); + matchSummaries = (S[]) Array.newInstance(summaryType, maxMatchSize); } - matchKeys[matchCount] = key; + matchHashArr[matchCount] = hash; matchSummaries[matchCount] = summarySetOps_.intersection(mySummary, (S)mySummary.copy()); matchCount++; } - hashTables_.fromArrays(matchKeys, matchSummaries, matchCount); + hashTables_.fromArrays(matchHashArr, matchSummaries, matchCount); } } @@ -198,23 +200,24 @@ public class Intersection<S extends Summary> { return new CompactSketch<>(null, null, thetaLong_, empty_); } //Compact the hash tables - final int tableSize = hashTables_.keys_.length; - final long[] keys = new long[hashTables_.count_]; + final int tableSize = hashTables_.hashTable_.length; + final long[] hashArr = new long[hashTables_.count_]; S[] summaries = null; + final Class<S> summaryType = (Class<S>) hashTables_.summaryTable_.getClass().getComponentType(); int cnt = 0; for (int i = 0; i < tableSize; i++) { - final long key = hashTables_.keys_[i]; - if ((key == 0) || (key > thetaLong_)) { continue; } - final S summary = hashTables_.summaries_[i]; + final long hash = hashTables_.hashTable_[i]; + if ((hash == 0) || (hash > thetaLong_)) { continue; } + final S summary = hashTables_.summaryTable_[i]; if (summaries == null) { - summaries = (S[]) Array.newInstance(summary.getClass(), hashTables_.count_); + summaries = (S[]) Array.newInstance(summaryType, hashTables_.count_); } - keys[cnt] = key; + hashArr[cnt] = hash; summaries[cnt] = summary; cnt++; } assert cnt == hashTables_.count_; - return new CompactSketch<>(keys, summaries, thetaLong_, empty_); + return new CompactSketch<>(hashArr, summaries, thetaLong_, empty_); } /** @@ -233,8 +236,8 @@ public class Intersection<S extends Summary> { } private class HashTables { - long[] keys_ = null; - S[] summaries_ = null; + long[] hashTable_ = null; + S[] summaryTable_ = null; int lgTableSize_ = 0; int count_ = 0; @@ -245,17 +248,17 @@ public class Intersection<S extends Summary> { lgTableSize_ = getLgTableSize(count_); S mySummary = null; - keys_ = new long[1 << lgTableSize_]; + hashTable_ = new long[1 << lgTableSize_]; final SketchIterator<S> it = sketch.iterator(); while (it.next()) { - final long key = it.getKey(); - final int index = hashInsertOnly(keys_, lgTableSize_, key); + final long hash = it.getHash(); + final int index = hashInsertOnly(hashTable_, lgTableSize_, hash); mySummary = (S)it.getSummary().copy(); - if (summaries_ == null) { - summaries_ = (S[]) Array.newInstance(mySummary.getClass(), 1 << lgTableSize_); + if (summaryTable_ == null) { + summaryTable_ = (S[]) Array.newInstance(mySummary.getClass(), 1 << lgTableSize_); } - keys_[index] = key; - summaries_[index] = mySummary; + hashTable_[index] = hash; + summaryTable_[index] = mySummary; } } @@ -264,43 +267,43 @@ public class Intersection<S extends Summary> { lgTableSize_ = getLgTableSize(count_); S mySummary = null; - keys_ = new long[1 << lgTableSize_]; + hashTable_ = new long[1 << lgTableSize_]; final org.apache.datasketches.theta.HashIterator it = sketch.iterator(); while (it.next()) { - final long key = it.get(); - final int index = hashInsertOnly(keys_, lgTableSize_, key); + final long hash = it.get(); + final int index = hashInsertOnly(hashTable_, lgTableSize_, hash); mySummary = summary; - if (summaries_ == null) { - summaries_ = (S[]) Array.newInstance(mySummary.getClass(), 1 << lgTableSize_); + if (summaryTable_ == null) { + summaryTable_ = (S[]) Array.newInstance(mySummary.getClass(), 1 << lgTableSize_); } - keys_[index] = key; - summaries_[index] = mySummary; + hashTable_[index] = hash; + summaryTable_[index] = mySummary; } } - void fromArrays(final long[] keys, final S[] summaries, final int count) { + void fromArrays(final long[] hashArr, final S[] summaryArr, final int count) { count_ = count; lgTableSize_ = getLgTableSize(count); S mySummary = null; - summaries_ = null; - keys_ = new long[1 << lgTableSize_]; + summaryTable_ = null; + hashTable_ = new long[1 << lgTableSize_]; for (int i = 0; i < count; i++) { - final long key = keys[i]; - final int index = hashInsertOnly(keys_, lgTableSize_, key); - mySummary = summaries[i]; - if (summaries_ == null) { - summaries_ = (S[]) Array.newInstance(mySummary.getClass(), 1 << lgTableSize_); + final long hash = hashArr[i]; + final int index = hashInsertOnly(hashTable_, lgTableSize_, hash); + mySummary = summaryArr[i]; + if (summaryTable_ == null) { + summaryTable_ = (S[]) Array.newInstance(mySummary.getClass(), 1 << lgTableSize_); } - keys_[index] = key; - summaries_[index] = summaries[i]; + hashTable_[index] = hash; + summaryTable_[index] = summaryArr[i]; } } void clear() { - keys_ = null; - summaries_ = null; + hashTable_ = null; + summaryTable_ = null; lgTableSize_ = 0; count_ = 0; } diff --git a/src/main/java/org/apache/datasketches/tuple/QuickSelectSketch.java b/src/main/java/org/apache/datasketches/tuple/QuickSelectSketch.java index 1fe0fb7..599daed 100644 --- a/src/main/java/org/apache/datasketches/tuple/QuickSelectSketch.java +++ b/src/main/java/org/apache/datasketches/tuple/QuickSelectSketch.java @@ -54,6 +54,8 @@ class QuickSelectSketch<S extends Summary> extends Sketch<S> { private final SummaryFactory<S> summaryFactory_; private final float samplingProbability_; private int rebuildThreshold_; + private long[] hashTable_; + S[] summaryTable_; /** * This is to create an instance of a QuickSelectSketch with default resize factor. @@ -115,10 +117,10 @@ class QuickSelectSketch<S extends Summary> extends Sketch<S> { lgResizeFactor_ = lgResizeFactor; samplingProbability_ = samplingProbability; summaryFactory_ = summaryFactory; - theta_ = (long) (Long.MAX_VALUE * (double) samplingProbability); + thetaLong_ = (long) (Long.MAX_VALUE * (double) samplingProbability); lgCurrentCapacity_ = Integer.numberOfTrailingZeros(startingSize); - keys_ = new long[startingSize]; - summaries_ = null; // wait for the first summary to call Array.newInstance() + hashTable_ = new long[startingSize]; + summaryTable_ = null; // wait for the first summary to call Array.newInstance() setRebuildThreshold(); } @@ -160,10 +162,10 @@ class QuickSelectSketch<S extends Summary> extends Sketch<S> { final boolean isThetaIncluded = (flags & (1 << Flags.IS_THETA_INCLUDED.ordinal())) > 0; if (isThetaIncluded) { - theta_ = mem.getLong(offset); + thetaLong_ = mem.getLong(offset); offset += Long.BYTES; } else { - theta_ = (long) (Long.MAX_VALUE * (double) samplingProbability_); + thetaLong_ = (long) (Long.MAX_VALUE * (double) samplingProbability_); } int count = 0; @@ -173,25 +175,34 @@ class QuickSelectSketch<S extends Summary> extends Sketch<S> { offset += Integer.BYTES; } final int currentCapacity = 1 << lgCurrentCapacity_; - keys_ = new long[currentCapacity]; + hashTable_ = new long[currentCapacity]; for (int i = 0; i < count; i++) { - final long key = mem.getLong(offset); + final long hash = mem.getLong(offset); offset += Long.BYTES; final Memory memRegion = mem.region(offset, mem.getCapacity() - offset); final DeserializeResult<S> summaryResult = deserializer.heapifySummary(memRegion); final S summary = summaryResult.getObject(); offset += summaryResult.getSize(); - insert(key, summary); + insert(hash, summary); } - isEmpty_ = (flags & (1 << Flags.IS_EMPTY.ordinal())) > 0; + empty_ = (flags & (1 << Flags.IS_EMPTY.ordinal())) > 0; setRebuildThreshold(); } + long[] getHashTable() { + return hashTable_; + } + @Override public int getRetainedEntries() { return count_; } + S[] getSummaryTable() { + return summaryTable_; + } + + /** * Get configured nominal number of entries * @return nominal number of entries @@ -238,7 +249,7 @@ class QuickSelectSketch<S extends Summary> extends Sketch<S> { public void trim() { if (count_ > nomEntries_) { updateTheta(); - rebuild(keys_.length); + rebuild(hashTable_.length); } } @@ -246,13 +257,13 @@ class QuickSelectSketch<S extends Summary> extends Sketch<S> { * Resets this sketch an empty state. */ public void reset() { - isEmpty_ = true; + empty_ = true; count_ = 0; - theta_ = (long) (Long.MAX_VALUE * (double) samplingProbability_); + thetaLong_ = (long) (Long.MAX_VALUE * (double) samplingProbability_); final int startingCapacity = Util.getStartingCapacity(nomEntries_, lgResizeFactor_); lgCurrentCapacity_ = Integer.numberOfTrailingZeros(startingCapacity); - keys_ = new long[startingCapacity]; - summaries_ = null; // wait for the first summary to call Array.newInstance() + hashTable_ = new long[startingCapacity]; + summaryTable_ = null; // wait for the first summary to call Array.newInstance() setRebuildThreshold(); } @@ -263,20 +274,20 @@ class QuickSelectSketch<S extends Summary> extends Sketch<S> { @SuppressWarnings("unchecked") public CompactSketch<S> compact() { if (getRetainedEntries() == 0) { - return new CompactSketch<>(null, null, theta_, isEmpty_); + return new CompactSketch<>(null, null, thetaLong_, empty_); } - final long[] keys = new long[getRetainedEntries()]; - final S[] summaries = (S[]) - Array.newInstance(summaries_.getClass().getComponentType(), getRetainedEntries()); + final long[] hashArr = new long[getRetainedEntries()]; + final S[] summaryArr = (S[]) + Array.newInstance(summaryTable_.getClass().getComponentType(), getRetainedEntries()); int i = 0; - for (int j = 0; j < keys_.length; j++) { - if (summaries_[j] != null) { - keys[i] = keys_[j]; - summaries[i] = (S)summaries_[j].copy(); + for (int j = 0; j < hashTable_.length; j++) { + if (summaryTable_[j] != null) { + hashArr[i] = hashTable_[j]; + summaryArr[i] = (S)summaryTable_[j].copy(); i++; } } - return new CompactSketch<>(keys, summaries, theta_, isEmpty_); + return new CompactSketch<>(hashArr, summaryArr, thetaLong_, empty_); } // Layout of first 8 bytes: @@ -292,9 +303,9 @@ class QuickSelectSketch<S extends Summary> extends Sketch<S> { if (count_ > 0) { summariesBytes = new byte[count_][]; int i = 0; - for (int j = 0; j < summaries_.length; j++) { - if (summaries_[j] != null) { - summariesBytes[i] = summaries_[j].toByteArray(); + for (int j = 0; j < summaryTable_.length; j++) { + if (summaryTable_[j] != null) { + summariesBytes[i] = summaryTable_[j].toByteArray(); summariesBytesLength += summariesBytes[i].length; i++; } @@ -313,7 +324,7 @@ class QuickSelectSketch<S extends Summary> extends Sketch<S> { sizeBytes += Float.BYTES; // samplingProbability } final boolean isThetaIncluded = isInSamplingMode() - ? theta_ < samplingProbability_ : theta_ < Long.MAX_VALUE; + ? thetaLong_ < samplingProbability_ : thetaLong_ < Long.MAX_VALUE; if (isThetaIncluded) { sizeBytes += Long.BYTES; } @@ -331,7 +342,7 @@ class QuickSelectSketch<S extends Summary> extends Sketch<S> { bytes[offset++] = (byte) ( (isBigEndian ? 1 << Flags.IS_BIG_ENDIAN.ordinal() : 0) | (isInSamplingMode() ? 1 << Flags.IS_IN_SAMPLING_MODE.ordinal() : 0) - | (isEmpty_ ? 1 << Flags.IS_EMPTY.ordinal() : 0) + | (empty_ ? 1 << Flags.IS_EMPTY.ordinal() : 0) | (count_ > 0 ? 1 << Flags.HAS_ENTRIES.ordinal() : 0) | (isThetaIncluded ? 1 << Flags.IS_THETA_INCLUDED.ordinal() : 0) ); @@ -343,7 +354,7 @@ class QuickSelectSketch<S extends Summary> extends Sketch<S> { offset += Float.BYTES; } if (isThetaIncluded) { - ByteArrayUtil.putLongLE(bytes, offset, theta_); + ByteArrayUtil.putLongLE(bytes, offset, thetaLong_); offset += Long.BYTES; } if (count_ > 0) { @@ -352,9 +363,9 @@ class QuickSelectSketch<S extends Summary> extends Sketch<S> { } if (count_ > 0) { int i = 0; - for (int j = 0; j < keys_.length; j++) { - if (summaries_[j] != null) { - ByteArrayUtil.putLongLE(bytes, offset, keys_[j]); + for (int j = 0; j < hashTable_.length; j++) { + if (summaryTable_[j] != null) { + ByteArrayUtil.putLongLE(bytes, offset, hashTable_[j]); offset += Long.BYTES; System.arraycopy(summariesBytes[i], 0, bytes, offset, summariesBytes[i].length); offset += summariesBytes[i].length; @@ -370,14 +381,14 @@ class QuickSelectSketch<S extends Summary> extends Sketch<S> { // this is a special back door insert for merging // not sufficient by itself without keeping track of theta of another sketch @SuppressWarnings("unchecked") - void merge(final long key, final S summary, final SummarySetOperations<S> summarySetOps) { - isEmpty_ = false; - if (key < theta_) { - final int index = findOrInsert(key); + void merge(final long hash, final S summary, final SummarySetOperations<S> summarySetOps) { + empty_ = false; + if ((hash > 0) && (hash < thetaLong_)) { + final int index = findOrInsert(hash); if (index < 0) { - insertSummary(~index, (S)summary.copy()); //did not find so insert + insertSummary(~index, (S)summary.copy()); //did not find, so insert } else { - insertSummary(index, summarySetOps.union(summaries_[index], summary)); + insertSummary(index, summarySetOps.union(summaryTable_[index], summary)); } rebuildIfNeeded(); } @@ -388,96 +399,102 @@ class QuickSelectSketch<S extends Summary> extends Sketch<S> { } void setThetaLong(final long theta) { - theta_ = theta; + thetaLong_ = theta; } void setEmpty(final boolean value) { - isEmpty_ = value; + empty_ = value; } SummaryFactory<S> getSummaryFactory() { return summaryFactory_; } - int findOrInsert(final long key) { - final int index = HashOperations.hashSearchOrInsert(keys_, lgCurrentCapacity_, key); + int findOrInsert(final long hash) { + final int index = HashOperations.hashSearchOrInsert(hashTable_, lgCurrentCapacity_, hash); if (index < 0) { count_++; } return index; } - S find(final long key) { - final int index = HashOperations.hashSearch(keys_, lgCurrentCapacity_, key); - if (index == -1) { return null; } - return summaries_[index]; - } + // S find(final long hash) { + // final int index = HashOperations.hashSearch(hashTable_, lgCurrentCapacity_, hash); + // if (index == -1) { return null; } + // return summaryTable_[index]; + // } boolean rebuildIfNeeded() { if (count_ < rebuildThreshold_) { return false; } - if (keys_.length > nomEntries_) { + if (hashTable_.length > nomEntries_) { updateTheta(); rebuild(); } else { - rebuild(keys_.length * (1 << lgResizeFactor_)); + rebuild(hashTable_.length * (1 << lgResizeFactor_)); } return true; } void rebuild() { - rebuild(keys_.length); + rebuild(hashTable_.length); } - void insert(final long key, final S summary) { - final int index = HashOperations.hashInsertOnly(keys_, lgCurrentCapacity_, key); + void insert(final long hash, final S summary) { + final int index = HashOperations.hashInsertOnly(hashTable_, lgCurrentCapacity_, hash); insertSummary(index, summary); count_++; - isEmpty_ = false; + empty_ = false; } private void updateTheta() { - final long[] keys = new long[count_]; + final long[] hashArr = new long[count_]; int i = 0; - for (int j = 0; j < keys_.length; j++) { - if (summaries_[j] != null) { - keys[i++] = keys_[j]; + for (int j = 0; j < hashTable_.length; j++) { + if (summaryTable_[j] != null) { + hashArr[i++] = hashTable_[j]; } } - theta_ = QuickSelect.select(keys, 0, count_ - 1, nomEntries_); + thetaLong_ = QuickSelect.select(hashArr, 0, count_ - 1, nomEntries_); } @SuppressWarnings({"unchecked"}) private void rebuild(final int newSize) { - final long[] oldKeys = keys_; - final S[] oldSummaries = summaries_; - keys_ = new long[newSize]; - summaries_ = (S[]) Array.newInstance(oldSummaries.getClass().getComponentType(), newSize); + final long[] oldHashTable = hashTable_; + final S[] oldSummaryTable = summaryTable_; + final Class<S> summaryType = (Class<S>) summaryTable_.getClass().getComponentType(); + hashTable_ = new long[newSize]; + summaryTable_ = (S[]) Array.newInstance(summaryType, newSize); lgCurrentCapacity_ = Integer.numberOfTrailingZeros(newSize); count_ = 0; - for (int i = 0; i < oldKeys.length; i++) { - if ((oldSummaries[i] != null) && (oldKeys[i] < theta_)) { - insert(oldKeys[i], oldSummaries[i]); + for (int i = 0; i < oldHashTable.length; i++) { + if ((oldSummaryTable[i] != null) && (oldHashTable[i] < thetaLong_)) { + insert(oldHashTable[i], oldSummaryTable[i]); } } setRebuildThreshold(); } private void setRebuildThreshold() { - if (keys_.length > nomEntries_) { - rebuildThreshold_ = (int) (keys_.length * REBUILD_THRESHOLD); + if (hashTable_.length > nomEntries_) { + rebuildThreshold_ = (int) (hashTable_.length * REBUILD_THRESHOLD); } else { - rebuildThreshold_ = (int) (keys_.length * RESIZE_THRESHOLD); + rebuildThreshold_ = (int) (hashTable_.length * RESIZE_THRESHOLD); } } @SuppressWarnings("unchecked") protected void insertSummary(final int index, final S summary) { - if (summaries_ == null) { - summaries_ = (S[]) Array.newInstance(summary.getClass(), keys_.length); + if (summaryTable_ == null) { + summaryTable_ = (S[]) Array.newInstance(summary.getClass(), hashTable_.length); } - summaries_[index] = summary; + summaryTable_[index] = summary; + } + + @Override + public SketchIterator<S> iterator() { + return new SketchIterator<>(hashTable_, summaryTable_); } } diff --git a/src/main/java/org/apache/datasketches/tuple/Sketch.java b/src/main/java/org/apache/datasketches/tuple/Sketch.java index 651602a..494fd82 100644 --- a/src/main/java/org/apache/datasketches/tuple/Sketch.java +++ b/src/main/java/org/apache/datasketches/tuple/Sketch.java @@ -33,10 +33,10 @@ public abstract class Sketch<S extends Summary> { protected static final byte PREAMBLE_LONGS = 1; - long[] keys_; - S[] summaries_; - long theta_; - boolean isEmpty_ = true; + //long[] hashArr_; + //S[] summaryArr_; + long thetaLong_; + boolean empty_ = true; Sketch() {} @@ -59,7 +59,7 @@ public abstract class Sketch<S extends Summary> { */ public double getUpperBound(final int numStdDev) { if (!isEstimationMode()) { return getRetainedEntries(); } - return BinomialBoundsN.getUpperBound(getRetainedEntries(), getTheta(), numStdDev, isEmpty_); + return BinomialBoundsN.getUpperBound(getRetainedEntries(), getTheta(), numStdDev, empty_); } /** @@ -72,7 +72,7 @@ public abstract class Sketch<S extends Summary> { */ public double getLowerBound(final int numStdDev) { if (!isEstimationMode()) { return getRetainedEntries(); } - return BinomialBoundsN.getLowerBound(getRetainedEntries(), getTheta(), numStdDev, isEmpty_); + return BinomialBoundsN.getLowerBound(getRetainedEntries(), getTheta(), numStdDev, empty_); } /** @@ -120,7 +120,7 @@ public abstract class Sketch<S extends Summary> { * @return true if empty. */ public boolean isEmpty() { - return isEmpty_; + return empty_; } /** @@ -129,7 +129,7 @@ public abstract class Sketch<S extends Summary> { * @return true if the sketch is in estimation mode. */ public boolean isEstimationMode() { - return ((theta_ < Long.MAX_VALUE) && !isEmpty()); + return ((thetaLong_ < Long.MAX_VALUE) && !isEmpty()); } /** @@ -142,7 +142,7 @@ public abstract class Sketch<S extends Summary> { * @return the value of theta as a double */ public double getTheta() { - return theta_ / (double) Long.MAX_VALUE; + return thetaLong_ / (double) Long.MAX_VALUE; } /** @@ -155,16 +155,14 @@ public abstract class Sketch<S extends Summary> { * Returns a SketchIterator * @return a SketchIterator */ - public SketchIterator<S> iterator() { - return new SketchIterator<>(keys_, summaries_); - } + public abstract SketchIterator<S> iterator(); /** * Returns Theta as a long * @return Theta as a long */ public long getThetaLong() { - return theta_; + return thetaLong_; } @Override diff --git a/src/main/java/org/apache/datasketches/tuple/SketchIterator.java b/src/main/java/org/apache/datasketches/tuple/SketchIterator.java index fb21c85..43ef64f 100644 --- a/src/main/java/org/apache/datasketches/tuple/SketchIterator.java +++ b/src/main/java/org/apache/datasketches/tuple/SketchIterator.java @@ -25,13 +25,13 @@ package org.apache.datasketches.tuple; */ public class SketchIterator<S extends Summary> { - private long[] keys_; - private S[] summaries_; + private long[] hashArrTbl_; //could be either hashArr or hashTable + private S[] summaryArrTbl_; //could be either summaryArr or summaryTable private int i_; - SketchIterator(final long[] keys, final S[] summaries) { - keys_ = keys; - summaries_ = summaries; + SketchIterator(final long[] hashes, final S[] summaries) { + hashArrTbl_ = hashes; + summaryArrTbl_ = summaries; i_ = -1; } @@ -42,24 +42,37 @@ public class SketchIterator<S extends Summary> { * @return true if the next element exists */ public boolean next() { - if (keys_ == null) { return false; } + if (hashArrTbl_ == null) { return false; } i_++; - while (i_ < keys_.length) { - if (keys_[i_] != 0) { return true; } + while (i_ < hashArrTbl_.length) { + if (hashArrTbl_[i_] > 0) { return true; } i_++; } return false; } /** - * Gets a key from the current entry in the sketch, which is a hash + * Gets the hash from the current entry in the sketch, which is a hash * of the original key passed to update(). The original keys are not * retained. Don't call this before calling next() for the first time * or after getting false from next(). - * @return hash key from the current entry + * @return hash from the current entry + * @deprecated Please use {@link #getHash()} */ + @Deprecated public long getKey() { - return keys_[i_]; + return hashArrTbl_[i_]; + } + + /** + * Gets the hash from the current entry in the sketch, which is a hash + * of the original key passed to update(). The original keys are not + * retained. Don't call this before calling next() for the first time + * or after getting false from next(). + * @return hash from the current entry + */ + public long getHash() { + return hashArrTbl_[i_]; } /** @@ -69,7 +82,7 @@ public class SketchIterator<S extends Summary> { * @return Summary object for the current entry (this is not a copy!) */ public S getSummary() { - return summaries_[i_]; + return summaryArrTbl_[i_]; } } diff --git a/src/main/java/org/apache/datasketches/tuple/Summary.java b/src/main/java/org/apache/datasketches/tuple/Summary.java index 8614df1..46e78a9 100644 --- a/src/main/java/org/apache/datasketches/tuple/Summary.java +++ b/src/main/java/org/apache/datasketches/tuple/Summary.java @@ -20,7 +20,7 @@ package org.apache.datasketches.tuple; /** - * Interface for user-defined Summary, which is associated with every key in a tuple sketch + * Interface for user-defined Summary, which is associated with every hash in a tuple sketch */ public interface Summary { diff --git a/src/main/java/org/apache/datasketches/tuple/SummarySetOperations.java b/src/main/java/org/apache/datasketches/tuple/SummarySetOperations.java index 354d002..eac86a1 100644 --- a/src/main/java/org/apache/datasketches/tuple/SummarySetOperations.java +++ b/src/main/java/org/apache/datasketches/tuple/SummarySetOperations.java @@ -26,7 +26,7 @@ package org.apache.datasketches.tuple; public interface SummarySetOperations<S extends Summary> { /** - * This is called by the union operator when both sketches have the same key. + * This is called by the union operator when both sketches have the same hash value. * * <p><b>Caution:</b> Do not modify the input Summary objects. Also do not return them directly, * unless they are immutable (most Summary objects are not). For mutable Summary objects, it is @@ -40,7 +40,7 @@ public interface SummarySetOperations<S extends Summary> { public S union(S a, S b); /** - * This is called by the intersection operator when both sketches have the same key. + * This is called by the intersection operator when both sketches have the same hash value. * * <p><b>Caution:</b> Do not modify the input Summary objects. Also do not return them directly, * unless they are immutable (most Summary objects are not). For mutable Summary objects, it is diff --git a/src/main/java/org/apache/datasketches/tuple/Union.java b/src/main/java/org/apache/datasketches/tuple/Union.java index f609bf2..884faff 100644 --- a/src/main/java/org/apache/datasketches/tuple/Union.java +++ b/src/main/java/org/apache/datasketches/tuple/Union.java @@ -36,7 +36,7 @@ import org.apache.datasketches.SketchesArgumentException; */ public class Union<S extends Summary> { private final SummarySetOperations<S> summarySetOps_; - private QuickSelectSketch<S> sketch_; + private QuickSelectSketch<S> qsk_; private long thetaLong_; // need to maintain outside of the sketch private boolean empty_; @@ -56,8 +56,8 @@ public class Union<S extends Summary> { */ public Union(final int nomEntries, final SummarySetOperations<S> summarySetOps) { summarySetOps_ = summarySetOps; - sketch_ = new QuickSelectSketch<>(nomEntries, null); - thetaLong_ = sketch_.getThetaLong(); + qsk_ = new QuickSelectSketch<>(nomEntries, null); + thetaLong_ = qsk_.getThetaLong(); empty_ = true; } @@ -69,18 +69,18 @@ public class Union<S extends Summary> { public void update(final Sketch<S> sketchIn) { if ((sketchIn == null) || sketchIn.isEmpty()) { return; } empty_ = false; - if (sketchIn.theta_ < thetaLong_) { thetaLong_ = sketchIn.theta_; } + if (sketchIn.thetaLong_ < thetaLong_) { thetaLong_ = sketchIn.thetaLong_; } final SketchIterator<S> it = sketchIn.iterator(); while (it.next()) { - sketch_.merge(it.getKey(), it.getSummary(), summarySetOps_); + qsk_.merge(it.getHash(), it.getSummary(), summarySetOps_); } - if (sketch_.theta_ < thetaLong_) { - thetaLong_ = sketch_.theta_; + if (qsk_.thetaLong_ < thetaLong_) { + thetaLong_ = qsk_.thetaLong_; } } /** - * Updates the internal set by combining entries using the hash keys from the Theta Sketch and + * Updates the internal set by combining entries using the hashes from the Theta Sketch and * summary values from the given summary and rules from the summarySetOps defined by the * Union constructor. * @param sketchIn the given Theta Sketch input. If null or empty, it is ignored. @@ -97,10 +97,10 @@ public class Union<S extends Summary> { if (thetaIn < thetaLong_) { thetaLong_ = thetaIn; } final org.apache.datasketches.theta.HashIterator it = sketchIn.iterator(); while (it.next()) { - sketch_.merge(it.get(), (S)summary.copy(), summarySetOps_); + qsk_.merge(it.get(), (S)summary.copy(), summarySetOps_); } - if (sketch_.theta_ < thetaLong_) { - thetaLong_ = sketch_.theta_; + if (qsk_.thetaLong_ < thetaLong_) { + thetaLong_ = qsk_.thetaLong_; } } @@ -111,53 +111,56 @@ public class Union<S extends Summary> { @SuppressWarnings("unchecked") public CompactSketch<S> getResult() { if (empty_) { - return sketch_.compact(); + return qsk_.compact(); } - if ((thetaLong_ >= sketch_.theta_) && (sketch_.getRetainedEntries() <= sketch_.getNominalEntries())) { - return sketch_.compact(); + if ((thetaLong_ >= qsk_.thetaLong_) && (qsk_.getRetainedEntries() <= qsk_.getNominalEntries())) { + return qsk_.compact(); } - long theta = min(thetaLong_, sketch_.theta_); + long theta = min(thetaLong_, qsk_.thetaLong_); - int num = 0; + int numHashes = 0; { - final SketchIterator<S> it = sketch_.iterator(); + final SketchIterator<S> it = qsk_.iterator(); while (it.next()) { - if (it.getKey() < theta) { num++; } + if (it.getHash() < theta) { numHashes++; } } } - if (num == 0) { + if (numHashes == 0) { return new CompactSketch<>(null, null, theta, empty_); } - if (num > sketch_.getNominalEntries()) { - final long[] keys = new long[num]; // temporary since the order will be destroyed by quick select - final SketchIterator<S> it = sketch_.iterator(); + if (numHashes > qsk_.getNominalEntries()) { + final long[] hashArr = new long[numHashes]; // temporary, order will be destroyed by quick select + final SketchIterator<S> it = qsk_.iterator(); int i = 0; while (it.next()) { - if (it.getKey() < theta) { keys[i++] = it.getKey(); } + final long hash = it.getHash(); + if (hash < theta) { hashArr[i++] = hash; } } - theta = QuickSelect.select(keys, 0, num - 1, sketch_.getNominalEntries()); - num = sketch_.getNominalEntries(); + theta = QuickSelect.select(hashArr, 0, numHashes - 1, qsk_.getNominalEntries()); + numHashes = qsk_.getNominalEntries(); } - final long[] keys = new long[num]; - final S[] summaries = (S[]) Array.newInstance(sketch_.summaries_.getClass().getComponentType(), num); - final SketchIterator<S> it = sketch_.iterator(); + final Class<S> summaryType = (Class<S>) qsk_.getSummaryTable().getClass().getComponentType(); + final long[] hashArr = new long[numHashes]; + final S[] summaries = (S[]) Array.newInstance(summaryType, numHashes); + final SketchIterator<S> it = qsk_.iterator(); int i = 0; while (it.next()) { - if (it.getKey() < theta) { - keys[i] = it.getKey(); + final long hash = it.getHash(); + if (hash < theta) { + hashArr[i] = hash; summaries[i] = (S) it.getSummary().copy(); i++; } } - return new CompactSketch<>(keys, summaries, theta, empty_); + return new CompactSketch<>(hashArr, summaries, theta, empty_); } /** * Resets the internal set to the initial state, which represents an empty set */ public void reset() { - sketch_.reset(); - thetaLong_ = sketch_.getThetaLong(); + qsk_.reset(); + thetaLong_ = qsk_.getThetaLong(); empty_ = true; } } diff --git a/src/main/java/org/apache/datasketches/tuple/UpdatableSketch.java b/src/main/java/org/apache/datasketches/tuple/UpdatableSketch.java index fd37888..b6aa87f 100644 --- a/src/main/java/org/apache/datasketches/tuple/UpdatableSketch.java +++ b/src/main/java/org/apache/datasketches/tuple/UpdatableSketch.java @@ -140,15 +140,15 @@ public class UpdatableSketch<U, S extends UpdatableSummary<U>> extends QuickSele insertOrIgnore(MurmurHash3.hash(key, DEFAULT_UPDATE_SEED)[0] >>> 1, value); } - private void insertOrIgnore(final long key, final U value) { + void insertOrIgnore(final long hash, final U value) { setEmpty(false); - if (key >= getThetaLong()) { return; } - int index = findOrInsert(key); + if (hash >= getThetaLong()) { return; } + int index = findOrInsert(hash); if (index < 0) { index = ~index; insertSummary(index, getSummaryFactory().newSummary()); } - summaries_[index].update(value); + summaryTable_[index].update(value); rebuildIfNeeded(); } diff --git a/src/main/java/org/apache/datasketches/tuple/adouble/DoubleSummarySetOperations.java b/src/main/java/org/apache/datasketches/tuple/adouble/DoubleSummarySetOperations.java index 6d0aa61..961a658 100644 --- a/src/main/java/org/apache/datasketches/tuple/adouble/DoubleSummarySetOperations.java +++ b/src/main/java/org/apache/datasketches/tuple/adouble/DoubleSummarySetOperations.java @@ -32,7 +32,7 @@ public final class DoubleSummarySetOperations implements SummarySetOperations<Do /** * Intersection is not well defined or even meaningful between numeric values. - * Nevertheless, this can be defined to be a different type of aggregation for intersecting keys. + * Nevertheless, this can be defined to be a different type of aggregation for intersecting hashes. */ private final Mode intersectionSummaryMode_; diff --git a/src/main/java/org/apache/datasketches/tuple/aninteger/IntegerSummarySetOperations.java b/src/main/java/org/apache/datasketches/tuple/aninteger/IntegerSummarySetOperations.java index 7132a22..351bb3a 100644 --- a/src/main/java/org/apache/datasketches/tuple/aninteger/IntegerSummarySetOperations.java +++ b/src/main/java/org/apache/datasketches/tuple/aninteger/IntegerSummarySetOperations.java @@ -34,7 +34,7 @@ public class IntegerSummarySetOperations implements SummarySetOperations<Integer /** * Intersection is not well defined or even meaningful between numeric values. - * Nevertheless, this can be defined to be a different type of aggregation for intersecting keys. + * Nevertheless, this can be defined to be a different type of aggregation for intersecting hashes. */ private final Mode intersectionSummaryMode_; diff --git a/src/test/java/org/apache/datasketches/tuple/adouble/AdoubleIntersectionTest.java b/src/test/java/org/apache/datasketches/tuple/adouble/AdoubleIntersectionTest.java index 4115e6f..25359ca 100644 --- a/src/test/java/org/apache/datasketches/tuple/adouble/AdoubleIntersectionTest.java +++ b/src/test/java/org/apache/datasketches/tuple/adouble/AdoubleIntersectionTest.java @@ -110,6 +110,8 @@ public class AdoubleIntersectionTest { Assert.assertEquals(result.getUpperBound(1), 1.0); SketchIterator<DoubleSummary> it = result.iterator(); Assert.assertTrue(it.next()); + Assert.assertTrue(it.getHash() > 0); + Assert.assertTrue(it.getKey() > 0); Assert.assertEquals(it.getSummary().getValue(), 4.0); Assert.assertFalse(it.next()); --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
