while not null

Monday, October 3, 2011

Danny Deckchair

Originally posted 2009-12-20.

Category: Romantic Comedy
Actors: Rhys Ifans, Miranda Otto, Justine Clarke
Screenplay: Jeff Balsmeyer
Director: Jeff Balsmeyer
Year: 2003

Running Time: 1 hour 40 minutes

Rhys Ifans plays Danny Morgan, a cement man in Sydney who desparately needs his vacation. Unfortunately, his partner Trudy Dunphy, played by Justine Clarke, does not share his love for rustic camping. She would rather stay in the city and pursue her career and a more important man.

Danny Deckchair is a refreshingly light, intriguing, story of finding one's place and mate. Highly recommended, especially when feeling down.

The PG-13 rating in the U.S. is nuts. This is a PG movie.

Clockwise

Originally posted 2008-04-19.

Category: Comedy
Actors: John Cleese
Screenplay: Michael Frayn
Year: 1986

Running Time: 1 hour 36 minutes

John Cleese plays Brian Stimpson - a headmaster obsessed with punctuality. His school resembles a workcamp with principal Stimpson keeping an eye on everyone from his watch-tower.

His few vices include not paying attention to what people say and overusing the word "right", right?

This light comedy is a pleasure to watch. Not overdone. Not boring. Not irritating. Just right.

Playing for Pizza

Originally posted 2008-06-18.

Author: John Grisham

Category: Fiction

Read By: Christopher Evan Welch

I do not know much about American football, but the story of an extremely unlucky NFL player Rick Dockery is still captivating.

Playing for Cleveland Browns, Rick makes 3 mistakes in a matter of minutes, and lands unconscious in a hospital. He's fired. Browns fans want to kill him...

John Grisham likes Italy. This is his second book I listened to, that takes place mostly in Italy. He likes the food, the people, the clothes, the way of life. I like it too. It is hard not to.

Predictably Irrational - The Hidden Forces That Shape Our Decisions

Originally posted 2010-03-07.

Author: Dan Ariely
Category: Popular Science
Read By: Simon Jones
CDs: 6

Refreshing, if not groundbreaking, look at human behavior in the context of economics.
Dan Ariely writes about results of real, clever and meaningful research experiments in a very approachable way.
Even though this is a truly scientific book, it has very practical implications for regular consumers like you and me. Make sure you read it before making your next big purchase. An eye opener.

For all chapter overviews go to wikipedia: Predictably Irrational

Highly recommended for adults. Contains details of reasearch about human sexuality that may not be appropriate for young readers.

Huffman's compression algorithm implemented in JavaScript

Originally published 2009-06-02, on tom-ash.net

The other night I have implemented Huffman's compression algorithm in JavaScript. Here is a wiki link describing what Huffman coding is:
Huffman coding
Here is my JavaScript implementation:

<html>
<head>
<title>Huffman's compression algorithm implemented in JavaScript

by Tomasz Andraszek</title>

<script type="text/javascript">
   
function compress() {
 var input = document.getElementById("input").value;
 document.getElementById("inputlength").innerHTML =input.length*8;
 var probabilities = getProbabilities(input);
 var codes = getCodes(probabilities);
 var output = compressHuffman(input, codes);
 
 var temp = "";
 for (var elem in probabilities) {
   temp += elem + " = " + probabilities[elem] + "<br/>";
 }
 document.getElementById("probabilities").innerHTML = temp;
 
 temp = "";
 for (var elem in codes) {
   temp += elem + " = " + codes[elem] + "<br/>";
 }
 document.getElementById("codes").innerHTML = temp;
 document.getElementById("output").innerHTML = output;
 document.getElementById("outputlength").innerHTML =output.length;
}

function sortNumberAsc(a, b) {
 return a[1] - b[1];
}

function getCodes(prob) {
 var tree = new Array();
 var secondTree = new Array();
 
 this.getNext = function() {
 if (tree.length > 0 && secondTree.length > 0 
               && tree[0].prob < secondTree[0].prob)
   return tree.shift();
 
 if (tree.length > 0 && secondTree.length > 0 
                && tree[0].prob > secondTree[0].prob)
   return secondTree.shift();
 
 if (tree.length > 0)
   return tree.shift();
 
 return secondTree.shift();
 }
 var sortedProb = new Array();
 var codes = new Array();
 
 var x = 0;
 for (var elem in prob) {
   sortedProb[x] = new Array(elem, prob[elem]);
   x = x + 1;
 }
 
 sortedProb = sortedProb.sort(sortNumberAsc);
 x = 0;
 
 for (var elem in sortedProb) {
   tree[x] = new node();
   tree[x].prob = sortedProb[elem][1];
   tree[x].value = sortedProb[elem][0];
   x = x + 1;
 }
 while (tree.length + secondTree.length > 1) {
  var left = getNext();
  var right = getNext();
  var newnode = new node();
  newnode.left = left;
  newnode.right = right;
  newnode.prob = left.prob + right.prob;
  newnode.left.parent = newnode;
  newnode.right.parent = newnode;
  secondTree.push(newnode);
 }

 var currentnode = secondTree[0];
 var code = "";
 while (currentnode) {
  if (currentnode.value) {
   codes[currentnode.value] = code;
   code = code.substr(0, code.length - 1);
   currentnode.visited = true;
   currentnode = currentnode.parent;
  }
  else if (!currentnode.left.visited) {
   currentnode = currentnode.left;
   code += "0";
  }
  else if (!currentnode.right.visited) {
   currentnode = currentnode.right;
   code += "1";
  }
  else {
   currentnode.visited = true;
   currentnode = currentnode.parent;
   code = code.substr(0, code.length - 1);
  }
 }
 return codes;
}

function node() {
  this.left = null;
  this.right = null;
  this.prob = null;
  this.value = null;
  this.code = "";
  this.parent = null;
  this.visited = false;
}

function compressHuffman(input, codes) {
  var output = input.split("");
  for (var elem in output) {
   output[elem] = codes[output[elem]];
  }
  return output.join("");
}

function getProbabilities(input) {
  var prob = new Array();
  var x = 0;
  var len = input.length;
  while (x < len) {
   var chr = input.charAt(x);
   if (prob[chr]) {
    prob[chr] = prob[chr] + 1;
   }
   else {
    prob[chr] = 1;
   }
   x++;
  }

  for (var elem in prob) {
   prob[elem] = prob[elem] / len;
  }
  return prob;
}
</script>

</head>
<body>
Type in the text to compress here:<br />
<textarea id="input" rows="5" cols="80">aaabcc</textarea><br/>
<input type="button" onclick="compress()" value="Compress" /><br/>
Text's length (8 bits per character): <span id="inputlength"></span><br/>
Probabilities of all distinct characters in the text:<br />

<span id="probabilities"></span><br/>
Binary codes assigned to characters: <br /><span id="codes"></span><br/>
Binary output: <span id="output"></span><br/>
Output's length in bits: <span id="outputlength"></span><br/>
</body>
</html>

Enums in JavaScript

Originally published 2008-12-27, on tom-ash.net

JavaScript does not support enums like these in C#:

        enum SpriteSize
        {
            Small = 100,
            Big = 200
        }
        
        void Render(SpriteSize spriteSize)
        {
            if (spriteSize == SpriteSize.Small)
            {
            // TODO: implement
            }
        }

The simplest way to get enum functionality in JavaScript is to create a variable using JSON:

<script type="text/javascript">
            var SpriteSize = 
            {
                Small: 100,
                Big: 200
            }

            function Render(spriteSize)
            {
                if (spriteSize == SpriteSize.Small)
                {
                // TODO: implement
                }
            }
</script>

Hunting Deadlocks - SQL Server 2000

One of a series of posts from andraszek.net posted originally between 2006 and 2010.

A typical scenario for a deadlock is described in Books Online: two procedures which try to use two tables in a different order, block each other after aquiring a lock to the first table.

I will describe here a different scenario: one procedure using one table. How can a deadlock occurr in such a case? Let's see.

It all starts with SQL Error 1205: Your transaction (process ID #99) was deadlocked on lock resources with another process and has been chosen as the deadlock victim. Rerun your transaction.

First, let's enable SQL Server Trace 1204 flag. You must be in sysadmin server role to execute the following statement:

DBCC TRACEON (1204)

The trace, by default is written to this file:
C:\Program Files\Microsoft SQL Server\MSSQL\LOG\ERRORLOG

Here we find details of our deadlock:

Deadlock encountered .... Printing deadlock information
2004-10-15 19:14:04.64 spid4
2004-10-15 19:14:04.64 spid4 Wait-for graph
2004-10-15 19:14:04.64 spid4
2004-10-15 19:14:04.64 spid4 Node:1
2004-10-15 19:14:04.64 spid4 KEY: 10:1266375687:3 (dd0025eb9a53) CleanCnt:1 
Mode: S Flags: 0x0
2004-10-15 19:14:04.64 spid4 Grant List 1::
2004-10-15 19:14:04.64 spid4 Owner:0x655ac660 Mode: S Flg:0x0 Ref:1 
Life:00000000 SPID:75 ECID:0
2004-10-15 19:14:04.64 spid4 SPID: 75 ECID: 0 Statement Type: SELECT Line #: 29
2004-10-15 19:14:04.64 spid4 Input Buf: RPC Event: InvoiceUpdate;1
2004-10-15 19:14:04.64 spid4 Requested By:
2004-10-15 19:14:04.64 spid4 ResType:LockOwner Stype:'OR' Mode: X SPID:64 
ECID:0 Ec:(0x63B3F580) Value:0x57648ee0 Cost:(0/3C)
2004-10-15 19:14:04.64 spid4
2004-10-15 19:14:04.64 spid4 Node:2
2004-10-15 19:14:04.64 spid4 KEY: 16:1153035489:1 (d1003ffe1113) CleanCnt:1 
Mode: X Flags: 0x0
2004-10-15 19:14:04.64 spid4 Grant List 0::
2004-10-15 19:14:04.64 spid4 Owner:0x42bc2140 Mode: X Flg:0x0 Ref:0 
Life:02000000 SPID:64 ECID:0
2004-10-15 19:14:04.64 spid4 SPID: 64 ECID: 0 Statement Type: UPDATE Line #: 
679
2004-10-15 19:14:04.64 spid4 Input Buf: RPC Event: InvoiceUpdate;1
2004-10-15 19:14:04.64 spid4 Requested By:
2004-10-15 19:14:04.64 spid4 ResType:LockOwner Stype:'OR' Mode: S SPID:75 
ECID:0 Ec:(0x61D09580) Value:0x655ad200 Cost:(0/0)
2004-10-15 19:14:04.64 spid4 Victim Resource Owner:
2004-10-15 19:14:04.64 spid4 ResType:LockOwner Stype:'OR' Mode: S SPID:75 
ECID:0 Ec:(0x61D09580) Value:0x655ad200 Cost:(0/0)

You can notice that both nodes executed procedure InvoiceUpdate. From the KEY you can decipher the object they fought for:
10 is database id,
1266375687 is table id,
and 1 or 3 are index ids.

Find name of the database:

SELECT [name] FROM master.dbo.sysdatabases WHERE dbid = 10

Find name of the table:

SELECT OBJECT_NAME('1266375687')

This may be a temporary object, for example a cursor, which will not exist when we check later. In this case find name of the table from the stored procedure: just look for line # provided by trace.

There is a little trap here: if your procedure calls another procedure, then the deadlock may actually occurr in the subprocedure and the line number applies to the subprocedure.

Find ids and names of the indexes:

SELECT indid, [name] FROM sysindexes WHERE id = OBJECT_ID('Invoice')

Find keys of the indexes:

sp_helpindex 'Invoice'

Both instances aquire a shared lock to a range of rows, and then one of them tries to escalate that lock to exclusive to update a row, but cannot, because the other keeps it and also tries to escalate to exclusive to update another row.

The problem is that the initial shared lock was too wide. The index used was not optimal for the SELECT statement and too many rows were locked.

The solution is to create another index which matches exactly the WHERE clause used in the SELECT. This of course does not solve the problem if there are two or more processes that try to execute this procedure with the same parameters. The application has to be designed in a way that processes operate on different sets of data.