Set implementations in PHP

README.md

Set implementations in PHP

Results

N:100000, R:1000

$ /usr/bin/env php client.php -n 100000 -r 1000
testStringSetWithInArray: 3.157351 sec
testStringSetWithArrayUnique: 0.392945 sec
testStringSetWithArrayKeys: 0.083967 sec
testIntHashSet: 0.210591 sec
testStringHashSet: 0.621980 sec
testIntTreeSet: 1.922332 sec
testStringTreeSet: 3.406180 sec
testIntTreeSetX: 1.263026 sec
testStringTreeSetX: 3.201873 sec

N:100000, R:10

$ /usr/bin/env php client.php -n 10000 -r 10
testStringSetWithInArray: 0.169218 sec
testStringSetWithArrayUnique: 0.373651 sec
testStringSetWithArrayKeys: 0.079586 sec
testIntHashSet: 0.281084 sec
testStringHashSet: 0.496643 sec
testIntTreeSet: 0.580253 sec
testStringTreeSet: 0.967903 sec
testIntTreeSetX: 0.394975 sec
testStringTreeSetX: 0.750752 sec

N:10000, R:10000

$ /usr/bin/env php client.php -n 10000 -r 10000
testStringSetWithInArray: 2.145616 sec
testStringSetWithArrayUnique: 0.029357 sec
testStringSetWithArrayKeys: 0.011391 sec
testIntHashSet: 0.029540 sec
testStringHashSet: 0.073061 sec
testIntTreeSet: 0.247157 sec
testStringTreeSet: 0.436166 sec
testIntTreeSetX: 0.171811 sec
testStringTreeSetX: 0.530785 sec

BenchmarkRunner.php

<?php

class BenchmarkRunner
{
    function run($name, $func, $args)
    {
        $start = microtime(true);
        call_user_func_array($func, $args);
        printf("%s: %f sec\n", $name, microtime(true) - $start);
    }
}

BenchmarkTask.php

<?php

require_once dirname(__FILE__) . '/HashSet.php';
require_once dirname(__FILE__) . '/TreeSet.php';
require_once dirname(__FILE__) . '/TreeSetX.php';

class BenchmarkTask
{
    function testStringSetWithInArray($N, $R)
    {
        $keys = array();
        for ($i = 0; $i < $N; $i++) {
            $key = 'KEY' . mt_rand(1, $R);
            if (!in_array($key, $keys)) {
                $keys[] = $key;
            }
        }
    }

    function testStringSetWithArrayUnique($N, $R)
    {
        $seq = array();
        for ($i = 0; $i < $N; $i++) {
            $key = 'KEY' . mt_rand(1, $R);
            $seq[] = $key;
        }
        $keys = array_unique($seq);
    }

    function testStringSetWithArrayKeys($N, $R)
    {
        $map = array();
        for ($i = 0; $i < $N; $i++) {
            $key = 'KEY' . mt_rand(1, $R);
            $map[$key] = null;
        }
        $keys = array_keys($map);
    }

    function _testIntSet($set, $N, $R)
    {
        for ($i = 0; $i < $N; $i++) {
            $key = mt_rand(1, $R);
            $set->add($key);
        }
    }

    function _testStringSet($set, $N, $R)
    {
        for ($i = 0; $i < $N; $i++) {
            $key = 'KEY' . mt_rand(1, $R);
            $set->add($key);
        }
    }

    function testIntHashSet($N, $R)
    {
        $set = new HashSet();
        self::_testIntSet($set, $N, $R);
    }

    function testStringHashSet($N, $R)
    {
        $set = new HashSet();
        self::_testStringSet($set, $N, $R);
    }

    function testIntTreeSet($N, $R)
    {
        $set = new TreeSet();
        self::_testIntSet($set, $N, $R);
    }

    function testStringTreeSet($N, $R)
    {
        $set = new TreeSet(array($this, '_compareString'));
        self::_testStringSet($set, $N, $R);
    }

    function testIntTreeSetX($N, $R)
    {
        $set = new TreeSetX();
        self::_testIntSet($set, $N, $R);
    }

    function testStringTreeSetX($N, $R)
    {
        $set = new TreeSetX(array($this, '_compareString'));
        self::_testStringSet($set, $N, $R);
    }

    function _compareString($a, $b)
    {
        return strcmp($a, $b);
    }
}

client.php

<?php

require_once dirname(__FILE__) . '/BenchmarkRunner.php';
require_once dirname(__FILE__) . '/BenchmarkTask.php';

$options = getopt('n:r:');
$N = (isset($options['n'])) ? ((int) $options['n']) : 100000;
$R = (isset($options['r'])) ? ((int) $options['r']) : 1000;

$task = new BenchmarkTask();
$methods = get_class_methods($task);
foreach ($methods as $method) {
    if (!preg_match('/^test/', $method)) {
        continue;
    }
    BenchmarkRunner::run($method, array($task, $method), array($N, $R));
}

HashSet.php

<?php

class HashSet
{
    var $table = array();

    function add($value)
    {
        $h = self::hashCode($value);
        if (!isset($this->table[$h])) {
            $this->table[$h] = array();
        }
        if (!in_array($value, $this->table[$h])) {
            $this->table[$h][] = $value;
        }
    }

    function hashCode($value)
    {
        if (gettype($value) === 'integer') {
            return $value;
        }
        $h = 0;
        $str = (string) $value;
        $len = strlen($str);
        for ($i = 0; $i < $len; $i++) {
            $h = (31 * $h + ord($str[$i])) & 0xFFFF;
        }
        return $h;
    }
}

TreeSet.php

<?php

class TreeSet
{
    var $root;
    var $comparator;

    function TreeSet($comparator = null)
    {
        $this->root = new TreeSet_Node(null, null, null);
        $this->comparator = $comparator;
    }

    function add($value)
    {
        self::_add($this->root, $value);
    }

    function _add($node, $value)
    {
        if ($node->value === null) {
            $node->value = $value;
            return;
        }

        if ($this->comparator !== null) {
            $cmp = call_user_func($this->comparator, $value, $node->value);
        } else {
            $cmp = ($value < $node->value) ? -1 : (($value > $node->value) ? 1 : 0);
        }

        if ($cmp < 0) {
            if ($node->left !== null) {
                self::_add($node->left, $value);
            } else {
                $node->left = new TreeSet_Node($value, null, null);
            }
        } elseif ($cmp > 0) {
            if ($node->right !== null) {
                self::_add($node->right, $value);
            } else {
                $node->right = new TreeSet_Node($value, null, null);
            }
        } else {
            return;
        }
    }
}

class TreeSet_Node
{
    var $value;
    var $left;
    var $right;

    function TreeSet_Node($value, $left, $right)
    {
        $this->value = $value;
        $this->left = $left;
        $this->right = $right;
    }
}

TreeSetX.php

<?php

class TreeSetX
{
    var $node;
    var $comparator;

    function TreeSetX($comparator = null)
    {
        // array(value, leftNode, rightNode)
        $this->node = array(null, null, null);
        $this->comparator = $comparator;
    }

    function add($value)
    {
        self::_add($this->node, $value);
    }

    function _add(&$node, $value)
    {
        if ($node[0] === null) {
            $node[0] = $value;
            return;
        }

        if ($this->comparator !== null) {
            $cmp = call_user_func($this->comparator, $value, $node[0]);
        } else {
            $cmp = ($value < $node[0]) ? -1 : (($value > $node[0]) ? 1 : 0);
        }

        if ($cmp < 0) {
            if ($node[1] !== null) {
                self::_add($node[1], $value);
            } else {
                $node[1] = array($value, null, null);
            }
        } elseif ($cmp > 0) {
            if ($node[2] !== null) {
                self::_add($node[2], $value);
            } else {
                $node[2] = array($value, null, null);
            }
        } else {
            return;
        }
    }
}