Skip to content

Instantly share code, notes, and snippets.

@viccherubini
Last active August 29, 2015 14:21
Show Gist options
  • Save viccherubini/ecc1167183de865f69b9 to your computer and use it in GitHub Desktop.
Save viccherubini/ecc1167183de865f69b9 to your computer and use it in GitHub Desktop.
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;
}
}
<?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));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment