testing/performance/talos/page_load_test/jss/real-binary-trees-3.html

   1 <html><head>
   2 <!-- MOZ_INSERT_CONTENT_HOOK -->
   3 <script src = runner.js></script>
   4 <script>
   5 var onlyName = 'Binary Trees', onlyNum = 8;
   6 function thisTest() {
   7
   8 /* The Great Computer Language Shootout
   9    http://shootout.alioth.debian.org/
  10    contributed by Isaac Gouy */
  11
  12 function TreeNode(left,right,item){
  13    this.left = left;
  14    this.right = right;
  15    this.item = item;
  16 }
  17
  18 TreeNode.prototype.itemCheck = function(){
  19    if (this.left==null) return this.item;
  20    else return this.item + this.left.itemCheck() - this.right.itemCheck();
  21 }
  22
  23 function bottomUpTree(item,depth){
  24    if (depth>0){
  25       return new TreeNode(
  26           bottomUpTree(2*item-1, depth-1)
  27          ,bottomUpTree(2*item, depth-1)
  28          ,item
  29       );
  30    }
  31    else {
  32       return new TreeNode(null,null,item);
  33    }
  34 }
  35
  36 startTest("real-binary-trees");
  37
  38 var ret;
  39
  40 for ( var n = 2; n <= 8; n *= 2 ) (function(n){
  41         test( "Binary Trees", n, function(){
  42                 var minDepth = 4;
  43                 var maxDepth = Math.max(minDepth + 2, n);
  44                 var stretchDepth = maxDepth + 1;
  45
  46                 var check = bottomUpTree(0,stretchDepth).itemCheck();
  47
  48                 var longLivedTree = bottomUpTree(0,maxDepth);
  49                 for (var depth=minDepth; depth<=maxDepth; depth+=2){
  50                    var iterations = 1 << (maxDepth - depth + minDepth);
  51
  52                    check = 0;
  53                    for (var i=1; i<=iterations; i++){
  54                           check += bottomUpTree(i,depth).itemCheck();
  55                           check += bottomUpTree(-i,depth).itemCheck();
  56                    }
  57                 }
  58
  59                 ret = longLivedTree.itemCheck();
  60         });
  61 })(n);
  62
  63 endTest();
  64 }
  65 </script>
  66 <body onload="thisTest()"></body></html>