473,837 Members | 1,480 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Array, Hashtable or Binary Tree?

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

Dec 13 '05 #1
9 6307
GiantCranesInDu blin 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
}
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
Dec 13 '05 #2
"GiantCranesInD ublin" <ga********@gma il.com> wrote:
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.
--
John MexIT: http://johnbokma.com/mexit/
personal page: http://johnbokma.com/
Experienced programmer available: http://castleamber.com/
Happy Customers: http://castleamber.com/testimonials.html
Dec 13 '05 #3
"GiantCranesInD ublin" <ga********@gma il.com> writes:
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[i];
// 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
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleD OM.html>
'Faith without judgement merely degrades the spirit divine.'
Dec 13 '05 #4
Thomas 'PointedEars' Lahn wrote:
GiantCranesInDu blin 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.

Requirement s:

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.

[...]
--
Rob
Dec 13 '05 #5
Lasse Reichstein Nielsen wrote:
"GiantCranesInD ublin" <ga********@gma il.com> writes:
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
Dec 13 '05 #6
Many thanks for the replies. I have followed your advice and am seeing
great performance.

Cheers,
Gavin

Dec 14 '05 #7
Thomas 'PointedEars' Lahn <Po*********@we b.de> writes:
Lasse Reichstein Nielsen wrote:
"GiantCranesInD ublin" <ga********@gma il.com> writes:
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
"accidental ly" 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
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleD OM.html>
'Faith without judgement merely degrades the spirit divine.'
Dec 14 '05 #8
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.

Dec 16 '05 #9
GiantCranesInDu blin wrote:
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.lengt h; i--;)
{
this.add(argume nts[i]);
}
}

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

return apple;
}

return null;
}

AppleCollection .prototype.hasA pple = 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
Dec 17 '05 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

1
3410
by: Jerry Khoo | last post by:
hello, everybody, i am kinda new here, nice to meet u all. Now, i am > cs students and are now facing difficult problems in understanding > what a binary tree is, how it works, and the algorithm to display, > arrange, find, delete the leaf node in binary tree. > > I hope that anyone with expereince in building binary tree could help > me in explaining the binary tree functions, and give a sample code of > the whole picture behind the...
4
9024
by: Tarique Jawed | last post by:
Alright I needed some help regarding a removal of a binary search tree. Yes its for a class, and yes I have tried working on it on my own, so no patronizing please. I have most of the code working, even the removal, I just don't know how to keep track of the parent, so that I can set its child to the child of the node to be removed. IE - if I had C / \ B D
2
2212
by: William Stacey [MVP] | last post by:
I am doing a dns zone type of project which has an inverted tree like you all know. test.com. (top node. value contains arraylist of all test.com records) www.test.com. (node. value contains arraylist of all matching rrs) www.sub1.test.com. .... Bind and (probably) MSs dns, use a tree structure (i.e. red-black tree, etc) to store and search this data. However, I am thinking this is not required. I could just use a hash table with...
5
2838
by: francois | last post by:
First of all I would to to apologize for resending this post again but I feel like my last post as been spoiled Here I go for my problem: Hi, I have a webservice that I am using and I would like it to return an XML serialized version of an object.
5
2693
by: Dick | last post by:
Hello, I'm trying to serialize a class with a Hashtable within: ' Class code: Imports System.Collections Class clsOptions Public countID As Integer Public persons As New Hashtable End Class
4
1738
by: g35rider | last post by:
Hi was contemplating the use of either MAP or Hashtable for keeping a cache of objects with name as the key to object. I would be searching the MAP/Array/Hashtable often now for such a small number, which would be quicker and how exactly does MAP search? Thanks Ankur
8
2080
by: Martin Pöpping | last post by:
Hello, I´ve implemented a Hashtable with Int-Keys and Double Values. Now I want to get the i-th Int-Key of my hashtable. How do I do that? I tried it like that: ICollection intKeys = myHashtable.Keys;
3
5551
by: IZZI | last post by:
This code is created to find all duplicates in a list of number by using a binary search tree implemented as an array. I want to add a function to count how many numbers in the list are duplicated but i dont know where to put it. It's really confusing. One more, i want to increase my array size to 5,000,000 but the program doesnt work.I dont know how to fix it. Plz help me.Thanks 4 advance. #include <stdlib.h> #include <stdio.h> ...
7
3878
by: Vinodh | last post by:
Started reading about Binary Trees and got the following questions in mind. Please help. Definition of a Binary Tree from "Data Structures using C and C++ by Tanenbaum" goes like this, "A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. The first subset contains a single element called the 'Root' of the tree. The other two subsets are themselves binary trees, called the 'Left'...
0
9839
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, well explore What is ONU, What Is Router, ONU & Routers main usage, and What is the difference between ONU and Router. Lets take a closer look ! Part I. Meaning of...
0
10871
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
10564
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
0
9396
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development projectplanning, coding, testing, and deploymentwithout human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
7806
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupr who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
6998
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
5668
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
1
4474
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
4039
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.