CODEWITHSUNDEEP
javascriptperformancedata-structures
Robert Hurst
Robert Hurst

Reputation: 9092

Faster data access in javascript; for loop and if statement vs deep multidimensional arrays

I'm building a data structure for storing tile data from isometric maps. I'm currently using a multidimensional array with 3 axis.

var tile = tilesArray[X][Y][Z];

I'm wondering if it would be faster to use a for loop to find data

tilesArray[i] = tileObject

function getTile(x, y, z) {

    //loop through the tiles till we find the right one
    for (var i = 0; i < tilesArray.length; i += 1) {

        //grab the tile
        var tile = tilesArray[i];

        //check the tile position to see if it is the one requested
        if (tile.position[0] = x && tile.position[1] = y && tile.position[2] = z) {
            return tile;
        }   
    }

    //if the tile is not found and we fall out of the for loop return false
    return false;
}

So to recap

var tile = tilesArray[X][Y][Z];

vs

var tile = getTile(x, y, z);

Upvotes: 1

Views: 417

Answers (5)

Miquel
Miquel

Reputation: 4829

If there will be mostly random access and a lot of gaps then you could encapsulate an associative array looking like this

var store = {};

function setTile(x, y, z, tile) {
    k = x*1000000 + y*1000 + z;
    store["K" + k] = tile;
}

function getTile(x, y, z) {
    k = x*1000000 + y*1000 + z;
    return store["K" + k];
}

setTile(1, 7, 5, "1-7-5");
alert (getTile(1,7,5));

It is not as fast as the multidimensional array, but it is definitely faster than iteration and an space saver in comparison to the array.

The example would support indexes up to 999 though

Upvotes: 1

Raynos
Raynos

Reputation: 169383

Benchmark

The object is 2/3 times as slow in chrome 12.

The object is 1000 times slower in firefox 4. (Basically arrays are really fast in FF4, about a 1000 times faster then chrome)

Becuase the Object is nice and OO and doesn't involve having a 3 dimensional array with a LOT of gaps I would recommend using it as its just generally a better way to store data.

Upvotes: 0

Martin Strandbygaard
Martin Strandbygaard

Reputation: 273

Array indexing is approx. 3 times faster, using the test below and executed in node.js (Google V8 engine). It indexes the same element. You definitely want to try indexing random elements to get a better feel for how they compare.

var tilesArray = createTileArray();

function createTileArray()
{
    var rank = 1000;
    var start = new Date();

    // Define
    var ar = new Array(3);

    // Create
    for (var i=0; i < 3; i++)
    {
        ar[i] = new Array(rank);

        for (var j=0; j < rank; j++)
        {
            ar[i][j] = new Array(rank);
        }
    }

    // Fill
    for ( var i = 0; i < 3; i++) {
        for ( var j = 0; j < rank; j++) {
            for ( var k = 0; k < rank; k++) {
                ar[i.valueOf()][j.valueOf()][k.valueOf()] = 3;
            }
        }
    }

    var end = new Date();

    console.log("Created array in: " + (end-start) + "ms");

    return ar;
}

function getTile(array, x, y, z) {

    // loop through the tiles till we find the right one
    for (var i = 0; i < array.length; i++) {

        // grab the tile
        var tile = array[i];

        // check the tile position to see if it is the one requested
        if (tile[0] === x && tile[1] === y && tile[2] === z) {
            return tile;
        }   
    }

    // if the tile is not found and we fall out of the for loop return false
    return false;
}

function arrayIndexing(array, loopCount)
{
    var start = new Date();

    for (var i = 0; i < loopCount; i++) {
        var elem = array[1][2][3];
    }

    var end = new Date();
    console.log("Array indexing in: " + (end-start) + "ms");
}

function loopIndexing(array, loopCount)
{
    var start = new Date();

    for (var i = 0; i < loopCount; i++) {
        getTile(array, 1, 2, 3);
    }

    var end = new Date();

    console.log("Loop indexing in: " + (end-start) + "ms");
}

var loopCount = 1000000;

arrayIndexing(tilesArray, loopCount);
loopIndexing(tilesArray, loopCount);

Upvotes: 0

Miquel
Miquel

Reputation: 4829

It depends on the type of access you will do really. Will it be mostly insertions and then sequential access? Then the linear storage such as linked list with a access function might be better.

Will be mostly individual random access? then array access is definitely fastest.

Upvotes: 0

Seldaek
Seldaek

Reputation: 42026

Direct array access is the fastest you can get in most languages I think, especially when compared to a loop + function call. No offense, but this sounds like a bad idea :) Keep it as is.

Upvotes: 0

Related Questions