beltrachi / js-mst Goto Github PK

The intention of this code is to proove or test the speed/performance
of search trees. In this case, the keys are strings.

My intention is to use it in an autocomplete input field but not asking to
the server every time.

There have been 2 different aproaches:

 * BST: binary search tree
  Has demonstrated a low performance, not so much in retrieve as in insertion.
  You can pass the tests of BST if you want to compare.
  
  In a first implementation of BST, we detected that the creation of the nodes as 
  prototype Objects was being expensive, so the nodes were changed to hashes "{}".
  
  This reduced the cost of creating nodes to a half.
 
 * MST: m-ary search tree
  The reason to try that was to reduce the navigation cost. When we are looking
  for a character in the position p, we must navigate through the neighbours till
  find the node of that char.
  In the mst, each node has a hash that points to the node of that char. This 
  implementation is suposed to be faster as a hash hit is implemented in machine
  code in the browser, so should be faster than a script code.
  
The results have shown that mst is better.

Inserting 80k words in the bst costs 7 seconds.
Inserting 80k words in the mst costs 3 seconds.
  
  This tests were taken in a FF 3.0.5
  (Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.0.5) 
    Gecko/2008121621 Ubuntu/8.04 (hardy) Firefox/3.0.5)
  The computer has a Intel Core 2 Duo T5550
  
The tests on Internet Explorer 6 were done in a virtualized installation
on the same machine as FF3. Some code adaptions were made.
The results were really slow. Possibly afected by the virtualization.

For instance:
  Adding 8k words (not 80k) in the mst cost 48 seconds. See that its a tenth of 
  the size of the test on FF and the results are really worse. 
  Pending a test on a non virtualized environment.

=== Giving a chance to Google Closure Compiler

Recently Google has released a javascript suite which includes a javascript 
compiler which reduces the code and rewrites the code reducing the size and doing
some code optimizations.

URL: http://code.google.com/closure/

Applying the compiler on the MST source needed some rewritting but it finally passed
the tests.

The results have been disapointing as has not been any important performance 
improvement even aplying the advanced optimizations.

Probably the code cannot be optimized any more and the time spent is what it needs
to do the work expected.