Packages

object Canonical

The paper that introduces the exponential histogram proves that, given a positive number l, every integer s can be uniquely represented as the sum of

(l or (l + 1)) * 2i + (# from 1 to (l + 1)) 2j

for i = (0 to j - 1), given some j.

The paper calls this the "l-canonical" representation of s.

It turns out that if you follow the exponential histogram bucket-merging algorithm, you end up with the invariant that the number of buckets with size 2^i exactly matches that power of 2's coefficient in s's l-canonical representation.

Put another way - only sequences of buckets with sizes matching the l-canonical representation of some number s are valid exponential histograms.

(We use this idea in ExpHist.rebucket to take a sequence of buckets of any size and rebucket them into a sequence where the above invariant holds.)

This is huge. This means that you can implement addAll(newBuckets) by

- calculating newS = s + delta contributed by newBuckets - generating the l-canonical sequence of bucket sizes for newS - rebucketing newBuckets ++ oldBuckets into those bucket sizes

The resulting sequence of buckets is a valid exponential histogram.

Linear Supertypes
AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. Canonical
  2. AnyRef
  3. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. Protected

Value Members

  1. final def !=(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  2. final def ##: Int
    Definition Classes
    AnyRef → Any
  3. final def ==(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  4. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  5. def bucketsFromLong(s: Long, l: Int): Vector[Long]

    s

    the number to convert to l-canonical form

    l

    the "l" in l-canonical form

    returns

    vector of numbers that sum to s. Each entry is a power of 2, and the number of entries of each power of 2 matches the l-canonical representation of s. Note that:

    bucketsFromLong(s, l) == fromLong(s, k).toBuckets

    bucketsFromLong is more efficient.

  6. def clone(): AnyRef
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.CloneNotSupportedException]) @native()
  7. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  8. def equals(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef → Any
  9. def finalize(): Unit
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.Throwable])
  10. def fromLong(s: Long, l: Int): CanonicalVector

    s

    the number to convert to l-canonical form

    l

    the "l" in l-canonical form

    returns

    vector of the coefficients of 2^i in the l-canonical representation of s. For example:

    scala> Canonical.fromLong(15, 2)
res0: Vector[Int] = Vector(3, 2, 2)

    15 = (3 * 20) + (2 * 21) + (2 * 2^2) the "l" in l-canonical means that

    • all return vector entries but the last one == l or l + 1
    • 1 <= returnVector.last <= l + 1 ## L-Canonical Representation Procedure: - Find the largest j s.t. 2j <= (s + l) / (1 + l) - let s' = 2j(1 + l) - l - let diff = (s - s') is the position of s within that group. - let b = the little-endian binary rep of diff % (2^j - 1) - let ret = return vector of length j:
    (0 until j).map { i => ret(i) = b(i) + l }
ret(j) = math.floor(diff / 2^j)
  11. final def getClass(): Class[_ <: AnyRef]
    Definition Classes
    AnyRef → Any
    Annotations
    @native()
  12. def hashCode(): Int
    Definition Classes
    AnyRef → Any
    Annotations
    @native()
  13. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  14. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  15. final def notify(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native()
  16. final def notifyAll(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native()
  17. final def synchronized[T0](arg0: => T0): T0
    Definition Classes
    AnyRef
  18. def toString(): String
    Definition Classes
    AnyRef → Any
  19. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException])
  20. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException])
  21. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException]) @native()

Inherited from AnyRef

Inherited from Any

Ungrouped