0

I have a n*n*n array in javascript, in which i need to perform a LOT of access.

I don't need to access all elements sequentially, but at specific positions only. I also want, if possible, not to allocate all the memory of the array cells until it's used (other it would take several MB of memory directly).

I'm looking for the most efficient way to do so. I tried to use a dictionnary indexed by a built key ( x + '#' + y + '#' + z ) but it's cleary not efficient enough.

Could you suggest some other efficient ways to achieve this ?

Arun
  • 116,683
  • 26
  • 284
  • 387
Sebastien
  • 682
  • 1
  • 14
  • 26
  • 1
    What's wrong with `yourArray[0][1][2]`? – gen_Eric Feb 27 '13 at 20:45
  • 2
    @RocketHazmat It's clearly not efficient enough.... ;) – jondavidjohn Feb 27 '13 at 20:46
  • Dictionary approach is not efficient enough? I've got bad news for you: there is no better way to access data ( at least in general ). By the way: several MB of memory is **nothing** for computers nowadays. :D – freakish Feb 27 '13 at 20:46
  • 2
    if "dictionary" is not a good enough solution for you try changing your job, may solve your problems...at all – Toping Feb 27 '13 at 20:49
  • My main problem is that javascript use always string as indexes, which leads to a lot of overhead in the cell access. If i can find something to avoid that behavior, i'll probably have much more better performances. – Sebastien Feb 27 '13 at 21:00
  • @Seb37: `use always string as indexes`... what are you talking about? – gen_Eric Feb 27 '13 at 21:08
  • 1
    Have a look here: http://stackoverflow.com/questions/2002923/javascript-using-integer-as-key-in-associative-array – Sebastien Feb 27 '13 at 21:11
  • 1
    @Seb37 you misunderstood, they return string inside it, but there is always a integer key for each array. – Toping Feb 27 '13 at 21:15
  • @Seb37: Arrays and Objects are different. What *exactly* do you have, and *how exactly* are you trying to access it? – gen_Eric Feb 27 '13 at 21:24
  • 2
    @Seb37: No, that's only the semantics. Internally, the engine will of course optimize and use true arrays. Do you have actual performance issues or is this a case of premature optimisation? – Bergi Feb 27 '13 at 21:26
  • Er, you guys are wrong and Seb37 is right. Arrays in javascript ARE objects, and their indices are all strings. `var a = []; a[3] = 'test'; for(k in a) alert(typeof k);` This alerts 'string'. – Colin DeClue Feb 27 '13 at 21:39
  • @ColinDeClue you get a value of array using ["1"] or [1]? thats right... – Toping Feb 27 '13 at 22:01
  • @ColinDeClue: Have you read my comment? Of course, if you did `var a = []; a.someprop = 'test'`, then it gets represented as a hashmap. And yes, when enumerating object properties those are strings by specification. – Bergi Feb 27 '13 at 22:02
  • @Ark You can also do `var a = {}; a[3] = 'test'` and get the value with an integer that way. – Colin DeClue Feb 27 '13 at 22:07

2 Answers2

1

There's no faster way to access objects than a dictionary method, I'm afraid, because that's what everything in Javascript is, really. To not allocate the memory, you can use an object instead of an array:

var x = {};
var key = x + '#' + y + '#' + z;
x[key] = 'some value';

This will at least give you your memory concern, but I'm not sure it's really much of a concern. (Also, I'm not even sure that if you use an array it WILL allocate the memory, because I'm unfamiliar with memory allocation in Javascript).

Colin DeClue
  • 2,194
  • 3
  • 26
  • 47
  • The question is how that memory is allocated then by the dictionary. It might be much better with arrays, if those are packed and accessed not too randomly. – Bergi Feb 27 '13 at 21:59
  • And how are they represented in the RAM? There's a lot of difference, even if arrays act `instanceof` Object. Also, a multidimensional lookup (regardless whether array or object) is very different from a onedimensional as you proposed. – Bergi Feb 27 '13 at 22:06
  • I don't know how they are represented in the RAM. Can you link me to a discussion on it? That'd be really interesting. Also, based on his description I don't think he actually needs a multidimensional lookup, since he said he doesn't need to look at it sequentially, just at specific points. – Colin DeClue Feb 27 '13 at 22:08
  • http://www.html5rocks.com/en/tutorials/speed/v8/ contains some useful information. You can find much more on the web with the right search terms. – Bergi Feb 27 '13 at 22:19
  • Thanks! Based on that link, it looks like his requirements will produce a dictionary element, rather than a 'fast element', since it seems to be sparse data, rather than compact data. But it seems like a dictionary is what he wants, anyway, memory wise. (Of course, if dictionaries are obviously not efficient enough, I don't know what to tell him). – Colin DeClue Feb 27 '13 at 22:26
0

I think your multidimensional array is perfectly fine. If created sparse, it will not eat up all the memory, and act more like a simple "dictionary" object - you could use nested objects as well. Yet, I'd propose that the nested lookup will be faster than in a huge dictionary, since the hash function gets simpler with less keys. Also, loading or iterating a full array from the innermost dimension will be noticably faster than querying each single item from the huge dictionary.

After all, if you don't actually experience any essential performance issues use what you find easier to write/read/use.

Bergi
  • 630,263
  • 148
  • 957
  • 1,375
  • If I got my math correct for n=1000 if you put a boolean in array[n-1][n-1][n-1] you allocate 3814 MB – naugtur Mar 02 '13 at 09:09
  • How that? I don't think 3 objects with 3 properties will need more than a few dozen bytes. – Bergi Mar 02 '13 at 13:01
  • My bad, I counted it with an assumption that you fill all the arrays with one element and didn't state it clearly, anyway `var a=[]; a[1000]=true` should fill up up 1001*4 bytes of memory – naugtur Mar 03 '13 at 10:08
  • Yes, that's the assumption. Yet sparse arrays will unlikely [eat up all the memory](http://stackoverflow.com/q/4524067/1048572), see also http://stackoverflow.com/q/1510778/1048572 – Bergi Mar 03 '13 at 11:06