I have some constraints on how an array would be implemented under the hood. There can only be power-of-two contiguous elements up to 32 elements (1, 2, 4, 8, 16, 32). Therefore, this puts some constraints on how to optimally store the array elements of like 7 or 15 elements, etc.. The full list of examples from 1 to 32 is here, but some examples are next:
base-3
a
b
c
null
base-5
a
b
c
tree
d
e
base-6
a
b
c
d
e
f
null
null
...
base-10
a
b
c
d
e
f
g
tree
h
i
j
null
...
base-13
tree
a
b
c
d
tree
e
f
g
h
tree
i
j
k
l
tree
m
...
base-16
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
base-17
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
tree
p
q
Null is chosen in a few cases because it would take up less space to just have a null value than to make it into an appropriate tree (or using null would mean less traversal steps).
At 32, it should nest the pattern, like this:
base-33
tree
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
aa
ab
ac
ad
ae
af
tree
ag
The tree key just shows it is an address linking out to another array.
I started to implement an algorithm to fetch all the values from this tree system below. I didn't find a way of generically making it so I didn't have to write each of 32 functions. If you know of an abstract/generic way to write this, that would be cool to know (doesn't need to exactly match how I divided up the arrays, but it should be close to the same idea). But that is not the main question. The main question is simply how you would make this function repeat for arrays larger than 32. How do you make this algorithm (a loop/iterative algorithm, not using recursion) so that it can fetch up to billions of items from such a tree, and know how to traverse the custom array structure?
const map = [
get1,
get2,
get3,
get4,
get5,
get6,
get7,
get8,
get9,
get10,
get11,
get12,
get13,
get14,
get15,
get16,
get17,
get18,
get19,
get20,
get21,
get22,
get23,
get24,
get25,
get26,
get27,
get28,
get29,
get30,
get31,
get32,
]
// how to make getItems handle arrays larger than 32 in length?
function getItems(array) {
return map[array.length](array)
}
function get1(array) {
return [
array[0]
]
}
function get2(array) {
return [
array[0],
array[1],
]
}
function get3(array) {
return [
array[0],
array[1],
array[2],
]
}
function get4(array) {
return [
array[0],
array[1],
array[2],
array[3],
]
}
function get5(array) {
return [
array[0],
array[1],
array[2],
array[3][0],
array[3][1],
]
}
function get6(array) {
return [
array[0],
array[1],
array[2],
array[3],
array[4],
array[5],
]
}
function get7(array) {
return [
array[0],
array[1],
array[2],
array[3],
array[4],
array[5],
array[6],
]
}
function get8(array) {
return [
array[0],
array[1],
array[2],
array[3],
array[4],
array[5],
array[6],
array[7],
]
}
function get9(array) {
return [
array[0],
array[1],
array[2],
array[3],
array[4],
array[5],
array[6],
array[7][0],
array[7][1],
]
}
function get10(array) {
return [
array[0],
array[1],
array[2],
array[3],
array[4],
array[5],
array[6],
array[7][0],
array[7][1],
array[7][2],
]
}
function get11(array) {
return [
array[0],
array[1],
array[2],
array[3],
array[4],
array[5],
array[6],
array[7][0],
array[7][1],
array[7][2],
array[7][3],
]
}
function get12(array) {
return [
array[0][0],
array[1][1],
array[2][2],
array[3][3],
array[4][4],
array[5][5],
array[6][6],
array[6][7],
array[7][0],
array[7][1],
array[7][2],
array[7][3],
]
}
I am lost right at the beginning. It could be implemented with recursion, and perhaps from that I can figure it out as an imperative form.
function getItemsRecursive(tree) {
if (tree.size <= 32) {
return map[tree.size](tree)
}
// ... I am lost right at the beginning.
if (tree.size === 33) {
return [
...getItemsRecursive(tree[0]),
tree[1][0]
]
} else if (tree.size === 34) {
// ....?
}
}
The tree.size is just pseudocode. You can just do pseudocode if you'd like, but I am doing this in JavaScript.
CodePudding user response：
In JavaScript you would of course call .flat(Infinity), which would return the completely flattened array. But I'll assume these constraints:
- No use of array methods besides
pushandpop(as you target a custom, simpler language) - No use of recursion
- No use of a generator or iterator
I hope the use of a stack is acceptable. I would then think of a stack where each stacked element consists of an array reference and an index in that array. But to avoid "complex" stack elements, we can also use two stacks: one for array references, another for the indices in those arrays.
To implement "iteration", I will use a callback system, so that you can specify what should happen in each iteration. The callback can be console.log, so that the iterated value is just output.
Here is an implementation:
function iterate(arr, callback) {
let arrayStack = [];
let indexStack = [];
let i = 0;
while (true) {
if (i >= arr.length || arr[i] === null) {
if (arrayStack.length == 0) return; // all done
arr = arrayStack.pop();
i = indexStack.pop();
} else if (Array.isArray(arr[i])) {
arrayStack.push(arr);
indexStack.push(i 1);
arr = arr[i];
i = 0;
} else {
callback(arr[i]);
i ;
}
}
}
let arr = [1, 2, 3, [4, 5]];
iterate(arr, console.log);