Array, Hashtable or Binary Tree?

[GiantCranesInDublin]

Hi,

I am looking for the best performing solution for modifying and
iterating an object graph in JavaScript. I have outlined below a
simplified example of the object model and examples of how I will be
using this graph.


Object model:

Two objects, [BadApples] and [GoodApples] each contains a collection of
[Apple] items (500 max). [Apple] simply has an ID and a name.

Requirements:

A quick way of determining whether a certain apple exists in either
[GoodApples] or [BadApples] (by ID).

A quick way of iterating through [GoodApples] and [BadApples] in order
to update the web page.

A way of moving a certain [Apple] (by ID) between [GoodApples] and
[BadApples].


I currently have this implemented using arrays, but iterating these
arrays is expensive. Is there an implementation of a binary-tree for
JavaScript? The real-world application may contain many hundreds of
nodes, and performance is crucial.

Thanks for any advice,
Gavin

 

[Thomas 'PointedEars' Lahn]

[...]
Object model:

Two objects, [BadApples] and [GoodApples] each contains a collection of
[Apple] items (500 max). [Apple] simply has an ID and a name.

Object objects (i.e. objects that have Object as constructor) are /made/
for that:

var
badApples = {
id1: new Apple('name1'),
...
},

goodApples = {
id2: new Apple('name2'),
...
};

With the provision that IDs SHOULD NOT be names of properties inherited
from Object.

Requirements:

A quick way of determining whether a certain apple exists in either
[GoodApples] or [BadApples] (by ID).

If we assume that there are no false-value apples:

if (badApples['appleID'])
{
// this bad apple exists
}

A quick way of iterating through [GoodApples] and [BadApples] in order
to update the web page.

for (var i in badApples)
{
// With the provision that apples with IDs that are the same as
// names of properties inherited from Object that do not have
// the DontEnum flag set require a mapping from the used ID to
// an unused property name -- a leading underscore should suffice.
}

A way of moving a certain [Apple] (by ID) between [GoodApples] and
[BadApples].

// this previously determined good 'foo' apple is indeed a bad one
badApples['foo'] = goodApples['foo'];
delete goodApples['foo'];

// and vice-versa
goodApples['bar'] = badApples['bar'];
delete badApples['bar'];

I currently have this implemented using arrays, but iterating these
arrays is expensive. Is there an implementation of a binary-tree for
JavaScript?

Unless you write one, no. But IMHO a binary tree is neither necessary nor
helpful here, as you have only two subclasses of objects, in the general
sense.

The real-world application may contain many hundreds of
nodes, and performance is crucial.

There is no faster access to structured data than property accessors.


HTH

PointedEars

 

[John Bokma]

Hi,

I am looking for the best performing solution for modifying and
iterating an object graph in JavaScript. I have outlined below a
simplified example of the object model and examples of how I will be
using this graph.


Object model:

Two objects, [BadApples] and [GoodApples] each contains a collection of
[Apple] items (500 max). [Apple] simply has an ID and a name.

Requirements:

A quick way of determining whether a certain apple exists in either
[GoodApples] or [BadApples] (by ID).

A quick way of iterating through [GoodApples] and [BadApples] in order
to update the web page.

A way of moving a certain [Apple] (by ID) between [GoodApples] and
[BadApples].


I currently have this implemented using arrays, but iterating these
arrays is expensive. Is there an implementation of a binary-tree for
JavaScript? The real-world application may contain many hundreds of
nodes, and performance is crucial.

Depends on many things. Are the collections sorted? In which case you can
use binary search and go from O(n) to O( log n) in search. With 500 max,
that would be 11 steps at most, compared to 500 at most (i.e. you store a
binary tree in an array).

A hash table would outperform this: O(1) look up, but it might be that the
performance for 500 max is close to the array one.

 

[Lasse Reichstein Nielsen]

I am looking for the best performing solution for modifying and
iterating an object graph in JavaScript. I have outlined below a
simplified example of the object model and examples of how I will be
using this graph.

Object model:

Two objects, [BadApples] and [GoodApples] each contains a collection of
[Apple] items (500 max). [Apple] simply has an ID and a name.

What is the type of the "ID"? Is it a number or a string (or ...)?

Requirements:

A quick way of determining whether a certain apple exists in either
[GoodApples] or [BadApples] (by ID).

Using a simple object with the id as index (or an array if the id is a
number) for each will work in the time complexity of property lookup
on an object. Sadly, IE seems to be linear at that. It is however the
choice with the least overhead.

var a = someApple;
var isGoodApple = a.ID in goodApples;

A quick way of iterating through [GoodApples] and [BadApples] in order
to update the web page.

Again, properties of an object are easily iterated with for(...in...).

for(var i in goodApples) {
var goodApple = goodApples;
// do something
}

A way of moving a certain [Apple] (by ID) between [GoodApples] and
[BadApples].

var apple = GoodApples[ID];
BadApples[ID] = apple;
delete GoodApples[ID];

I currently have this implemented using arrays, but iterating these
arrays is expensive.

You only need to iterate when you actually need all the elements.
Then it won't get any cheaper than linear anyway.
If you are using numbers as ids (and there really is no reason
to use an Array otherwise), and the id's are not consequtive
and starting at 0, you should not count from 0 to length, but
use for(..in..) to only iterate the existing elements.

Is there an implementation of a binary-tree for
JavaScript?

Not that I know of, but I'm sure one can be build pretty easily. The
question is whether it is worth it.

The real-world application may contain many hundreds of
nodes, and performance is crucial.

Many hundreds doesn't sound like enough to worry about a complex data
structure, unless timing has shown property lookup to be too slow in a
target browser. The overhead of making ones own lookup is significant.

/L

 

[RobG]

GiantCranesInDublin wrote:

[...]
Object model:

Two objects, [BadApples] and [GoodApples] each contains a collection of
[Apple] items (500 max). [Apple] simply has an ID and a name.

Object objects (i.e. objects that have Object as constructor) are /made/
for that:

var
badApples = {
id1: new Apple('name1'),
...
},

goodApples = {
id2: new Apple('name2'),
...
};

With the provision that IDs SHOULD NOT be names of properties inherited
from Object.

Requirements:

A quick way of determining whether a certain apple exists in either
[GoodApples] or [BadApples] (by ID).

If we assume that there are no false-value apples:

if (badApples['appleID'])
{
// this bad apple exists
}

Also ;-p :

if ('appleID' in badApples)
{
// this bad apple exists
}

A quick way of iterating through [GoodApples] and [BadApples] in order
to update the web page.

for (var i in badApples)
{
// With the provision that apples with IDs that are the same as
// names of properties inherited from Object that do not have
// the DontEnum flag set require a mapping from the used ID to
// an unused property name -- a leading underscore should suffice.
}

A way of moving a certain [Apple] (by ID) between [GoodApples] and
[BadApples].

// this previously determined good 'foo' apple is indeed a bad one
badApples['foo'] = goodApples['foo'];
delete goodApples['foo'];

// and vice-versa
goodApples['bar'] = badApples['bar'];
delete badApples['bar'];

I currently have this implemented using arrays, but iterating these
arrays is expensive. Is there an implementation of a binary-tree for
JavaScript?

Unless you write one, no. But IMHO a binary tree is neither necessary nor
helpful here, as you have only two subclasses of objects, in the general
sense.

I agree. Binary trees are helpful if you have millions of items, but
for a few hundred, for..in should be fast enough. I recently did a
type-ahead thing for a thesaurus that has 5,0000 records (each has a
keyword plus comments, related terms, etc. - the data set is 300KB).

The records are sorted on keyword, then loaded into an object with a
simple alphabetic index based on the first character of each keyword.
It returns matches easily as fast you you can type even on an ancient
400MHz G3.

[...]

 

[Thomas 'PointedEars' Lahn]

Object model:

Two objects, [BadApples] and [GoodApples] each contains a collection of
[Apple] items (500 max). [Apple] simply has an ID and a name.

What is the type of the "ID"? Is it a number or a string (or ...)?

Why this question?

[...]

A way of moving a certain [Apple] (by ID) between [GoodApples] and
[BadApples].

1.
var apple = GoodApples[ID];
2.
BadApples[ID] = apple;
3.
delete GoodApples[ID];

Use this with caution if an apple is an object:

The unnecessary `apple' reference will not only slow down processing but
then also keeps memory allocated as that cannot be freed prematurely through
the GC when BadApples[ID] is "deleted" later. Keep in mind that even if
`delete' is applied on `GoodApples[ID]', `apple' retains a reference to the
object.

0. GoodApples[ID] --------> object

1. GoodApples[ID] --------> object <-------- apple

2. GoodApples[ID] --------> object <-------- apple
^
|
BadApples[ID]

3. object <-------- apple
^
|
BadApples[ID]

4. delete BadApples[ID]

object <-------- apple


PointedEars

 

[GiantCranesInDublin]

Many thanks for the replies. I have followed your advice and am seeing
great performance.

Cheers,
Gavin

 

[Lasse Reichstein Nielsen]

Object model:

Two objects, [BadApples] and [GoodApples] each contains a collection of
[Apple] items (500 max). [Apple] simply has an ID and a name.

What is the type of the "ID"? Is it a number or a string (or ...)?

Why this question?

Mostly curiosity. If the ids are 32-bit numbers, one might consider
using an array, but only if knowing an upper bound is valuable.
If they are strings, some structure other than a binary tree might
be usable, e.g. a trie. It's all about knowing ones options

[...]

A way of moving a certain [Apple] (by ID) between [GoodApples] and
[BadApples].

var apple = GoodApples[ID];

.....
Use this with caution if an apple is an object:

The unnecessary `apple' reference will not only slow down processing

Minimally, but true.

but then also keeps memory allocated as that cannot be freed
prematurely through the GC when BadApples[ID] is "deleted" later.

True, if the variable survives. However, code as the above should
not be performed in the global scope, but inside a dedicted method,
where the life time of the variable is limited (except if one
"accidentally" captures the scope by creating and storing a closure).


Still, not using an intermediate variable is at least as fast and at
least as safe, so other than reducing line length, there is no arguemnt
for the "apple" variable.

/L

 

[GiantCranesInDublin]

One last question if I may; Is it possible to get a count of the items
that have been added? Obviously Array.length is of no use here.

 

[Thomas 'PointedEars' Lahn]

One last question if I may; Is it possible to get a count of the items
that have been added? Obviously Array.length is of no use here.

I suggest you implement an add() method for your AppleCollection objects
and increase a `count' property there.

function AppleCollection()
{
this.count = 0;
this.apples = {};

for (var i = arguments.length; i--
{
this.add(arguments);
}
}

AppleCollection.prototype.add = function(id, apple)
{
if (typeof id != "undefined" && apple)
{
var hadApple = this.hasApple(id);
this.apples[id] = apple;
if (!hadApple)
{
this.count++;
}

return apple;
}

return null;
}

AppleCollection.prototype.hasApple = function(apple)
{
return !!this.apples[apple];
}

var
goodApples = new AppleCollection(
new Apple(...),
...),
badApples = new AppleCollection(
new Apple(...),
...);

badApples.add('foo', goodApples['foo']);
delete goodApples['foo'];


You could as well implement a move() method and so on. Happy coding!


PointedEars