Histogram.php

Histogram.php

<?php

class Histogram
{

    /** @var array */
    private $buckets = [];

    /** @var integer */
    private $count = 0;

    /** @const integer */
    const WIDTH = 100;

    public function __construct()
    {
    }

    /**
     * Returns the number of elements in the bucket
     * of the calculated percentile. For example,
     * if the values:
     *   12, 15, 167, 198, 206, 267, 344, 567, 456,
     *   702, 799, 801, and 941
     * were added to the histogram, this method would
     * return the following counts at the specified percentiles:
     *   10th - 2
     *   50th - 1
     *   60th - 1
     *   75th - 2
     *   90th - 1
     *   99.9th - 1
     *
     * @param float $percent
     * @return integer
     */
    public function computePercentile($percent)
    {
        $percentile = 0;

        if ($this->count > 0) {
            $index = (int)ceil(($percent / self::WIDTH) * $this->count);

            // Create an O(1) searchable hash in memory.
            $percentile = array_values($this->buckets)[$index-1];
        }

        return $percentile;
    }

    /**
     * Adds a value to the histogram buckets.
     *
     * @param float $value
     * @return boolean
     */
    public function addValue($value)
    {
        // (int) is used over floor() because floor() returns
        // a float in PHP and we want the indecies to be ints.
        $index = (int)(abs($value) / self::WIDTH);

        if (!isset($this->buckets[$index])) {
            $this->buckets[$index] = 0;
            $this->count += 1;
        }

        $this->buckets[$index] += 1;

        return true;
    }

    /**
     * Returns the count of a specific bucket, zero
     * if the bucket is empty.
     *
     * @param integer $index
     * @return integer
     */
    public function at($index)
    {
        $count = 0;

        if (isset($this->buckets[$index])) {
            $count = $this->buckets[$index];
        }

        return $count;
    }

    /**
     * Returns the total number of buckets.
     *
     * @return integer
     */
    public function count()
    {
        return $this->count;
    }

}

HistogramTest.php

<?php

include __DIR__ . '/Histogram.php';

class HistogramTest extends PHPUnit_Framework_TestCase
{

    public function testAddingValues()
    {
        $histogram = new Histogram;

        $histogram->addValue(15);
        $this->assertEquals(1, $histogram->at(0));
        $this->assertEquals(1, $histogram->count());

        $histogram->addValue(156);
        $histogram->addValue(176);
        $histogram->addValue(192);
        $this->assertEquals(3, $histogram->at(1));
        $this->assertEquals(2, $histogram->count());

        $histogram->addValue(250);
        $histogram->addValue(250);
        $this->assertEquals(2, $histogram->at(2));
        $this->assertEquals(3, $histogram->count());

        $histogram->addValue(-19);
        $this->assertEquals(2, $histogram->at(0));
        $this->assertEquals(3, $histogram->count());
    }

    public function testComputingPercentile()
    {
        $histogram = new Histogram;
        $this->assertSame(0, $histogram->computePercentile(70));

        $histogram->addValue(12);
        $histogram->addValue(15);
        $histogram->addValue(167);
        $histogram->addValue(198);
        $histogram->addValue(206);
        $histogram->addValue(267);
        $histogram->addValue(344);
        $histogram->addValue(567);
        $histogram->addValue(456);
        $histogram->addValue(702);
        $histogram->addValue(799);
        $histogram->addValue(801);
        $histogram->addValue(941);

        $this->assertEquals(2, $histogram->computePercentile(10));
        $this->assertEquals(1, $histogram->computePercentile(90));
        $this->assertEquals(1, $histogram->computePercentile(99.9));
    }

}