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

Question

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

{
    ID: string
}

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

这里是所有三个列表：

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

我想按照这个方案对它们进行排序：

始终保持项目的初始顺序
如果在 assigned 中，将其放在末尾但保留项目的初始顺序
如果禁用，将其放在后面分配的末尾，但保持项目的初始顺序

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

"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

我想到了一个有趣的方法，然后回过头来 post，发现 Benjamin Gruenbaum 给出了更好的答案。

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

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}

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

为了处理我们在同一类别中有两个的情况，我们利用了所有现代 JS 引擎都是 stable 而只是 return 0 的事实。

很明显，我们可以使用数组数组而不是类别字母来做到这一点，但我认为这更清楚，如果我们愿意，它可以让我们更明确，选择使用“分配”/“派生” “/”两者都不是“a”/“d”/“_”。在任何情况下，结果矩阵都需要 anti-symmetric 才有意义。

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

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

blocking recursive call when using two comparators

javascript

recursion

blocking

comparator

typescript