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

Question

我有一个 PartiePos 类型的项目列表...只需使用该方案：

{
    ID: string
}

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

这里是所有三个列表：

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

我想根据这个方案对它们进行排序：

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

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

"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

我想出了一个有趣的方法，回来发布它，发现本杰明·格伦鲍姆给出了更好的答案。

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

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}

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

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

显然，我们可以使用数组数组而不是类别字母来做到这一点，但我认为这更清晰，并且如果我们愿意，它可以让我们更加明确，选择使用“分配”/“派生”/“两者都不是”代替“a”/“d”/“_”。无论如何，结果矩阵必须是反对称的才有意义。

很容易想象它的概括，它接受一个生成键的函数和一个解释任何类别对的排序结果的表。但既然本杰明已经给出了明确的答案，那我就留到另一天再说吧。