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 9 6276
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
}
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
"GiantCranesInDublin" <ga********@gmail.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
"GiantCranesInDublin" <ga********@gmail.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/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
Thomas 'PointedEars' Lahn wrote: 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.
[...]
--
Rob
Lasse Reichstein Nielsen wrote: "GiantCranesInDublin" <ga********@gmail.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
Many thanks for the replies. I have followed your advice and am seeing
great performance.
Cheers,
Gavin
Thomas 'PointedEars' Lahn <Po*********@web.de> writes: Lasse Reichstein Nielsen wrote:
"GiantCranesInDublin" <ga********@gmail.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
"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
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
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.
GiantCranesInDublin 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.length; i--;)
{
this.add(arguments[i]);
}
}
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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
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...
|
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,...
|
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...
|
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...
|
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
|
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...
|
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 =...
|
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...
|
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...
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
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,...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
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,...
| | |