Segment tree implementation in JavaScript

A segment tree is a data structure in the form of a binary tree that allows to store intervals. It can sometimes be mistaken as an interval tree that has a different characteristic.

To build a segment tree the endpoints of intervals are projected to form new endpoints of elementary segments:

(1,          5)
   (2, 3)
         (4,       7)
---------------------
(1, 2, 3, 4, 5,    7)

A binary tree is then built with each leaf representing either an elementary segment or an endpoint:

Source: Wikipedia

Each interval can then be described as the sum of its sub segments. We therefore store in every node the information, if the segment it represents is part of an interval. But only if the segment of the parent of this node is not part of this certain interval. Otherwise we would create redundant data: if the segment represented by a certain node is contained in an interval, of course also the segments represented by the children of this node are contained in the interval.

Implementation in JavaScript

An implementation of the segment tree as a Node.js module can be found in this github repository: interval-query. It offers query methods to find all intervals in a certain range or at a certain point and also the calculation of all overlapping intervals in a set of intervals. Besides the tree also an alternative implementation is given in the form of a sequential algorithm that just traverses the set of intervals in search for matches. In certain cases this can be faster than building up a tree. See below for detailed analysis.

The coding is not aggressively optimized for performance: the buildTree() method as well as the query methods use recursion. Also the nodes of the tree are modeled as objects and therefore the tree is not implemented in an array. This leaves some space for optimization.

Performance analysis

First the tree has to be build up. The following diagramm shows the time required to build a tree dependent on the number of intervals.
All tests were carried out on the following machine:

Node.js (v0.6.11), Linux (3.1.9 x86_64), P8600 (Core2Duo@2.4GHz 4GB RAM)

The time to build the tree with 1000 intervals takes around 10 ms and rises linear to approx. 450 ms for 20000 intervals. For intervals with floats the distribution of intervals in the number range does not affect the time to build the tree.

Query methods

For the query methods the distribution of intervals in the number range has an impact on the performance of the tree. To measure this dependency we introduce the facter d (density) that describes the ratio between number of intervals to number range. An equal distributed set of 1000 intervals in a number range of 0 - 1000 would have the factor d = 1.


We see that for both algorithms, tree and sequential, the queries are faster for a lower density value. My current assumption is that this is more a side effect: if there is a lower number of overlapping intervals and we query for a certain point in the number range the number of hits or resulting intervals is also lower. The processing of these result amount adds to our complete processing time.
If we limit the influence of this side effect by choosing a density value of 0.01 and compare the two algorithms we get the following result:

Quering a point in a set of 1000 intervals is 3.5 times faster with the tree than with the sequential algorithm and the ratio is increasing with growing number of intervals.

Further queries

To illustrate the influence of the quality of the interval set one step further, another test was done with test data of the following characteristic: we create a set of intervals where the number range is 100 times the number of intervals and the length of the intervals is a random number between 0 - 1000. This means again the density of intervals in the number range is low: an average query on a certain point would hit approx. one interval. And this result is independent on the number of intervals in our set. Let's look at the result:

The performance of the sequential algorithm is similar to the test result with d=0.01: it degrades for larger number of intervals. The tree does not degrade at all here. Even with a test set of 20000 intervals we could run more than 60000 queries per second. How can this be explained? The costly part of the tree traversal is when we hit a node with many intervals stored in it. These intervals then have to be copied to our result array of intervals. If we have relatively small intervals (compared to the number range) and less overlapping between the intervals, then each interval can be represented by a small number of segments (nodes) in the tree and therefore the number of intervals per segment keeps on a low level.

Conclusion

The applicability of the segment tree as a data structure to store intervals depends on a number of factors:

• dynamic vs. static. The tree is a static structure. If the set of intervals is changing constantly then a dynamic data structure like the one described as sequential might be a better match.
• initial build time. The tree needs to be build up first. If multiple queries are required this delay might be compensated by an overall better query performance of the tree.
• distribution of intervals. The performance of the here presented JavaScript implementation of the segment tree highly depends on the distribution of the intervals. For small intervals with moderate overlapping the tree can outperform the sequential method by magnitudes.

References

1. Segment tree on Wikipedia
2. interval-query: segment tree implementation in JavaScript

Remove duplicate elements from an array

In this article I want to discuss three different implementations in JavaScript for the following problem: given an array of n elements of type integer, how to remove duplicate values?

Here an example of the input array:

[5, 8, 3, 3, 9, 5, 78, 8, 43, 7, 7]

1. loop & splice

In this first approach we traverse the array and compare each element with following elements. If an duplicate element is found it is removed by calling Array.splice():

var loopAndSplice = function(unordered, compFn) {
  for(var i = 0; i < unordered.length; i++) {
    for(var j = i + 1; j < unordered.length; j++) {
      var equal = (compFn !== undefined) 
                  ? compFn(unordered[i], unordered[j]) === 0 
                  : unordered[i] === unordered[j]; 
      if (equal) {
        unordered.splice(j, 1);
        j--;
      }
    }
  }
  return unordered;
}

The index of the inner for loop (j) is decremented to compare the same position again after removal of an element.

The following compare function (compFn) is used for all examples, doing a simple subtraction:

function(a, b) { return (a - b); }

2. sort & dedup

The second possibility is to sort the array with the built-in Array.sort() function and then do a single traversal to remove all adjacent duplicates.

var sortAndDeDup = function(unordered, compFn) {
  var result = [];
  var prev;
  unordered.sort(compFn).forEach(function(item) {
    var equal = (compFn !== undefined && prev !== undefined) 
                ? compFn(prev, item) === 0 : prev === item; 
    if (!equal) {
      result.push(item);
      prev = item;
    }
  });
  return result;
}

3. object dedup

Here we use property assignment to an object to remove duplicates. A property with a given name can only be added once to the same object. Therefore multiple assignments of the same property will filter out those values.

var objectDeDup = function(unordered) {
  var result = [];
  var object = {};
  unordered.forEach(function(item) {
    object[item] = null;
  });
  result = Object.keys(object);
  return result;
}

The properties of the object are assigned to the value null as we are only interested in the property names and not their values. In a next step the object is transformed to an array with the Object.keys() method.

The result array in this method is in ascending order without the need to explicitly sort it and consists of string values.

How does it perform?

The integer arrays used for these tests were created with a duplicate ratio of approx. 50%. The complete test script can be found here.

This leads to some first findings:

• loop&splice is only usable for arrays with up to ~1000 elements, it degrades badly for larger sizes
• object-dedup is 2 to 3 times faster than sort&dedup on V8, and on Firefox it outperforms the later even by a factor 3 to 6.
• V8 is around 8 times faster on sort&dedup than Firefox and and 3 to 6 times faster on object-dedup
• Firefox performs around 40% better with loop&splice than V8

Next the memory consumption was analyzed on node.js. The total heap consumption for the three methods can be seen in the next diagram:

Which does approve that everything comes with a cost: memory consumption for object-dedup can be 5 to 8 times higher than for the other methods.

How about floats?

All three algorithms can also be used with float arrays. The test arrays again contain 50% duplicate floats.

• loop&splice: Chrome is here ~45% slower than with integers. Firefox needs 30 times longer compared to integer arrays.
• sort&dedup: here it is the other way round. Firefox needs only ~28% longer than with integers. Chrome's performance degrades by a factor of 7 compared to integers (although overall faster than Firefox).
• object-dedup: again the fastest method for float arrays. Chrome needs 11 times longer than with integers and Firefox 3.7 times

Chasin' strings?

Arrays with 40 character strings were used in this test. Again with a duplicate ratio of 50%.

• Firefox shows quite similar results as with the previous tests with floats.
• Chrome's performance degrades in all three algorithms. For sort&dedup with a factor of 4 to 6 and for object-dedup we see 18-46% increase in time to process the task.
• Firefox outperforms Chrome with sort&dedup by a factor of 2 to 3.
• loop&splice degrades faster than with the previous tests

Limitations of object-dedup: values are unescaped in this algorithm which can lead to complications in the processing of strings that contain a backslash (\). In the following example a property is assigned to an object:

var obj = {};
obj['\u0041lbert'] = null;  // same as obj.Albert = null; 

That means the values '\u0041lbert' and 'Albert' would be considered as equal by the object-dedup method!
Further problems when using this method with strings can be found in this article: an object is not a hash

Summary

We have seen three different methods to remove duplicate elements from an array. loop&splice is the typical O(n²) algorithm and not recommended for arrays with more than 1000 elements. sort&dedup performs much better and is the most straightforward way to perform this task. It uses the built-in Arrays.sort() method of the JavaScript runtime which leads to good results for all type of elements on both tested browsers. object-dedup is a bit the exotic bird of the compared algorithms. It exploits object property assignment for its task which is highly optimized in modern browsers (see hidden classes for Chrome). This leads to an impressive performance that was in most of the tests at least twice as good as sort&dedup and in some cases even 9 times faster. But it comes with the cost of higher memory consumption and limitations as mentioned above when it comes to strings (escape problem). For dedicated environments like node.js object-dedup can be a solution for performance critical tasks. Further tests should evaluate efficiency and compatibility on older browsers.

Update: created a new test case at http://jsperf.com/dedup-int-array. Here a slightly optimized loop&splice method is used that yields to better results.