Skip to content

Instantly share code, notes, and snippets.

@nikic
Created April 23, 2015 12:16
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nikic/5dfad67c409dce354ea6 to your computer and use it in GitHub Desktop.
Save nikic/5dfad67c409dce354ea6 to your computer and use it in GitHub Desktop.
Tree traversal performance: yield from vs. naive implementation
<?php error_reporting(E_ALL);
class BinaryTree {
private $content, $left, $right;
public function __construct($content, BinaryTree $left = null, BinaryTree $right = null) {
$this->content = $content;
$this->left = $left;
$this->right = $right;
}
public function inOrder() : Traversable {
if ($this->left) {
yield from $this->left->inOrder();
}
yield $this->content;
if ($this->right) {
yield from $this->right->inOrder();
}
}
public function inOrderNaive() : Traversable {
if ($this->left) {
foreach ($this->left->inOrderNaive() as $elem) {
yield $elem;
}
}
yield $this->content;
if ($this->right) {
foreach ($this->right->inOrderNaive() as $elem) {
yield $elem;
}
}
}
}
function makeLinearTree(int $depth) {
if ($depth === 0) {
return null;
}
return new BinaryTree($depth, makeLinearTree($depth - 1), null);
};
$tree = makeLinearTree(10000);
// 0.01 seconds
$time = microtime(true);
foreach ($tree->inOrder() as $elem);
var_dump(microtime(true) - $time);
// 10 seconds
$time = microtime(true);
foreach ($tree->inOrderNaive() as $elem);
var_dump(microtime(true) - $time);
@kirugan
Copy link

kirugan commented Aug 27, 2015

PHP 7 ?)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment