Return to Answer

• 1

• 34.2k
• 5
• 70
• 267

• 22.8k
• 2
• 16
• 40

##Zero based indexing

Counting: when the index, or the position, is dependent on the item. Count from one. (Zero-based index is mathematically wrong.)

I will disagree. The index does not represent a count but rather it is a position. When we measure something we start at 0. For example a length of 5 units. Unit 0 the 1st unit is at 0 to < 1, and the last unit, the 5th is at 4 to < 5. The set of 5 units does not contain the unit 5.

It is not mathematically wrong to use zero based indexing, what is wrong is using the index to represent a count.

##Array V Grid AKA hash table

Grid: when the index, or the position, is independent on the item. (e.g. JavaScript array)

I think you understanding of how arrays work is leading to some bad assumptions.

###Arrays

Computers use RAM that is a continuous array of addresses. We use arrays because they are very fast when we need to get or set a item at an index.

To locate an item we get the RAM address of the array and add the index multiplied by the size of each item (JS arrays hold references so all array items are the same size) . In one addition and multiplication (a shift if item size is a power of two) we have the memory address of the data we want.

Almost all modern CPUs have special instructions (indexed addressing) to speed up array use.

###Hash table

A grid is a little more complicated.

As the index can be any value we can not just offset a RAM address to find an item. We need to know where the item associated with an index is in RAM. That means that another array is needed to hold all the indexes and RAM addresses.

So if you want the item of grid index 10000000, we need the address of the index 10000000 which must be found by searching the array of indexes one at a time. Then we can get the RAM offset of the item we are after.

However computers have been around for a long time and some cleaver people have come up with ways to make "grids" somewhat faster. In javascript we call them Map in computer science we use the term hash table.

Hash tables avoid the need to search for the index by applying a hash function to the index (key). This provides an offset that we can use to get the RAM address of the data we are after.

Still slower than an array as the hash function needs to be applied each time we index into the table, its a lot faster than searching all indexes each time we want an item.

###When JS arrays are not arrays.

On a side not. JavaScript arrays come in two flavors

1. Dense arrays, each item is held one after the other in a continuous section of memory.
2. Sparse arrays. Sparse arrays look from the code perspective like dense array, but under the hood sparse array are actually hash tables.

A dense array is converted to a sparse array if you add an item above the array length. Different engines have different rules but generally its a bad idea to add items to an array at random indexes (as you do in your grid sort)

##Review

I am not going to review your code as I think its is mute if you consider the above information.

I will say, you saw some institutionalized flaws and you created a better solution (sadly your assumptions were off). You demonstrate an initiative and a healthy skepticism of the status quo.

Most people will just keep at the same old same old and nothing great ever comes from that.

Keep at it.