brando - npm Package Compare versions

Comparing version 0.0.30 to 0.0.31

bench/parse-seq-simple-bench.js

 var log = console.log
+    , floor = Math.floor
+    , random = Math.random
     , Sequence = require( '../lib/filters/sequence' )
@@ -23,5 +25,5 @@ , test = function ( mbytes, items, range ) {
 
-        log( '\n- filling test buffer (%d MB)..', mb );
+        log( '\n- filling test buffer with %d bits values (%d MB)..', seq.ibits, mb );
 
-        for ( ; k < b.length; ++k ) b[ k ] = 0xe0 + k;
+        for ( ; k <= b.length - seq.ibytes; k += seq.ibytes ) b[ seq.wuint ]( floor( random() * ( 1 << seq.ibits ) ), k );
 
@@ -43,7 +45,5 @@ seq.once( 'feed', onFeed );
 
-test( 6, 1024 * 1024, 1024 * 1024 + 1 );
-test( 6, 1024 * 1024, 1024 * 257 );
-
+test( 8, 1024 * 1024, 1024 * 1024 + 1 );
+test( 8, 1024 * 1024, 1024 * 257 );
 test( 6, 1024 * 1024, 1024 * 360 );
-
 test( 4, 1024 * 1024, 1024 * 1024 );
@@ -50,0 +50,0 @@ test( 4, 1024 * 1024, 1024 * 256 );

lib/brando.js

@@ -5,15 +5,5 @@ /*
  * NOTE: Actually, there is no size limit for sequence with repetitions,
- * instead, the max possible size for full (FP) and partial permutations
- * (PP) is 2^(32) * 2^(2) bytes, or 16GB.
+ * instead, the max size for full (FP) and partial permutations (PP) is
+ * limited to 2^(32) * 2^(2) bytes, or 16GB.
  *
- * Partial permutations (PP) implementation uses bitmap, it increases of
- * about 1/8 the memory consumption; then PP should be used with a set of
- * values that covers less than ~7/8 of the full range, to avoid waste of
- * memory.
- * Generally, it is better to use PP, as long as the choosen set of values
- * covers no more than 2/3 of the full range; it ensures that the algorithm,
- * used for parsing and selecting values from the (real) random source, could
- * find a usable value, with a probability of at least 1/3 (33%); otherwise
- * use FP, slicing to the desired size, the resulting set, to get a PP.
- *
  * Copyright(c) 2014 Guglielmo Ferri <[e-mail]>
@@ -20,0 +10,0 @@ * MIT Licensed

lib/filters/fullperm.js

@@ -46,2 +46,3 @@ /*
 
+    // Full range permutations (FP) uses random data only for shuffling the result Buffer.
     fproto.parse = function ( data ) {
@@ -64,3 +65,3 @@ var me = this
         for ( ; me.wpos < tbytes; o += ibytes ) {
-            if ( o > l ) return me.emit( 'feed', tbytes - me.wpos );
+            if ( o > l ) break;
             data[ o ] &= cmask;
@@ -71,3 +72,6 @@ if ( ( r = data[ ruint ]( o ) ) >= range ) continue;
         }
-        return me.emit( 'fart', me.result );
+        return me.wpos < tbytes ?
+               me.emit( 'feed', tbytes - me.wpos, tbytes / o ):
+               me.emit( 'fart', me.result, tbytes / o )
+               ;
     };
@@ -74,0 +78,0 @@

lib/filters/partperm.js

@@ -81,46 +81,40 @@ /*
 
+    /*
+     * Partial permutations (PP) implementation uses also a bitmap, it increases of
+     * about 1/8 the memory consumption; then PP should never be used with a set of
+     * values that covers no more than ~7/8 of the full range, to avoid waste of memory,
+     * in this case it is better to use FP.
+     *
+     * How many bytes of random data will be consumed, depends on the ratio between items
+     * and the range selected.
+     *
+     * Generally the minimum consumption of data happens when we have range equal to a pow
+     * of 2, instead, the worst case is when the range is equal to a (pow of 2) + 1.
+     *
+     * When range = (a pow of 2):
+     * - the probability to find the 1st value is 1/items
+     * - the probability to find the k-th value is 1/(items - k)
+     *
+     * It means that, for a particular value k not already inserted/parsed, on the average,
+     * we expect (items - k) bytes for finding it. Then 1 byte for the first, 2 for the 2nd
+     * and so on.
+     * This bring us to the well known Gauss formula to sum n integers, on the worst case, to
+     * obtain all distinct values, we expect to consume:
+     *
+     * - (items/2)*(items+1) bytes, or ( items^(2) + items )/2
+     *
+     * Formula suggests to use items = radix(range) to have a 50% consumption of random data,
+     * in the worst case or probability to find a value of ~1/2:
+     *
+     * - ((radix(range))^(2) + radix(range))/2 = (range + radix(range))/2, or ~radix/2
+     *
+     * When range = (a pow of 2) + 1:
+     * - the algo cuts 7 bits from the left-most byte of parse value (see comments in sequence.js),
+     *   then the probability that the current value is in range is >~1/2. Then all probability 
+     *   results above, will be divided by 2 in the worst case.
+     *
+     * These results show that PPs have a limited use, instead we can use FPs in most cases.
+     */
     pproto.parse = function ( data ) {
         var me = this
-            , bcomp = me.bcompare
-            , brange = me.brange
-            , result = me.result
-            , tbytes = me.tbytes
-            , ibytes = me.ibytes
-            , bits = me.bits
-            , ibits = me.ibits
-            , cmask = masks[ ibits - bits ]
-            , dlen = data.length
-            , l = dlen - ibytes
-            , o = 0
-            , s = 0
-            ;
-        for ( ; me.wpos < tbytes; o += ibytes ) {
-            if ( o > l ) break;
-            data[ o ] &= cmask;
-            // log( 'masked value;', data.slice( o, o + ibytes ), brange, ~ bcomp( data, o ) ? true : false );
-            if ( ~ bcomp( data, o ) ) {
-                if ( ( o - s ) === tbytes ) {
-                    data.copy( result, me.wpos, s, o );
-                    me.wpos = tbytes;
-                    break;
-                }
-                if ( o < l ) continue;
-                data.copy( result, me.wpos, s, dlen );
-                me.wpos += dlen - s;
-                break;
-            }
-            if ( s < o ) {
-                data.copy( result, me.wpos, s, o );
-                me.wpos += o - s;
-            }
-            s = o + ibytes;
-        }
-        return me.wpos < tbytes ?
-               me.emit( 'feed', tbytes - me.wpos, tbytes / o ) :
-               me.emit( 'fart', me.result, tbytes / o )
-               ;
-    };
-
-    pproto.parse = function ( data ) {
-        var me = this
             , ruint = me.ruint
@@ -141,3 +135,3 @@ , wuint = me.wuint
         for ( ; me.wpos < tbytes; o += ibytes ) {
-            if ( o > l ) return me.emit( 'feed', tbytes - me.wpos );
+            if ( o > l ) break;
             data[ o ] &= cmask;
@@ -149,3 +143,6 @@ if ( ( ( r = data[ ruint ]( o ) ) < range ) && ~ bmap.add( r ) ) {
         }
-        return me.emit( 'fart', me.result );
+        return me.wpos < tbytes ?
+               me.emit( 'feed', tbytes - me.wpos, tbytes / o ):
+               me.emit( 'fart', me.result, tbytes / o )
+               ;
     };
@@ -152,0 +149,0 @@

package.json

 {
   "name": "brando"
-  , "version": "0.0.30"
+  , "version": "0.0.31"
   , "description": "Brando."
@@ -5,0 +5,0 @@ , "homepage": "https://github.com/rootslab/brando"

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

48152

increased by8.28%

Number of package files

24

increased by9.09%

Lines of code

950

increased by9.07%

No dependency changes