More specifically, am I actually using arrays here. I never declared the size of the array, I just start adding numbers to the chosen index.
To me, this is suspicious, and makes me think that JavaScript might be using a hash map instead of an array, which would involve more computation.
Can I make JavaScript use a fixed array over a dynamic array over a hash?
Is there a way to verify the underlying data structure without digging through the code base?
var generate = function(n) {
const matrix = [[1], [1, 1]];
// base case : n = 1
if(n === 1) {
return [[1]];
}
// base case : n = 2
if(n === 2) {
return matrix;
}
// first iterative case : n = 3
// be careful of off by one error here
// n is number of rows (3), but i is 0 based (2)
for(let i = 2; i < n; i++) {
// add empty row
matrix[i] = [];
for(let j = 0; j <= i; j++) {
// if first or last element set to 1
if( j === 0 || j === i ) {
matrix[i][j] = 1;
} else {
matrix[i][j] = matrix[i-1][j-1] + matrix[i-1][j]
}
}
}
return matrix;
};
makes me think that JavaScript might be using a hash map instead of an array, which would involve more computation.
Without looking at the actual code, this is true. In JavaScript an array is just a plain object (i.e. dictionary) with additional features. The indexes are properties that happen to represent non-negative integer (in a certain range). Although the engine might store the array as a consecutive array (as you would expect in C-style languages), the engine is free to really use a hash table like it would for any other object. It may even decide at run time to switch from one internal representation to another (transparent to the code).
Can I make JavaScript use a fixed array over a dynamic array over a hash?
Yes, there are typed arrays, like Int16Array