0

I'm storing objects for a grid in a two dimensional array. Since the grid is hexagonal, it is much easier to use a coordinate system that is centered at (0, 0) and ranges from -r to r.

According to this thread, apparently negative indices in an array aren't real indices, but actually properties of the array.

I have two questions:

  1. Does this affect running time speed of operations on the array? Would negative indices still be accessed in constant time?

  2. How do I delete negative indices? I tried using splice, but it deleted the wrong indices (shown below).

Community
  • 1
  • 1
user244145
  • 73
  • 1
  • 11
  • most built-in array methods like forEach, sort, splice, pop, etc won't work with non-positive integer indices. it will also be much slower to iterate in decent browsers. – dandavis Jan 04 '14 at 04:11

1 Answers1

0

  1. JavaScript object is essentially a glorified hashmap. Properties should be accessed in constant time.

  2. You should be able to delete a property using delete keyword. For example delete a["-1"]. Any propery of a JavaScript object can be accessed using either dot notation or bracket notation.

Zong
  • 6,160
  • 5
  • 32
  • 46
markovuksanovic
  • 15,676
  • 13
  • 46
  • 57
  • 1
    Note that modern JavaScript implementations are optimized so nonnegative integer properties are much more efficient that other types of properties. – Raymond Chen Jan 04 '14 at 04:23
  • Best way to prove is to measure. Here is a js perf which measures access using property (I.e. Negative index) vs array index. The results are not very different. Property access was even faster in my case http://jsperf.com/array-vs-object-loop – markovuksanovic Jan 04 '14 at 05:42
  • On a side note, put, get and search hashmap operations all run in O(1) time. This is same complexity as accessing an array at some index. The only overhead that hasmap could have is computing the hash function. But based on the results above this is highly optimized too. – markovuksanovic Jan 04 '14 at 05:56
  • Yes, they are both O(1), but the constant is much larger for dictionary lookups than for direct array indexing. [See this talk](https://www.youtube.com/watch?feature=player_detailpage&v=XAqIpGU8ZZk#t=17m24s). At 18:11, the speaker notes that dictionary mode is "considerable less efficient and a case you want to avoid." – Raymond Chen Jan 04 '14 at 07:26
  • @RaymondChen I agree, the constant should be larger but access time depends on lots of other things (data locality, cache, etc). Also the talk is from 2012. It's 2014 today. There were lots of improvements in JS engines since then. Anyway, the only true way to find out if property access will work for you is to code sth that will use similar patterns that you will use in your code and see how that performs. As you can see, property access can be faster then indexing into an array, at least in some cases. – markovuksanovic Jan 04 '14 at 08:33
  • Doesn't the delete keyword leave an undefined element? Disfated said that in [this](http://stackoverflow.com/questions/7142890/js-remove-an-array-element-by-index-in-javascript) thread. – user244145 Jan 04 '14 at 19:38
  • @user244145 As per MDN, delete is used to remove property from an object - https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/delete – markovuksanovic Jan 04 '14 at 23:33