JavaScript; n-dimensional array creation

Question

In the process of building a JavaScript interpreter for a simple language, I've faced the following problem;

After parsing, we get an array of indices that specifies the element in an n-dimensional array to be modified. For instance, after parsing this:

a[1, 1, 1]

We get an array [1, 1, 1]. The language I'm working on doesn't have variable definitions, so variables get initialized on their first use. My goal is to be able to create this n-dimensional array so that I can place it in the variable table (in the example above, we'd need to create a 3-dimensional array).

The short question:

Is there a way to create an n-dimensional array in JavaScript without using eval()?

Piraeus

Answer 1

Tested in Chrome:

function createNDimArray(dimensions) {
    if (dimensions.length > 0) {
        var dim = dimensions[0];
        var rest = dimensions.slice(1);
        var newArray = new Array();
        for (var i = 0; i < dim; i++) {
            newArray[i] = createNDimArray(rest);
        }
        return newArray;
     } else {
        return undefined;
     }
 }

Then createNDimArray([3, 2, 5]) returns a 3x2x5 array.

You can use a similar recursive procedure to access an element whose index is in an array:

function getElement(array, indices) {
    if (indices.length == 0) {
        return array;
    } else {
        return getElement(array[indices[0]], indices.slice(1));
    }
 }

Setting an element is similar, and left as an exercise for the reader. 

Retaretable

I hate posting the same comment on two answers, but, like I said to @Pete: how would you access a specific element in the already-created array? – Piraeus

One suggestion: I think null is a better default value than undefined. That way it's easy to test whether you're outside the bounds of the array or just getting an empty value. But the OP doesn't specify, so undefined might be what he/she wants. – Byway

See my edit for accessing elements. And it would be trivial to make the default element a parameter to the creation function. – Retaretable

@Retaretable Yeah, that'll do it. Thanks! – Piraeus

The getElement-function seems to be not correct, slice is not defined. – Inhumane

@Inhumane Not sure what was going through my head when I wrote that, fixed it. – Retaretable

Instead of getElement(a, [2, 3, 5]) you can simply write a[2][3][5]. – Irreverence

@sebastian_k The whole point of the question is that you have a dynamic array of subscripts, you're not writing it literally. – Retaretable

I'm not sure I understand your point—couldn't I just go a[index1][index2][index3] if I need dynamic subscripts? – Irreverence

The number of dimensions is also dynamic. It could be a[index1] or a[index][index2]. – Retaretable

@sebastian_k He's implementing an interpreter for another language. So he's parsing its array indexing syntax and needs to implement it using JS. – Retaretable

@ArthurAlunts Array indexes go from 0 to 4, so there's no [5][5][5][5] element. – Retaretable

@ Barmar ok I have already corrected this in my answer see 6-th answer where evrything is ok! – Sheela

Answer 2

There's nothing built in, but it's pretty easy to create a function that would do the job:

var genArray = function () {
    var arr, len, i;
    if(arguments.length > 0) {
        len = [].slice.call(arguments, 0, 1)[0];
        arr = new Array(len);
        for(i = 0; i < len; i++) {
            arr[i] = genArray.apply(null, [].slice.call(arguments, 1));
        }
    } else {
        return null; //or whatever you want to initialize values to.
    }
    return arr;
};

var a = genArray(3, 2); //is [[null, null],[null, null],[null, null]]
var b = genArray(3, 1, 1); //is [[[null]],[[null]],[[null]]]

a[0][1]; //is null
b[1][0][0]; //is null
b[1][0][0] = 3;
b[1][0][0]; //is 3;
b; //is [[[null]],[[3]],[[null]]]

Maybe that will help?

PS --

I know this might seem like more effort than is necessary. But unfortunately, JavaScript arrays are not really "arrays" (if by "array" you mean a contiguous, indexed, immutable memory block). They're more like "maps" in most languages. So there's a certain amount of effort involved in creating them. Most languages have no problem creating multi-dimensional arrays because they're just doing some simple multiplication followed by an malloc(). But with JavaScript, you really have to go recursively generate your arrays if you want to have them pre-constructed. It's a pain, but it does demonstrate the effort required by the interpreter.

Go figure.

Byway

Clever; thanks. One more thing, though, how would you access a specific element in the already-created array? – Piraeus

I mean, since we don't know how many indices we'll actually be dealing with. – Piraeus

Hmm, not precisely. Suppose we've created the array, and then we're be faced with another array of indices [a, b, c]. How would you go on actually looking up array[a][b][c]? The main issue is that you don't know how many indices there will be. I know it can be done using eval(), but I hope there's a less-ugly solution. – Piraeus

@Abody97 Check Barmar's update to his answer. It will work on arrays generated by my code, also. – Byway

@Retaretable got it in his edit. I guess I'll have to accept his answer, even though you were first. Sorry about that. – Piraeus

Answer 3

For creating an n-dimensional array:

function createNDimArray(dimensions) {
 var ret = undefined;
 if(dimensions.length==1){
    ret = new Array(dimensions[0]);
    for (var i = 0; i < dimensions[0]; i++)
        ret[i]=null; //or another value
    return ret;     
 }
 else{
    //recursion
    var rest = dimensions.slice(1);
    ret = new Array(dimensions[0]);
    for (var i = 0; i < dimensions[0]; i++)
        ret[i]=createNDimArray(rest);       
    return ret;
 }
}

Dapplegray

Despite the lack of instructional help on this answer. This is the fastest one of the three listed recursion solutions. It is a great example of why "hard coding" the last iteration of recursion will greatly speeds things up. And the improved speed factor you get increases with higher and larger dimensions, compared to the other createNDimArray above (or genArray, which is the slowest). With a little refactoring, this solution can be made in four lines and possibly a touch faster. – Nootka

Answer 4

---

EDIT: Due to the fact that any recursive solution will have a limit to the size of the array you can create... I made another solution in my PJs @ GitHub library. This one runs at pseudo-instant speed and can create and manage a multidimensional array of any size, any structure, with any dimensions at any branch. It also can simulate prefilling and/or use a node object of custom design. Check it out here: https://github.com/PimpTrizkit/PJs/wiki/14.-Complex-Multidimensional-Object--(pCMO.js)

---

Using a modified version of jfabrizio's solution:

function createNDimArray(dimensions) {
    var t, i = 0, s = dimensions[0], arr = new Array(s);
    if ( dimensions.length < 3 ) for ( t = dimensions[1] ; i < s ; ) arr[i++] = new Array(t);
    else for ( t = dimensions.slice(1) ; i < s ; ) arr[i++] = createNDimArray(t);
    return arr;
}

Usages:

var arr = createNDimArray([3, 2, 3]); 
//  arr = [[[,,],[,,]],[[,,],[,,]],[[,,],[,,]]]
console.log(arr[2][1]); // in FF: Array [ <3 empty slots> ]
console.log("Falsy = " + (arr[2][1][0]?true:false) ); // Falsy = false

I found this to be quite a bit faster. I might stretch to say that it could be the fastest way possible to generate a N Dimensional array in Javascript. This refactoring above had some good speed increases. But, the best speed increase came from not prefilling, of course. This version doesn't prefill the array. It only returns a fully created N dimensional array of Ns lengths where the last level is just an empty array. I would hope that arr[x][y][z]?arr[x][y][z]:null is sufficient if you really need the null value. It is for my uses. :)

If you need prefilling, use his original version.

And, if you don't really care about what I did; then stop reading.

Want more geek talk? A little something about recursion for those learning out there. Alright here are the tactics. When doing deep recursion, keep in mind the final level. Its where most of the work is done. In this case its the Nth dimension, literally. This is your "payload", the rest is logistics. In jfab's function, when dimensions.length gets to 1, its last dimension, its in the Nth dimension and performs the payload. Which is to create the array of nulls, or in my case, an empty array. Since the recursion gets so deep each dimension is a factor of the last one. By the time you get to the Nth dimension you will have a lot of function calls and logistics gets cumbersome to the computer. And at the Nth dimension you will call your base recursion function (createNDimArray in our case) more times for the payload than you will for logistics. Now, as in jfab's original solution, putting the execution of the payload as the very first thing you do in recursion (if possible) is usually a good thing, especially if its simple. Here, by making the payload a building of the final 2D array (instead of just a 1D array by simply returning a new Array() only). Then the excessive amount of function calls now don't have to happen at this level. Now, of course, if you want to prefill the array, then this shortcut doesn't always help. But more to the point, prefilling the array would be the appropriate payload. By not visiting every item on the Nth dimension we have effectively removed it. That way there is one less level of function calls and basically the Nth dimension's payload is actually done on the N-1 th Dimension. And we are never calling the recursive function again just to deliver the new Array(). Unfortunately, the call to new Array(x) (in general) doesn't see it that way. Its execution time does increase with a larger x. Which is effectively still visiting every item in the Nth Dimension, but now we do it only once and with native code and wrapped in a tight and light loop. Now we require that createNDimArray can only be called with N > 1, ie never used to create 1D arrays. Theoretically you could require a larger N, and unroll even more dimensions at the end. Basically, the line with if ( dimensions.length < 3 ) will read something like < 4 or < 5 and you would have to wrap that many more for loops around the one thats there, and they would each all need their own set of vars --- so I'm not sure how efficient it all might be, as you are trading excessive function call and stack space/manipulation with a similar idea but in embedded for loops --- But I suppose it could speed up some environments if you know that N is always above a certain level or if its only for the final dimensions. Like here, I did it for the last two dimensions. But if you unroll too much, then your payload itself is a bear. Only testing will tell if thats worth it. It does seem that stack space is limited, and I think I remember having been able to make larger arrays with more unrolling. There is a limit to how big you can make an array. And recursion solutions that call themselves for each item at the Nth level had the lowest limit if I do.. recall.. correctly.... much lower.

The next part in revising his solution is just the logistics, its was just a simple refactor to get rid of excessive blocks and code. Join all the var work together and thats it. Since you need a arr to return, once the looping is over, might as well do all your var work on one line first and luckily, three of the four vars have the same initialization. Remember, Javascript can optimize code when joining with , if possible. This also makes for smaller code as well.

PT

Nootka

Answer 5

One more version of createNDimArray using map, apply and bind functions:

function createNDimArray(dims) {
    return dims.length === 1
        ? new Array(dims[0])
        : Array.apply(null, Array(dims[0])).map(createNDimensionalArray.bind(null, dims.slice(1)));
}
createNDimArray([3, 2, 5]); // returns 3x2x5 array

Helli

Answer 6

Creating an ND Array requires cloning nested ND arrays. Accordingly you will need a proper Array.prototype.clone() method and the rest is easy. To my knowledge the following is the simplest and most efficient way in JS.

Array.prototype.clone = function(){
  return this.reduce((p,c,i) => (p[i] = Array.isArray(c) ? c.clone() : c, p),[])
}

function arrayND(...n){
  return n.reduceRight((p,c) => c = (new Array(c)).fill().map(e => Array.isArray(p) ? p.clone() : p ));
}

var NDarr = arrayND(4,4,4,4,"."); // size of each dimension and the init value at the end
console.log(JSON.stringify(NDarr))
NDarr[0][1][2][3] = "kitty"; //access any location and change.
console.log(JSON.stringify(NDarr))

Esmeraldaesmerelda

Came separately into this similar one linear solution stackoverflow.com/a/48013225 [1, 3, 1, 4, 1].reduceRight((x, y) => new Array(y).fill().map(() => JSON.parse(JSON.stringify(x))), 0); which doesn't need a separate clone definition but perhaps has less performance. – Resor

Answer 7

Reason For Anwser

There are good answers here but as JavaScript has changed here is an additional method of tackling this problem with some of the updated features in JavaScript.

function nArray (dem, size=dem, fill=null, currDepth=0) {
    const arr = new Array(size).fill(fill);
    return (currDepth+1 === dem) ? arr : arr.map(i => nArray(dem, size, fill, currDepth+1));
};

Notes

dem is the dimensions of the array.

size is the size of each dimension by default it is the dem value.

fill is the value that will be the default filled value.

currDepth is not to be used it is for the recursive nature of the function.

Gassman

Answer 8

Create n dimensional matrix array with default values

function arr (arg, def = 0){
      if (arg.length > 2){
        return Array(arg[0]).fill().map(()=>arr(arg.slice(1)));
      } else {
        return Array(arg[0]).fill().map(()=>Array(arg[1]).fill(def));
      }
    }

//simple usage -> fills with 0
var s = arr([3,5,8,4])  // 4 dimensions
var t = arr([5,7])  // 2 dimensions

//fill with null
var k = arr([4,7,9] , null)  // 3 dimensions 

Dumfries

Answer 9

If you need to create 4d Array with index from 0 to 4 in the each cluster just do this code:

function createNDimArray(dimensions) {
    if (dimensions.length > 0) {
        var dim = dimensions[0];
        var rest = dimensions.slice(1);
        var newArray = new Array();
        for (var i = 0; i < dim; i++) {
            newArray[i] = createNDimArray(rest);
        }
        return newArray;
     } else {
        return undefined;
     }
 }
var MyArray=createNDimArray([5, 5, 5, 5]);
//returns a 5x5x5x5 array with index from 0 to 4;
MyArray[4][4][4][4]="MyArray 4d MyValue";
alert(MyArray[4][4][4][4]);



//For 5-demension array with this param.: 5x4x3x2x2 -> do this:
var MyArray_5d=createNDimArray([5, 4, 3, 2, 2]);
MyArray_5d[4][3][2][1][1]="MyArray 5d MyValue";
alert(MyArray_5d[4][3][2][1][1]);

Sheela

This seems to be an exact copy of my answer. Am I missing something? – Retaretable

I append the second part: "MyArray=createNDimArray([5, 5, 5, 5]);" .................. My answer made of your answer this is right – Sheela

Answer 10

MULTIDIMENSIONAL ARRAYS can be seen as EMBEDED ARRAYS. See if the following can help.

<script type="text/javascript">"use strict";
   const arr = [
                  ["D1","D2","D3"],
                  [
                     ["T11","T12","T13"],
                     ["T21","T22","T23"]
                  ]
               ];

   for(let k=0;k<arr[0].length;k++)console.log(arr[0][k]);
      // D1
      // D2
      // D3

   for(let k=0;k<arr[1].length;k++)console.log(arr[1][k]);
      // Array(3) [ "T11", "T12", "T13" ]
      // Array(3) [ "T21", "T22", "T23" ]

   for(let k=0;k<arr[1].length;k++)console.log(arr[1][0][k]);
      // T11
      // T12

   for(let k=0;k<arr[1].length;k++)console.log(arr[1][1][k]);
      // T21
      // T22

   for(let k=0;k<arr[1][0].length;k++)console.log(arr[1][0][k]);
      // T11
      // T12
      // T13

   for(let k=0;k<arr[1][1].length;k++)console.log(arr[1][1][k]);
      // T21
      // T22
      // T23
</script>

// // // // // // // // // // // // // // // // // // // //

And from the same point of vue, a MULTIDIMENSIONAL OBJECT !

<script type="text/javascript">"use strict";
   const o = {
               un:{u1:"U1",u2:"U2",u3:"U3"},
               deux:{
                  trois : {d11:"D11",d12:"D12",d13:"D13"},
                  quatre: {t21:"T21",t22:"T22",t23:"T23"}
               }
             };

   let ref = Object.keys(o);
   for(let k=0;k<ref.length;k++)
      console.log(ref[k] , ":" ,
                  Object.values(o)[k]);
      // un   : Object { u1: "U1", u2: "U2", u3: "U3" }
      // deux : Object { trois: {…}, quatre: {…} }
         // quatre: Object { t21: "T21", t22: "T22", t23: "T23" }
         // trois : Object { d11: "D11", d12: "D12", d13: "D13" }

   ref = Object.keys(o["un"]);
   for(let k=0;k<ref.length;k++)
      console.log(ref[k] , ":" ,
                  Object.values(o["un"])[k]);
      // u1 : U1
      // u2 : U2
      // u3 : U3

   ref = Object.keys(o["deux"]);
   for(let k=0;k<ref.length;k++)
      console.log(ref[k] , ":" ,
                  Object.values(o["deux"])[k]);
      // trois  : Object { d11: "D11", d12: "D12", d13: "D13" }
      // quatre : Object { t21: "T21", t22: "T22", t23: "T23" }

   ref = Object.keys(o["deux"]["trois"]);
   for(let k=0;k<ref.length;k++)
      console.log(ref[k] , ":" ,
                  Object.values(o["deux"]["trois"])[k]);
      // d11 : D11
      // d12 : D12
      // d13 : D13

   ref = Object.keys(o["deux"]["quatre"]);
   for(let k=0;k<Object.keys(ref).length;k++)
      console.log(ref[k] , ":" ,
                  Object.values(o["deux"]["quatre"])[k]);
      // t21 : T21
      // t22 : T22
      // t23 : T23

   ref = Object.keys(o["deux"]["trois"]);
   console.log(ref[0] , ":" ,
               Object.values(o["deux"]["trois"])[0]);
      // d11 : D11

   ref = Object.values(o["deux"]["quatre"]);
   console.log(Object.keys(o["deux"]["quatre"])[ref.length-1] ,
               ":" , ref[ref.length-1] );
      // t23 : T23
</script>

Contradistinction