Iterating sparse arrays

**Richard Cornford** · Jul 23 '05, 04:40 PM

Re: Iterating sparse arrays

Christopher Benson-Manica wrote:[color=blue]
> If an array is sparse, say something like
>
> var foo=[];
> foo[3]=4;
> foo['bar']='baz';
> foo['quux']='moo';
>
> is there a way to iterate through the entire array?[/color]
<snip>

for (var c = foo.length; c--; ){
... // using foo[c]
}

The values at indexes 0 to 2 will return Undefined values. The named
properties are not related to the Arrayness of the Array object but
rather to its Objectness. As such they should not be considered relevant
to a desire to iterate through the "entire array".

Richard.

**Douglas Crockford** · Jul 23 '05, 04:40 PM

Re: Iterating sparse arrays

> If an array is sparse, say something like[color=blue]
>
> var foo=[];
> foo[3]=4;
> foo['bar']='baz';
> foo['quux']='moo';
>
> is there a way to iterate through the entire array?[/color]

It is incorrect to use an array when the keys are non-integers. If you
have keys like 'bar' and 'quux', you should be using an object. You can
then use the for..in statement to iterate through them.

var foo = {};
foo[3] = 4;
foo.bar = 'baz';
foo['quux'] = 'moo';

for (key in foo) {
...
}

See http://www.crockford.com/javascript/survey.html

**Robert** · Jul 23 '05, 04:41 PM

Re: Iterating sparse arrays

In article <csjvpb$6of$1@c hessie.cirr.com >,
Christopher Benson-Manica <ataru@nospam.c yberspace.org> wrote:
[color=blue]
> If an array is sparse, say something like
>
> var foo=[];
> foo[3]=4;
> foo['bar']='baz';
> foo['quux']='moo';
>
> is there a way to iterate through the entire array?[/color]

Yes.

Note: The length property includes the numeric indexes. Since three is
the highest index, the length property has a value of four.

Robert

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<title>Sparse array</title>

<script type="text/javascript">

var foo=[];
foo[3]=4;
foo['bar']='baz';
foo['quux']='moo';

var accumulate = "";

for (var i in foo)
{
accumulate += "foo["+ i + "] = " + foo[i] + "; ";
}

alert(accumulat e);

alert("number of elements in foo = " + foo.length);
</script>
</head>
<body>
<p>Demonstrat e retrieving all set array values.</p>
</body>

**Robert** · Jul 23 '05, 04:41 PM

Re: Iterating sparse arrays

In article <d9b27$41ed9bce $436562c0$7637@ msgid.meganewss ervers.com>,
Douglas Crockford <nospam@covad.n et> wrote:
[color=blue][color=green]
> > If an array is sparse, say something like
> >
> > var foo=[];
> > foo[3]=4;
> > foo['bar']='baz';
> > foo['quux']='moo';
> >
> > is there a way to iterate through the entire array?[/color]
>
> It is incorrect to use an array when the keys are non-integers.[/color]

I think this is too strong of a statement since the array declaration
supports string values as references. See my post to this thread for
the example code.

When you declare an object an array your javascript supports methods
like pop and the length property with the array object. When you
declare a variable an object you get fewer methods and properties. The
author of the javascript code should decide what is more appropriate.

I do not think we can tell from the segment of code shown what is more
appropriate.

The object declaration does allow for a more compact declaration:

var foo= { 3: 4, bar: "baz", "quux": "moo" };

Robert

**Douglas Crockford** · Jul 23 '05, 04:41 PM

Re: Iterating sparse arrays

>>It is incorrect to use an array when the keys are non-integers.
[color=blue]
> I think this is too strong of a statement since the array declaration
> supports string values as references.[/color]

Wrong is wrong even if you do not understand the difference.

**David Given** · Jul 23 '05, 04:41 PM

Re: Iterating sparse arrays

Robert wrote:
[...][color=blue]
> When you declare an object an array your javascript supports methods
> like pop and the length property with the array object.[/color]

What do push and pop do if there are non-integer keys in the array?

[...][color=blue]
> I do not think we can tell from the segment of code shown what is more
> appropriate.[/color]

With better designed programming languages, associative arrays distinguish
between methods and data, so you can have a key "push" which doesn't
conflict with the method push(). Alas, Javascript doesn't seem to have this
concept, which is a shame.

It's usually considered good practice (in other languages with similar
semantics to Javascript) that associative arrays are used for storing
stupid data and objects are used for storing smart data; that is, it's
intended that the data gets modified by calling methods on the object.

--
+- David Given --McQ-+ (base 10) = (base pi)
| dg@cowlark.com | 1 = 1; 2 = 2; 3 = 3
| (dg@tao-group.com) | 3.1415926... = 10.0
+- www.cowlark.com --+ 4 = 12.201220211...

**Robert** · Jul 23 '05, 04:41 PM

Re: Iterating sparse arrays

My understanding that a numeric index of an array is converted to a
string then looked up in the array. The code below seems to
demonstrate this:

var list = [];
list[1] = "abc";
alert("Index as a number one and the string one is " +
(list["1"] == list[1] ));

What I am staying is that you need to use the data structure the best
represents your intent.

Robert

**Robert** · Jul 23 '05, 04:41 PM

Re: Iterating sparse arrays

In article <MsxHd.673$DD5. 533@newsfe5-gui.ntli.net>,
David Given <dg@cowlark.com > wrote:

[color=blue]
> With better designed programming languages, associative arrays distinguish
> between methods and data, so you can have a key "push" which doesn't
> conflict with the method push(). Alas, Javascript doesn't seem to have this
> concept, which is a shame.[/color]

This is unfortunate. Seems like 'informal' languages win out in market
share over 'formal' one.
[color=blue]
> It's usually considered good practice (in other languages with similar
> semantics to Javascript) that associative arrays are used for storing[/color]

People freak out over the term 'associative arrays' in this forum.
'cause it's not in the standard they stay.
[color=blue]
> stupid data and objects are used for storing smart data; that is, it's
> intended that the data gets modified by calling methods on the object.[/color]

Robert

**Christopher Benson-Manica** · Jul 23 '05, 04:41 PM

Re: Iterating sparse arrays

Douglas Crockford <nospam@covad.n et> spoke thus:
[color=blue]
> It is incorrect to use an array when the keys are non-integers. If you
> have keys like 'bar' and 'quux', you should be using an object. You can
> then use the for..in statement to iterate through them.[/color]
[color=blue]
> var foo = {};
> foo[3] = 4;
> foo.bar = 'baz';
> foo['quux'] = 'moo';[/color]
[color=blue]
> for (key in foo) {
> ...
> }[/color]

That is a beautiful thing - thank you for showing me the light!

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cybers pace.org | don't, I need to know. Flames welcome.

**David Given** · Jul 23 '05, 04:42 PM

Re: Iterating sparse arrays

Robert wrote:
[...][color=blue][color=green]
>> It's usually considered good practice (in other languages with similar
>> semantics to Javascript) that associative arrays are used for storing[/color]
>
> People freak out over the term 'associative arrays' in this forum.
> 'cause it's not in the standard they stay.[/color]

Having done some experimentation ... you're right, they aren't true
associative arrays.

a = new Array();
b = {value:"object1 "};
c = {value:"object2 "};
a[b] = 42;
a[c] = 42;
for (i in a) alert(a[i])

How many alert boxes do you get? One. It would appear that Array is hashing
both objects to the same value. In fact...

for (i in a) alert(i.value)

....produces 'undefined', so it's not even storing a real object.

Using an object instead of an array for 'a' does the same thing. That sucks.
If it doesn't work properly with values that aren't a particular type, it
should damn well produce a run-time error.

Here we go. ECMAscript specification, 15.2.4.5: property names seem to have
toString called on them before hashing. Which means that both object keys
are turning into '[object Object]'. That's grotesque...

....and Arrays are just Objects with some utility methods, so the same thing
applies there.

I'm going to need a real associative array; I think I can come up with a
reasonably efficient one using two Arrays. Anyone interested?

--
+- David Given --McQ-+ "I don't like the thought of her hearing what I'm
| dg@cowlark.com | thinking." "*No-one* likes the thought of hearing
| (dg@tao-group.com) | what you're thinking." --- Firefly, _Objects in
+- www.cowlark.com --+ Space_

**Michael Winter** · Jul 23 '05, 04:42 PM

Re: Iterating sparse arrays

On Wed, 19 Jan 2005 14:25:24 -0500, Robert <rccharles@my-deja.com> wrote:

[snip]
[color=blue]
> People freak out over the term 'associative arrays' in this forum.[/color]

No-one has "freaked out" over the term, however there is disagreement with
regard to its suitability.

ECMAScript provides a syntax that resembles associative array usage and
does, to a certain extent, meet what is expected of the data type.
However, all objects in ECMAScript have predefined members and these may
cause problems, especially as you cannot determine (without supporting
code) whether a member is predefined or part of the "associativ e array".
There are other issues:

- You cannot reliably enumerate elements within the "associativ e
array".

Whilst a for..in statement will enumerate all properties within an
object, it may not be possible to determine what has been added and
what was predefined. Though I haven't encountered a user agent that
allows a host- or specification-defined property to be enumerated,
that (1) doesn't mean the former would never happen, and (2) doesn't
account for any properties added to the prototype of Object or a
more specific object (such as Array, if you decided to use that for
some reason).

- You cannot determine the number of elements within an "associativ e
array".

Though this might not be important in all instances, this feature
is not available in ECMAScript.

The main objection I have to the term is that it leads to confusion.
Examples such as

var hash = new Array();
hash['property'] = value;

do nothing but instill the mistaken belief that arrays can be subscripted
using arbitrary strings. The same effect could be achieved with

var hash = new Object();
hash.property = value;

or

var hash = {property : value};

but this isn't shown.

Instead of understanding the actual mechanics - which really are quite
simple - new programmers believe a feature exists where in fact it does
not.

ECMAScript allows one to use square brackets to access the
properties of an object in addition to the normal dot notation
form. The use of expressions within the square bracket property
accessors provides a great deal of flexibility and allows something
akin to associative arrays or hash tables using nothing more than
an object. However, there are some caveats to this usage.

Fleshed out to include descriptions of the topics mentioned in that
paragraph and clear code examples should provide an accurate
understanding. The reader would know about the square bracket property
accessors and how they can be used to construct property names (hopefully
reducing the incidence of eval usage), *and* how objects can be used to
implement a basic hash table. The article
(<URL:http://www.jibbering.c om/faq/faq_notes/square_brackets .html>) in the
FAQ notes certainly goes a long way to accomplish this.

[snip]

Mike

--
Michael Winter
Replace ".invalid" with ".uk" to reply by e-mail.

**Michael Winter** · Jul 23 '05, 04:42 PM

Re: Iterating sparse arrays

On Thu, 20 Jan 2005 15:06:45 GMT, David Given <dg@cowlark.com > wrote:
[color=blue]
> In fact...
>
> for (i in a) alert(i.value)
>
> ...produces 'undefined',[/color]

It should in every case. The value assigned to i on each iteration is the
property name as a string, and strings don't have a value property. If you
want the value of the enumerated property, use

a[i]
[color=blue]
> Using an object instead of an array for 'a' does the same thing.[/color]

Again, it should. This whole business has nothing to do with arrays. See
my other post (and the link therein).
[color=blue]
> I'm going to need a real associative array;[/color]

There are several in the archives. Mine is at
<URL:http://www.mlwinter.pw p.blueyonder.co .uk/clj/hash.js> (14.4KB). This
particular implementation allows objects to be true keys (rather than only
their toString value). However, it's also more readable than efficient (or
small). If you do end up using it, at the very least I'd advise you to
make a copy, remove methods that you aren't using (including the Iterator,
if appropriate) and run it through JSMin
(<URL:http://www.crockford.c om/javascript/jsmin.html>). That'll take out
about 10.5KBs of comments and whitespace. If you want to be adventurous,
you could also shorten the variable names - that'll shave off another
kilobyte or so.

I'm terrible at formal testing procedures, so the script hasn't undergone
any, but playing with it hasn't uncovered any errors (unlike the last time
I uploaded it[1] :-().

Mike

[1] My apologies for asking for a check of a blatently non-functioning
script.

--
Michael Winter
Replace ".invalid" with ".uk" to reply by e-mail.

**David Given** · Jul 23 '05, 04:42 PM

Re: Iterating sparse arrays

Michael Winter wrote:
[...][color=blue]
> http://www.mlwinter.pwp.blueyonder.co.uk/clj/hash.js[/color]

I'll certainly use this; ta. However, looking at the code, you seem to be
using toString() as your hash function. This will mean that all objects
hash to the same value, which means that in the common case of...

twoWayHashTable = new AssociativeArra y()
for (lots)
{
twoWayHashTable .put(key, value);
twoWayHashTable .put(value, key);
}

....then if value is an object, I'm going to end up with a vast linear list
as one of the hash chains.

Does Javascript have a real hash function? I couldn't find one, and I notice
that:

a = {}
b = {}
ASSERT(a != b)
ASSERT(!(a < b))
ASSERT(!(a > b))

Aaargh. This is, of course, completely useless for constructing trees.

--
+- David Given --McQ-+ "I don't like the thought of her hearing what I'm
| dg@cowlark.com | thinking." "*No-one* likes the thought of hearing
| (dg@tao-group.com) | what you're thinking." --- Firefly, _Objects in
+- www.cowlark.com --+ Space_

**Michael Winter** · Jul 23 '05, 04:42 PM

Re: Iterating sparse arrays

On Thu, 20 Jan 2005 16:48:20 GMT, David Given <dg@cowlark.com > wrote:
[color=blue]
> [...] looking at the code, you seem to be using toString() as your hash
> function.[/color]

Yes, as their's no native alternative (answering your later question). One
could force client code to implement a hashCode method like Java, but that
would add (*way*) too much of a burden.
[color=blue]
> [...] I'm going to end up with a vast linear list [...][/color]

True, iff all of the objects have the same toString result[1], but I seem
to remember good performance (see the end of
<URL:http://groups.google.c o.uk/groups?selm=ops ilrs6aax13kvk%4 0atlantis>).

[snip]
[color=blue]
> a = {}
> b = {}
> ASSERT(a != b)[/color]

Object equality is based on references to the object itself, not its
content. References are only equal if they refer to the same object or a
joined object (algorithm: 11.9.3; joined objects 13.1.2).
[color=blue]
> ASSERT(!(a < b))
> ASSERT(!(a > b))[/color]

In relational comparisons (11.8.5), the internal ToPrimitive operator
(9.1) is called on both objects with the hint, Number. If a valueOf method
is defined, the return value is used when comparing, otherwise toString is
used (8.6.2.6).

Mike

And here I was thinking I'd take a break from Usenet...

[1] If they're your own objects, you could implement a toString method
that generates a return based on the content of that object.
Alternatively, you could just generate random numbers:

function MyObject() {
var id = String((Math.ra ndom() % 1) * 100000);

this.toString = function() {return id;};
}

Although there would be some clashes, it would prevent a single list and
should have relatively little overhead.

--
Michael Winter
Replace ".invalid" with ".uk" to reply by e-mail.

Iterating sparse arrays

Iterating sparse arrays

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment