brando - npm Package Compare versions

Comparing version 0.0.31 to 0.0.32

lib/filters/partperm.js

		@@ -90,28 +90,25 @@ /*
		*
		* 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.
		* Generally the minimum consumption of data happens when we have range equal to a power of 2,
		* or if range = 2^p, algo checks for values with p bits.
		*
		* 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)
		* - the probability to find the 1st value is 1 or range/range, for 2nd is (range - 1)/range
		* - the probability to find the k-th value is (range - k + 1)/range or 1 - (k - 1)/range
		* - the probability to find the k-th value if items ~= range is 1 - (range-1)/range or ~0
		*
		* Then, to have a chance of at least 50% to find a value, in the worst case, we can set:
		*
		* - (k-1)/range = 1/2 or k = 1 + range/2
		*
		* 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:
		* So, when the items > 1 + range/2, we expect to consume more than 2 random values to find
		* an element to insert.
		*
		* The worst case is when the range is equal to a power of 2 + 1, when range = 2^(p) + 1,
		* algo checks for values with p+1 bits, but those values are in the range 0 to 2^(p + 1),
		* so the probability to find a value in the correct range is:
		*
		* - (items/2)*(items+1) bytes, or ( items^(2) + items )/2
		* (2^(p) + 1) / 2^(p + 1), or 1/2 + 2^-(p+1) ~ 1/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:
		* Then, using result from the previous case, the probability to find the k-th value, is
		* 1/2 - (k - 1)/(range*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.
		*/
		@@ -118,0 +115,0 @@ pproto.parse = function ( data ) {

package.json

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

brando - npm Package Compare versions

New alerts

Fixed alerts

Worsened metrics