使用两个比较器时阻止递归调用

Question

我有一个PartiePos类型的项目列表。。。简单地说，就是

{
ID: string
}

现在，我有另外两个类型为string的项目列表。

这里列出了所有三个列表：

items = [{ID: "123"}, {ID: "234"}, {ID: "345"}, {ID: "456"}, {ID: "567"}]
assigned = ["123", "345"]
disabled = ["567", "234"]

我想根据这个方案对它们进行分类：

• 始终保持项目的初始顺序
• 如果已分配，请将其放在最后，但保留项目的初始顺序
• 如果处于禁用状态，则将其放在分配的后面的末尾，但保留项目的初始顺序

将我的列表解析为这个排序输出：

"456"
"123"
"345"
"234"
"567"

我通过将这两个比较器应用于我的列表排序来实现这一点：

const comparatorA = (a: PartiePos, b: PartiePos) => {
if (assigned.includes(a.ID) && assigned.includes(b.ID)) {
return 0
}
if (assigned.includes(a.ID) && ! assigned.includes(b.ID)) {
return 1
}
if (! assigned.includes(a.ID) && assigned.includes(b.ID)) {
return -1
}
}
const comparatorD = (a: PartiePos, b: PartiePos) => {
if (disabled.includes(a.ID) && disabled.includes(b.ID)) {
return 0
}
if (disabled.includes(a.ID) && ! disabled.includes(b.ID)) {
return 1
}
if (! disabled.includes(a.ID) && disabled.includes(b.ID)) {
return -1
}
}
[...]
return items.sort(comparatorA).sort(comparatorD)

但是排序非常慢，并且阻塞了我的站点，开发控制台告诉我有一个递归突变，这导致了javascript的阻塞。

知道如何改进吗？

Answer 1

这里不需要排序，因为这需要O(n log n)时间。您可以过滤掉禁用和分配的项目，然后只连接这些项目：

const items = [{ID: "123"}, {ID: "234"}, {ID: "345"}, {ID: "456"}, {ID: "567"}];
// If these are long, use a JS `new Set` object for fast lookup;
const assigned = ["123", "345"];
const disabled = ["567", "234"];
// just those that keep their regular place
const withoutAssignedAndDisabled = items.filter(x => !assigned.includes(x.ID) && !disabled.includes(x.ID));
// concat the assigned and then disabled
const result = withoutAssignedAndDisabled.concat(
items.filter(x => assigned.includes(x.ID))
).concat(
items.filter(x => disabled.includes(x.ID))
);

Answer 2

我想出了一个有趣的方法，回来发布它，发现Benjamin Gruenbaum给出了更好的答案。

但这仍然很有趣，我认为可能对许多场景有用，所以我仍然会发布它：

const using = ((table) => (assigned, disabled) => (
{ID: x}, {ID: y}, 
kx = assigned .includes (x) ? 'a' : disabled .includes (x) ? 'd' : '_',
ky = assigned .includes (y) ? 'a' : disabled .includes (y) ? 'd' : '_',
) => table [kx] [ky])({
//x↓  y→
a: {a:  0, d: -1, _:  1},
d: {a:  1, d:  0, _: -1},
_: {a: -1, d:  1, _:  0}
})
const items = [{ID: "123"}, {ID: "234"}, {ID: "345"}, {ID: "456"}, {ID: "567"}]
const assigned = ["123", "345"]
const disabled = ["567", "234"]
console .log (items .sort (using (assigned, disabled)))

.as-console-wrapper {max-height: 100% !important; top: 0}

在这里，我们对从assigned和disabled类别派生的简单键使用表查找(假设它们互斥(。

为了处理同一类别中有两个的情况，我们利用了所有现代JS引擎都是稳定的，并且只返回0这一事实。

很明显，我们可以使用数组数组而不是类别字母来实现这一点，但我认为这更清楚，如果我们愿意，它将允许我们更明确地选择使用"；指定"/"衍生的"/"两者都不是"；代替"；a"/"d"/&quot_&"；。在任何情况下，结果矩阵都需要是反对称的才能有意义。

很容易想象这样的泛化，它接受一个函数，该函数生成一个键和一个表，解释任何类别对的排序结果。但既然Benjamin已经给出了明确的答案，我就改天再说了。