how to create 5-dimensional array ?

[VK]

While trying to port the promised Shannon's Clairvoyant code to
Javascript, I am having real troubles to figure out what that would be
in Javascript: 5-dimensional array of 72 elements
In VBA it is as simple as:

Dim Moves(0 To 1, 0 To 2, 0 To 1, 0 To 2, 0 To 1) As Integer

but I am really lost in trying to visualize it so to create an
adequate structure . So far I am using the fact of simple object
augmentation in Javascript so doing like

var Moves = new Object;
// ...
if (typeof Moves['01001'] == 'undefined') {
Moves['01001'] = 1;
}
else {
++Moves['01001'];
}

Sorry if the question is not clear enough, I can explain deeper.

 

[Thomas 'PointedEars' Lahn]

[...] I am having real troubles to figure out what that would be
in Javascript: 5-dimensional array of 72 elements
In VBA it is as simple as:

Dim Moves(0 To 1, 0 To 2, 0 To 1, 0 To 2, 0 To 1) As Integer

but I am really lost in trying to visualize it so to create an
adequate structure .

Start with the representation of a two-dimensional array, then improve on
that. See the FAQ.


PointedEars

 

[nick]

While trying to port the promised Shannon's Clairvoyant code to
Javascript, I am having real troubles to figure out what that would be
in Javascript: 5-dimensional array of 72 elements
In VBA it is as simple as:

  Dim Moves(0 To 1, 0 To 2, 0 To 1, 0 To 2, 0 To 1) As Integer

Here's one way to emulate multidimensional arrays in languages that
lack them. It requires that each dimension but the last have a fixed
size, but your case seems to support that.

For an example we can use a 2d 5x4 data set.

. . . . .
. . . . .
. . . x .
. . . . .

Now if this was a 2d array with the first dimension being the column
and the second being the row, the 'x' would be at index [3, 2].

var myPos = board[3, 2]; // not gonna work

To emulate it with a 1d array we could do this:

var myPos = board[3 + 2*5];

In other words, separate your indices with '+' and multiply each index
after the first by all previous dimension boundaries. If it was a 3d
array, with the dataset shown being element 4 of the first dimension
of the array, and the size of the first dimension is 7, it would
become:

var myPos = board[4 + 3*7 + 2*7*5];

You could turn this idea into a class constructor (not tested):

function FixedMultiArray () {
this._sizes = arguments;
this._data = [];
}

FixedMultiArray.prototype = new function() {
// get an element
this.get = function (indexArray) {
return this._data[getRealIndex(indexArray)];
}
// set an element
this.set = function (indexArray, value) {
this._data[getRealIndex(indexArray)] = value;
}
// get the real index in the 1d array
function getRealIndex(indexArray) {
for (var i=0, realIndex=0; i<indexArray.length; i++) {
var ix = indexArray;
for (var j=0; j<i; j++) ix *= this._sizes[j];
realIndex += ix;
}
return realIndex;
}
}

...
var myData = new FixedMultiArray(2,3,2,3,2);
myData.set([0,1,0,1,0], 'someValue');
...

I hope this is useful to you.

-- Nick

 

[VK]

<code>

<code>

Great thanks to all of you! I have enough food for thoughts now.

P.S. Stefan Weiss: "I swear, one of these days I'm going to learn
Russian." It doesn't mean that I'm Russian but I have good courses to
recommend. Lucky to study code samples across the Web a particular
human language knowledge is not a must. Javascript code is Javascript
code on Chinese pages as well

P.P.S. Special thanks to Thomas for an educational yet rather hard to
use answer.

 

[Thomas 'PointedEars' Lahn]

if (typeof Moves['01001'] == 'undefined') {
Moves['01001'] = 1;
}

...

I don't see anything intrinsically wrong with that. If strings work for
you, why not use them. One problem I see with this is when one of the
dimensions gets larger than 9.

Probably you mean _indexes_ instead of dimensions. This can be worked
around with a delimiter, though:

if (typeof moves['0-1-0-0-1'] == 'undefined')
{
moves['0-1-0-0-1'] = 1;
}

If you want to go with the nested array approach, you'd need loops to
create/initialize the structure, or a generator function. Here's a
simplistic attempt for a dim "replacement", which I'm sure can be
improved on. For example, the DEFAULT_VALUE could be passed as a third
argument for each [from, to] group.

var DEFAULT_VALUE = 0;

function dim () {
if (arguments.length) {
var args = Array.prototype.splice.call(arguments, 0),
fromTo = args.shift(),
start = fromTo[0],
end = fromTo[1],
result = [];
while (start <= end) {
result[start] = dim.apply(null, args);
++start;
}
return result;
}
return DEFAULT_VALUE;
}

// Dim Moves(0 To 1, 0 To 2, 0 To 1, 0 To 2, 0 To 1)
var moves = dim([0, 1], [0, 2], [0, 1], [0, 2], [0, 1]);

// ++Moves['01001']
++moves[0][1][0][0][1];

console.log(moves);

It is unnecessary to initialize each and every "element" of the "multi-
dimensional array", though. In fact, it wastes a lot of memory. Consider
this instead:

function Matrix()
{
this.data = Array.prototype.slice.call(arguments, 0);
}

Matrix.prototype.putValue = function (x, y, value) {
var tmp = this.data;

for (var i = 0, len = arguments.length; i < len - 2; ++i)
{
var arg = arguments;

if (typeof tmp[arg] == "undefined")
{
tmp[arg] = [];
}

tmp = tmp[arg];
}

var lastArgs = Array.prototype.slice.call(arguments, i);
tmp[lastArgs[0]] = lastArgs[1];

return lastArgs[1];
};

Matrix.prototype.getValue = function (x, y) {
var tmp = this.data;

for (var i = 0, len = arguments.length; i < len; ++i)
{
var arg = arguments;
tmp = tmp[arg];

if (typeof tmp == "undefined")
{
break;
}
}

return tmp;
};

Matrix.prototype.inc = function (x, y) {
var
coords = Array.prototype.slice(arguments, 0).
v = +this.getValue.apply(this, coords);

return this.putValue.apply(
this, coords.concat((isNaN(v) ? 0 : +v) + 1));
};

var a = new Matrix();
a.inc(0, 1, 0, 0, 1);


PointedEars

 

[Sean Kinsey]

I swear, one of these days I'm going to learn Russian. There's a huge
part of the web that I don't have access to, and that bugs me.

Haven't you tried Google Chrome with its translation feature?

 

[Thomas 'PointedEars' Lahn]

Matrix.prototype.inc = function (x, y) {
var
coords = Array.prototype.slice(arguments, 0).

coords = Array.prototype.slice.call(arguments, 0),

v = +this.getValue.apply(this, coords);
[...]

 

[VK]

        coords = Array.prototype.slice.call(arguments, 0),

Thank you! Working on the interface right now.

 

[Dr J R Stockton]

In comp.lang.javascript message <7fe7b790-e599-4592-a83d-8526174bacfe@y3
0g2000yqh.googlegroups.com>, Mon, 26 Apr 2010 04:28:58, Sean Kinsey

Haven't you tried Google Chrome with its translation feature?

There is no *need* to use Chrome for that; one can go to
<http://translate.google.com/?langpair=it|en#> directly, and remove or
adjust the language pair. I don't know what the hash is for.

 

[Michael Wojcik]

In comp.lang.javascript message <7fe7b790-e599-4592-a83d-8526174bacfe@y3
0g2000yqh.googlegroups.com>, Mon, 26 Apr 2010 04:28:58, Sean Kinsey


There is no *need* to use Chrome for that; one can go to
<http://translate.google.com/?langpair=it|en#> directly, and remove or
adjust the language pair. I don't know what the hash is for.

The hash is the delimiter for an empty fragment identifier. An empty
fragment ID is a no-op for an HTTP URL, but it appears that Google
Translate's URL canonicalization will add it if you omit it.

You can also add "&text=[URL-encoded text in source language]" to the
URL, and have the page appear with the translation:

http://translate.google.com/?langpair=it|en&text=ciao#

in which case, at least if you have a small viewport, the "#autotrans"
fragment identifier might be useful:

http://translate.google.com/?langpair=it|en&text=ciao#autotrans

 

[Guest]

While trying to port the promised Shannon's Clairvoyant code to
Javascript, I am having real troubles to figure out what that would be
in Javascript: 5-dimensional array ...

I wouldn't. Suppose you want to have five dimension, let me index them
from 0 through 4 and want to hold data with index (a,b,c,d,e) where the
first index has A possible values (from 0 throut A-1), the second has
B values (from 0 through B-1), etc. I would construct a one dimensional
array of size A*B*C*D*E, say MYARRAY and use the function:
_indexer(a,b,c,d,e) = {return ((((e*D+d)*C+c)*B+b)*A+a)}
as MYARRAY[_indexer(a,b,c,d,e)]

It is easy enough to calculate _indexer. It gives a single number from
five and that number is unique (once you know it, take the result mod(A)
to find a mod A, but as a can only vary from 0 through A-1, you know A.
Subtract to get (((e*D+d)*C+c)*B+b)*A, divide by A to get ((e*D+d)*C+c)*B+b
and take that mod B to get b mod B. But b can only vary from 0 through B-1
so you know b ... in short, once you have that single number it gives the
five numbers which are used to create it).

This one-one mapping maps to the range 0 through A*B*C*D*E-1, A*B*C*D*E
consecutive integers to hold just that many elements (which would be
required by the five dimensional array).

There *are* ways to do it if you don't know A,B,C,D,E, but they can
be inefficient (find some one-one mappying from five non-negative
integers into the integers) in that it may not map to all consecutive
integers in the smallest range.

 

[VK]

While trying to port the promised Shannon's Clairvoyant code to
Javascript, I am having real troubles to figure out what that would be
in Javascript: 5-dimensional array ...

I wouldn't. Suppose you want to have five dimension, let me index them
from 0 through 4 and want to hold data with index (a,b,c,d,e) where the
first index has A possible values (from 0 throut A-1), the second has
B values (from 0 through B-1), etc. I would construct a one dimensional
array of size A*B*C*D*E, say MYARRAY and use the function:
_indexer(a,b,c,d,e) = {return ((((e*D+d)*C+c)*B+b)*A+a)}
as MYARRAY[_indexer(a,b,c,d,e)]

It is easy enough to calculate _indexer. It gives a single number from
five and that number is unique (once you know it, take the result mod(A)
to find a mod A, but as a can only vary from 0 through A-1, you know A.
Subtract to get (((e*D+d)*C+c)*B+b)*A, divide by A to get ((e*D+d)*C+c)*B+b
and take that mod B to get b mod B. But b can only vary from 0 through B-1
so you know b ... in short, once you have that single number it gives the
five numbers which are used to create it).

This one-one mapping maps to the range 0 through A*B*C*D*E-1, A*B*C*D*E
consecutive integers to hold just that many elements (which would be
required by the five dimensional array).

You just answered it before I got ready to post myself :-(
Indeed I was getting nuts by trying to visualize that "5-dimensional
array of 72 elements" because I hate to use things I do not "see" even
if they work properly. Finally I realized that numOfNodes-dimensional
real array just unnecessarily obfuscates the otherwise simple picture.
In fact we have a symmetrical binary tree with 5 node steps and 64
leaves. On each of five steps we have to either turn left or turn
right. Let's denote left turn as zero and right turn as 1. This way
the path to each leaf is one of permutations between 00000 (all left
turns) and 11111 (all right turns). Let's look at these permutations
as binary numbers. Let's also introduce the "holding bit" on the left
to prevent zeros collapsing if we ever need to stringify the path. The
set of paths to each leaf is then the set of binary numbers 100000 -
111111 (decimal 32 - 63).
The universal init algorithm then is as simple as:

function initTree(numOfNodes) {
var Tree = new Array();
// var Tree = new Object();
var lBound = '';
var uBound = '';

do {
lBound+= '0';
} while (lBound.length < numOfNodes);
lBound = parseInt('1'+lBound, 2);

do {
uBound+= '1';
} while (uBound.length < numOfNodes);
uBound = parseInt('1'+uBound, 2);

for (var i = lBound; i<uBound; i++) {
Tree = 0; // or another init value
}
return Tree;
}

The algorithm can be further improved of course. For instance it is
highly tempting to use binary logical operators AND, OR, XOR instead
of string manipulations in order to get paths and later to match the
given path to the leaf value. It is tempting as it would be first ever
practical and logical use of binary logical operators in JavaScript I
would ever saw.

The beauty of this approach is that it works for ternary and higher
orders trees as well. One just need to think for say ternary tree
(left, straight, right choice on each node) as a set of two wrong
choices and one right choice. By denoting wrong with 0 and right with
1 we are getting 001, 010, 100 and respectively the full set of paths
will be found in a range of base-3 numbers with the right choice for
each node being a trit in that number. So on for base-4, base-5 etc.

I am sure that all that is already written in tree books but I arrived
to that completely by my own so cannot resist to state how proud I am
of myself

P.S. I am wondering if it would be more effective or equal for storing
paths: to use properties of Object instance or to use sparse Array
instance?

 

[VK]

The beauty of this approach is that it works for ternary and higher
orders trees as well. One just need to think for say ternary tree
(left, straight, right choice on each node) as a set of two wrong
choices and one right choice. By denoting wrong with 0 and right with
1 we are getting 001, 010, 100 and respectively the full set of paths
will be found in a range of base-3 numbers with the right choice for
each node being a trit in that number.

The latter means that it is possible to build an analog of neural
quantum network and entanglement states using tools of JavaScript.
Just each trit has to be a qubit like

function Qubit(entangledQubit) {
this.superposition = true;
this.entangledQubit = entangledQubit || null;
this.state = -1;
this.mesure = Qubit.mesure;
}
Quibit.mesure = function() {
this.superposition = false;
var n = Math.floor(Math.random()*2);
this.state = (n==2) ? 1 : 0;
this.entangledQubit.state = !this.state;
}

It's all highly sketchy and not even sure if practically applicable
but hell, I have to think of it immediately...

-

 

[Evertjan.]

VK wrote on 01 mei 2010 in comp.lang.javascript:

Indeed I was getting nuts by trying to visualize that "5-dimensional
array of 72 elements" because I hate to use things I do not "see" even
if they work properly.

Having a 5 dimensional array, which each array maximized at 1000 is easy,
if you do not fill the array to much.

Use an object [here 3 members are used]:

<script type='text/javascript'>

var my5dim = {
'000!235!148!999!400':'qwerty',
'074!088!002!000!874':'asd',
'000!088!148!999!401':'blah'};

function getArrayVal(a,b,c,d,e) {
return my5dim[t3(a)+'!'+t3(b)+'!'+t3(c)+'!'+t3(d)+'!'+t3(e)];
};

function t3(x){return (1000+x+'').substr(1)};

alert( getArrayVal(0,235,148,999,400) ); // qwerty
alert( getArrayVal(0,235,148,999,401) ); // undefined

</script>

 

[VK]

VK wrote on 01 mei 2010 in comp.lang.javascript:

Indeed I was getting nuts by trying to visualize that "5-dimensional
array of 72 elements" because I hate to use things I do not "see" even
if they work properly.

Having a 5 dimensional array, which each array maximized at 1000 is easy,
if you do not fill the array to much.

Use an object [here 3 members are used]:

<script type='text/javascript'>

var my5dim = {
 '000!235!148!999!400':'qwerty',
 '074!088!002!000!874':'asd',
 '000!088!148!999!401':'blah'};

function getArrayVal(a,b,c,d,e) {
  return my5dim[t3(a)+'!'+t3(b)+'!'+t3(c)+'!'+t3(d)+'!'+t3(e)];

};

function t3(x){return (1000+x+'').substr(1)};

alert( getArrayVal(0,235,148,999,400) ); // qwerty
alert( getArrayVal(0,235,148,999,401) ); // undefined

</script>

There is always a way to do something in several ways. I am just
"felling in love" with trees and the idea of thinking of trees, node
levels, leaves and paths rather than of nested arrays, indexes and
array elements. It seems much more visual and elegant, not talking of
production and usage cost.

<script type="text/javascript">

function BinaryTree(depth) {

/* Building a perfect binary tree */

// Prevent calling our constructor
// as a regular function:
if (!(this instanceof BinaryTree)) {
return new Error('Illegal constructor call');
}

// Argument validity check:
if (
(typeof depth != 'number') ||
(depth == 0) ||
(depth != Math.round(depth))
) {
return new Error('Illegal depth value');
}

// The Array instance index must be in the range
// [0, 4294967295] which is
// [0, 11111111111111111111111111111111] binary
// With the "holding bit" usage that gives us
// 31 dimensions/ tree depth limit or 32 without
// that bit.
if (depth > 31) {
return new Error('Depth value is out of range');
}

var Tree = new Array();
var lBound = '';
var uBound = '';

do {
lBound+= '0';
} while (lBound.length < depth);
lBound = parseInt('1'+lBound, 2);

do {
uBound+= '1';
} while (uBound.length < depth);
uBound = parseInt('1'+uBound, 2);

for (var i = lBound; i<uBound; i++) {
Tree = 0; // or another init value
}

this.Tree = Tree;
this.tree = this.Tree // lower case alias
this.lBound = lBound;
this.uBound = uBound;
this.length = i;
this.get = BinaryTree.get;
this.set = BinaryTree.set;
}

BinaryTree.get = function(i) {
return this.Tree[parseInt(i,2)];
}

BinaryTree.set = function(i, val) {
this.Tree[parseInt(i,2)] = val;
}


// 20 levels depth, 2097151 leaves
var tree = new BinaryTree(20);

window.alert(
tree.get('100000000000000000011')
); // 0

tree.set('100000000000000000011', 1);

window.alert(
tree.get('100000000000000000011')
); // 1
</script>


The instantiation of 20 level (dimensions) in depth structure with
2,097,151 leaves makes Fx even on my Intel Dual 1.6GHz to think for a
couple of second, but nothing close to a crucial delay. After that the
get/set usage cost is negligible.

 

[VK]

The instantiation of 20 level (dimensions) in depth structure with
2,097,151 leaves makes Fx even on my Intel Dual 1.6GHz to think for a
couple of second, but nothing close to a crucial delay. After that the
get/set usage cost is negligible.

Full capacity 31 levels in depth tree (2,147,483,648 leaves) will take
approx. 1024 times longer. On the same system it would be approx. 34
mins to wait which is way beyond a regular acceptable waiting period.
So if one needs to use trees with more than 20 levels in depth another
approach should be used. I guess the Object instance augmentation
should be used without the initial properties instantiation, so
undefined or 0 both treated as 0.
I just don't need such monstrosity at this moment, so not coding that
variant.

 

[VK]

Full capacity 31 levels in depth tree (2,147,483,648 leaves) will take
approx. 1024 times longer. On the same system it would be approx. 34
mins to wait which is way beyond a regular acceptable waiting period.
So if one needs to use trees with more than 20 levels in depth another
approach should be used. I guess the Object instance augmentation
should be used without the initial properties instantiation, so
undefined or 0 both treated as 0.
I just don't need such monstrosity at this moment, so not coding that
variant.

Just as a proof of concept I've made a working ternary tree
constructor ready for base-3 operations:

<script type="text/javascript">

function TernaryTree(depth) {

/* Building a perfect ternary tree */

// Prevent calling our constructor
// as a regular function:
if (!(this instanceof TernaryTree)) {
return new Error('Illegal constructor call');
}

// Argument validity check:
if (
(typeof depth != 'number') ||
(depth == 0) ||
(depth != Math.round(depth))
) {
return new Error('Illegal depth value');
}

// The Array instance index must be in the range
// [0, 4294967295] which is
// [0, 11111111111111111111111111111111] binary
// With the "holding bit" usage that gives us
// 10 dimensions/ tree depth limit as we have
// 111 111 111 111 111 111 111 111 111 111 for trits.
// That is 613,566,756 leaf nodes.
if (depth > 10) {
return new Error('Depth value is out of range');
}
var Tree = new Array();
var lBound = '';
var uBound = '';
var _depth = depth * 3;

do {
lBound+= '000';
} while (lBound.length < _depth);
lBound = parseInt('1'+lBound, 2);

do {
uBound+= '100';
} while (uBound.length < _depth);
uBound = parseInt('1'+uBound, 2);

for (var i = lBound; i<uBound; i++) {
Tree = 0; // or another init value
}

this.Tree = Tree;
this.tree = this.Tree // lower case alias
this.lBound = lBound;
this.uBound = uBound;
this.length = i;
this.get = TernaryTree.get;
}

TernaryTree.get = function(trits) {
var path = trits.join('');
return this.Tree[parseInt('1'+path,2)];
}



var left = '001';
var right = '100';
var straight = '010';

var tree = null;

// 5 levels depth, 18724(?) leaves
if ((tree = new TernaryTree(5)) instanceof Error) {
window.alert(tree.message);
}
else {
window.alert(tree.get([
left, left, right, straight, left
])); // 0
}
</script>

 

[Guest]

VK wrote on 01 mei 2010 in comp.lang.javascript:

Indeed I was getting nuts by trying to visualize that "5-dimensional
array of 72 elements" because I hate to use things I do not "see" even
if they work properly.

Having a 5 dimensional array, which each array maximized at 1000 is easy,
if you do not fill the array to much.

Use an object [here 3 members are used]:

<script type='text/javascript'>

var my5dim = {
'000!235!148!999!400':'qwerty',
'074!088!002!000!874':'asd',
'000!088!148!999!401':'blah'};

I was writing a little recursive routine in Javascript (it's a simple
language and I have the spider monkey interpreter) needing what was
effectively a two-dimensional array and originally used an object
(keys: ""+i1+","+i2)

In use, parameters were 100 to 500 and ... well, it was OK, but a
bit slow so I implemented it as a one dimensional array with
_indexer (one-one map from whole number pairs to whole numbers)
and that sped it up *quite* dramatically. It seems that with thousands
of keys, Javascript is not too efficient in searching the key space
to get a value. Perhaps I should have tried perl!

 

[Lasse Reichstein Nielsen]

I was writing a little recursive routine in Javascript (it's a simple
language and I have the spider monkey interpreter) needing what was
effectively a two-dimensional array and originally used an object
(keys: ""+i1+","+i2)

In use, parameters were 100 to 500 and ... well, it was OK, but a
bit slow so I implemented it as a one dimensional array with
_indexer (one-one map from whole number pairs to whole numbers)
and that sped it up *quite* dramatically.

Unsurprisingly, one might add.

It seems that with thousands of keys, Javascript is not too
efficient in searching the key space to get a value. Perhaps I
should have tried perl!

Have you considered the overhead of string concatenation for
each lookup? That is likely to take at least as long as doing
the actual lookup, and it creates a lot of garbage strings that
will trigger garbage collection more often.

/L

 

[Ry Nohryb]

VK wrote on 01 mei 2010 in comp.lang.javascript:

Having a 5 dimensional array, which each array maximized at 1000 is easy,
if you do not fill the array to much.

Use an object [here 3 members are used]:

<script type='text/javascript'>

var my5dim = {
 '000!235!148!999!400':'qwerty',
 '074!088!002!000!874':'asd',
 '000!088!148!999!401':'blah'};

I was writing a little recursive routine in Javascript (it's a simple
language and I have the spider monkey interpreter) needing what was
effectively a two-dimensional array and originally used an object
(keys: ""+i1+","+i2)

In use, parameters were 100 to 500 and ... well, it was OK, but a
bit slow so I implemented it as a one dimensional array with
_indexer (one-one map from whole number pairs to whole numbers)
and that sped it up *quite* dramatically. It seems that with thousands
of keys, Javascript is not too efficient in searching the key space
to get a value. Perhaps I should have tried perl!

That may have been so in the past, but it seems that it's not so
anymore in most current browsers: this snippet tests lookup of 1e6
elements in an array vs lookup in an object, and the results in my Mac
are:

FF 3.6:
array lookup: 258 ms
object lookup: 258 ms
Chrome:
array lookup: 7 ms
object lookup: 6 ms
Opera:
array lookup: 459 ms
object lookup: 424 ms
Safari:
array lookup: 9 ms
object lookup: 577 ms

http://jorgechamorro.com/cljs/098/

<script type="text/javascript">
onload= function () {
//debugger;

function log (txt) {
document.body.appendChild(
document.createElement('p')).innerHTML= txt;
}

var timer= (function () {
var time;
return function timer (p, msg) {
switch (p) {
case "start":
return (time= +new Date());
break;
case "stop":
return log((msg || "")+ (new Date()- time)+ " ms");
break
}
}
})();
var array= [];
var object= {};
var kMax= 1e6;
var n= kMax;
var acumulador= 0;

while (n--) {
object[n]= array[n]= n%2 ? 1 : -1;
}

n= kMax;
timer('start');
while (n--) {
acumulador+= array[n];
}
timer('stop', "array lookup: ");

n= kMax;
timer('start');
while (n--) {
acumulador+= object[n];
}
timer('stop', "object lookup: ");

};
</script>