我對如何在后臺實作陣列有一些限制。最多只能有 32 個元素（1、2、4、8、16、32）的 2 次冪連續元素。因此，這對如何以最佳方式存盤 7 或 15 個元素等的陣列元素設定了一些限制。從 1 到 32 的完整示例串列在這里，但接下來是一些示例：
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 是因為與將其放入適當的樹相比，僅具有 null 值占用的空間更少（或者使用 null 意味著更少的遍歷步驟）。
在 32 處，它應該嵌套模式，如下所示：
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
tree關鍵只是表明它是一個鏈接到另一個陣列的地址。
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.
uj5u.com熱心網友回復：
在 JavaScript 中，您當然會呼叫.flat(Infinity)，這將回傳完全展平的陣列。但我會假設這些限制：
push除了and之外不使用陣列方法pop（當您針對自定義的更簡單的語言時）- 不使用遞回
- 不使用生成器或迭代器
我希望使用堆疊是可以接受的。然后我會想到一個堆疊，其中每個堆疊元素都由一個陣列參考和該陣列中的一個索引組成。但是為了避免“復雜”的堆疊元素，我們還可以使用兩個堆疊：一個用于陣列參考，另一個用于這些陣列中的索引。
為了實作“迭代”，我將使用一個回呼系統，這樣你就可以指定每次迭代應該發生什么。回呼可以是console.log，以便迭代值只是輸出。
這是一個實作：
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);轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424338.html
上一篇：如何使樹模式適合約束，但演算法是通用的而不是硬編碼的？
下一篇：尋找減少分數的最有效方法