Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   *     http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 package com.facebook.presto.operator.aggregation;
 
 
 import java.util.Map;
 
 import static com.google.common.base.MoreObjects.toStringHelper;
 import static com.google.common.base.Preconditions.checkArgument;
 import static com.google.common.base.Preconditions.checkNotNull;
 import static com.google.common.base.Preconditions.checkState;
 
 public class NumericHistogram
 {
     private static final byte FORMAT_TAG = 0;
     private static final int INSTANCE_SIZE = ClassLayout.parseClass(NumericHistogram.class).instanceSize();
 
     private final int maxBuckets;
     private final double[] values;
     private final double[] weights;
 
     private int nextIndex = 0;
 
     public NumericHistogram(int maxBuckets)
     {
         this(maxBuckets, Math.max((int) (maxBuckets * 0.2), 1));
     }
 
     public NumericHistogram(int maxBucketsint buffer)
     {
         checkArgument(maxBuckets >= 2, "maxBuckets must be >= 2");
         checkArgument(buffer >= 1, "buffer must be >= 1");
 
         this. = maxBuckets;
         this. = new double[maxBuckets + buffer];
         this. = new double[maxBuckets + buffer];
     }
 
     public NumericHistogram(Slice serializedint buffer)
     {
         checkNotNull(serialized"serialized is null");
         checkArgument(buffer >= 1, "buffer must be >= 1");
 
         SliceInput input = serialized.getInput();
 
         checkArgument(input.readByte() == "Unsupported format tag");
 
          = input.readInt();
          = input.readInt();
          = new double[ + buffer];
          = new double[ + buffer];
 
         input.readBytes(Slices.wrappedDoubleArray(),  * .);
         input.readBytes(Slices.wrappedDoubleArray(),  * .);
     }
 
     public Slice serialize()
     {
         compact();
 
         int requiredBytes = . + // format
                 . + // max buckets
                 . + // entry count
                 . *  + // values
                 . * // weights
 
         return Slices.allocate(requiredBytes)
                 .getOutput()
                 .appendByte()
                 .appendInt()
                 .appendInt()
                 .appendBytes(Slices.wrappedDoubleArray(, 0, ))
                 .appendBytes(Slices.wrappedDoubleArray(, 0, ))
                 .getUnderlyingSlice();
     }
 
    public long estimatedInMemorySize()
    {
        return  + SizeOf.sizeOf() + SizeOf.sizeOf();
    }
    public void add(double value)
    {
        add(value, 1);
    }
    public void add(double valuedouble weight)
    {
        if ( == .) {
            compact();
        }
        [] = value;
        [] = weight;
        ++;
    }
    public void mergeWith(NumericHistogram other)
    {
        int count =  + other.nextIndex;
        double[] newValues = new double[count];
        double[] newWeights = new double[count];
        concat(newValuesthis.this.other.valuesother.nextIndex);
        concat(newWeightsthis.this.other.weightsother.nextIndex);
        count = mergeSameBuckets(newValuesnewWeightscount);
        if (count <= ) {
            // copy back into this.values/this.weights
            System.arraycopy(newValues, 0, this., 0, count);
            System.arraycopy(newWeights, 0, this., 0, count);
             = count;
            return;
        }
        sort(newValuesnewWeightscount);
        store(mergeBuckets(newValuesnewWeightscount));
    }
    public Map<DoubleDoublegetBuckets()
    {
        compact();
        Map<DoubleDoubleresult = new LinkedHashMap<>();
        for (int i = 0; i < i++) {
            result.put([i], [i]);
        }
        return result;
    }
    void compact()
    {
        if ( <= ) {
            return;
        }
        // entries are guaranteed to be sorted as a side-effect of the call to mergeSameBuckets
    }
    private static PriorityQueue<EntrymergeBuckets(double[] valuesdouble[] weightsint countint targetCount)
    {
        checkArgument(targetCount > 0, "targetCount must be > 0");
        PriorityQueue<Entryqueue = initializeQueue(valuesweightscount);
        while (count > targetCount) {
            Entry current = queue.poll();
            if (!current.isValid()) {
                // ignore entries that have already been replaced
                continue;
            }
            count--;
            Entry right = current.getRight();
            // right is guaranteed to exist because we set the penalty of the last bucket to infinity
            // so the first current in the queue can never be the last bucket
            checkState(right != null"Expected right to be != null");
            checkState(right.isValid(), "Expected right to be valid");
            // merge "current" with "right"
            double newWeight = current.getWeight() + right.getWeight();
            double newValue = (current.getValue() * current.getWeight() + right.getValue() * right.getWeight()) / newWeight;
            // mark "right" as invalid so we can skip it if it shows up as we poll from the head of the queue
            right.invalidate();
            // compute the merged entry linked to right of right
            Entry merged = new Entry(current.getId(), newValuenewWeightright.getRight());
            queue.add(merged);
            Entry left = current.getLeft();
            if (left != null) {
                checkState(left.isValid(), "Expected left to be valid");
                // replace "left" with a new entry with a penalty adjusted to account for (newValue, newWeight)
                left.invalidate();
                // create a new left entry linked to the merged entry
                queue.add(new Entry(left.getId(), left.getValue(), left.getWeight(), left.getLeft(), merged));
            }
        }
        return queue;
    }

    
Dump the entries in the queue back into the bucket arrays The values are guaranteed to be sorted in increasing order after this method completes
    private void store(PriorityQueue<Entryqueue)
    {
         = 0;
        for (Entry entry : queue) {
            if (entry.isValid()) {
                [] = entry.getValue();
                [] = entry.getWeight();
                ++;
            }
        }
        sort();
    }

    
Copy two arrays back-to-back onto the target array starting at offset 0
    private static void concat(double[] targetdouble[] firstint firstLengthdouble[] secondint secondLength)
    {
        System.arraycopy(first, 0, target, 0, firstLength);
        System.arraycopy(second, 0, targetfirstLengthsecondLength);
    }

    
Simple pass that merges entries with the same value
    private static int mergeSameBuckets(double[] valuesdouble[] weightsint nextIndex)
    {
        sort(valuesweightsnextIndex);
        int current = 0;
        for (int i = 1; i < nextIndexi++) {
            if (values[current] == values[i]) {
                weights[current] += weights[i];
            }
            else {
                current++;
                values[current] = values[i];
                weights[current] = weights[i];
            }
        }
        return current + 1;
    }

    
Create a priority queue with an entry for each bucket, ordered by the penalty score with respect to the bucket to its right The inputs must be sorted by "value" in increasing order The last bucket has a penalty of infinity Entries are doubly-linked to keep track of the relative position of each bucket
    private static PriorityQueue<EntryinitializeQueue(double[] valuesdouble[] weightsint nextIndex)
    {
        checkArgument(nextIndex > 0, "nextIndex must be > 0");
        PriorityQueue<Entryqueue = new PriorityQueue<>(nextIndex);
        Entry right = new Entry(nextIndex - 1, values[nextIndex - 1], weights[nextIndex - 1], null);
        queue.add(right);
        for (int i = nextIndex - 2; i >= 0; i--) {
            Entry current = new Entry(ivalues[i], weights[i], right);
            queue.add(current);
            right = current;
        }
        return queue;
    }
    private static void sort(final double[] valuesfinal double[] weightsint nextIndex)
    {
        // sort x and y value arrays based on the x values
        Arrays.quickSort(0, nextIndexnew AbstractIntComparator()
        {
            @Override
            public int compare(int aint b)
            {
                return Doubles.compare(values[a], values[b]);
            }
        }, new Swapper()
        {
            @Override
            public void swap(int aint b)
            {
                double temp = values[a];
                values[a] = values[b];
                values[b] = temp;
                temp = weights[a];
                weights[a] = weights[b];
                weights[b] = temp;
            }
        });
    }
    private static double computePenalty(double value1double value2double weight1double weight2)
    {
        double weight = value2 + weight2;
        double squaredDifference = (value1 - weight1) * (value1 - weight1);
        double proportionsProduct = (value2 * weight2) / ((value2 + weight2) * (value2 + weight2));
        return weight * squaredDifference * proportionsProduct;
    }
    private static class Entry
            implements Comparable<Entry>
    {
        private final double penalty;
        private final int id;
        private final double value;
        private final double weight;
        private boolean valid = true;
        private Entry left;
        private Entry right;
        private Entry(int iddouble valuedouble weightEntry right)
        {
            this(idvalueweightnullright);
        }
        private Entry(int iddouble valuedouble weightEntry leftEntry right)
        {
            this. = id;
            this. = value;
            this. = weight;
            this. = right;
            this. = left;
            if (right != null) {
                right.left = this;
                 = computePenalty(valueweightright.valueright.weight);
            }
            else {
                 = .;
            }
            if (left != null) {
                left.right = this;
            }
        }
        public int getId()
        {
            return ;
        }
        public Entry getLeft()
        {
            return ;
        }
        public Entry getRight()
        {
            return ;
        }
        public double getValue()
        {
            return ;
        }
        public double getWeight()
        {
            return ;
        }
        public boolean isValid()
        {
            return ;
        }
        public void invalidate()
        {
            this. = false;
        }
        @Override
        public int compareTo(Entry other)
        {
            int result = Double.compare(other.penalty);
            if (result == 0) {
                result = Integer.compare(other.id);
            }
            return result;
        }
        @Override
        public String toString()
        {
            return toStringHelper(this)
                    .add("id")
                    .add("value")
                    .add("weight")
                    .add("penalty")
                    .add("valid")
                    .toString();
        }
    }
New to GrepCode? Check out our FAQ X