You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ah...@apache.org on 2020/03/18 11:18:50 UTC

[commons-collections] 05/05: Optimise DynamicHasher iterator.

This is an automated email from the ASF dual-hosted git repository.

aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-collections.git

commit 39aef5978586b0c344daf4e84a508895722e7f49
Author: Alex Herbert <ah...@apache.org>
AuthorDate: Wed Mar 18 11:18:40 2020 +0000

    Optimise DynamicHasher iterator.
---
 .../bloomfilter/hasher/DynamicHasher.java          | 54 ++++++++++++++++------
 1 file changed, 39 insertions(+), 15 deletions(-)

diff --git a/src/main/java/org/apache/commons/collections4/bloomfilter/hasher/DynamicHasher.java b/src/main/java/org/apache/commons/collections4/bloomfilter/hasher/DynamicHasher.java
index f7aa5b6..ecdc66e 100644
--- a/src/main/java/org/apache/commons/collections4/bloomfilter/hasher/DynamicHasher.java
+++ b/src/main/java/org/apache/commons/collections4/bloomfilter/hasher/DynamicHasher.java
@@ -84,11 +84,20 @@ public class DynamicHasher implements Hasher {
 
     /**
      * The iterator of integers.
+     *
+     * <p>This assumes that the list of buffers is not empty.
      */
     private class Iterator implements PrimitiveIterator.OfInt {
-        private int buffer = 0;
-        private int funcCount = 0;
-        private final Shape shape;
+        /** The number of hash functions per item. */
+        private final int k;
+        /** The number of bits in the shape. */
+        private final int m;
+        /** The current item. */
+        private byte[] item;
+        /** The index of the next item. */
+        private int nextItem;
+        /** The count of hash functions for the current item. */
+        private int functionCount;
 
         /**
          * Constructs iterator with the specified shape.
@@ -96,32 +105,45 @@ public class DynamicHasher implements Hasher {
          * @param shape
          */
         private Iterator(final Shape shape) {
-            this.shape = shape;
+            // Assumes that shape returns non-zero positive values for hash functions and bits
+            k = shape.getNumberOfHashFunctions();
+            m = shape.getNumberOfBits();
+            // Assume non-empty
+            item = buffers.get(0);
+            nextItem = 1;
         }
 
         @Override
         public boolean hasNext() {
-            // Note: This iterator is only used when buffers.size() is not zero
-            return buffer < buffers.size() - 1 || funcCount < shape.getNumberOfHashFunctions();
+            if (functionCount != k) {
+                return true;
+            }
+            // Reached the number of hash functions for the current item.
+            // Try and advance to the next item.
+            if (nextItem != buffers.size()) {
+                item = buffers.get(nextItem++);
+                functionCount = 0;
+                return true;
+            }
+            // Finished.
+            // functionCount == shape.getNumberOfHashFunctions()
+            // nextItem == buffers.size()
+            return false;
         }
 
         @Override
         public int nextInt() {
             if (hasNext()) {
-                if (funcCount >= shape.getNumberOfHashFunctions()) {
-                    funcCount = 0;
-                    buffer++;
-                }
-                return (int) Math.floorMod(function.apply(buffers.get(buffer), funcCount++),
+                return (int) Math.floorMod(function.apply(item, functionCount++),
                     // Cast to long to workaround a bug in animal-sniffer.
-                    (long) shape.getNumberOfBits());
+                    (long) m);
             }
             throw new NoSuchElementException();
         }
     }
 
     /**
-     * An iterator of integers to use then there are no values.
+     * An iterator of integers to use when there are no values.
      */
     private static class NoValuesIterator implements PrimitiveIterator.OfInt {
         /** The singleton instance. */
@@ -145,13 +167,15 @@ public class DynamicHasher implements Hasher {
 
     /**
      * The list of byte arrays that are to be hashed.
+     * Package private for access by the iterator.
      */
-    private final List<byte[]> buffers;
+    final List<byte[]> buffers;
 
     /**
      * The function to hash the buffers.
+     * Package private for access by the iterator.
      */
-    private final HashFunction function;
+    final HashFunction function;
 
     /**
      * Constructs a DynamicHasher.