blocking recursive call when using two comparators

user_6539837 0
Viewed 34

I have a list of items of type PartiePos ... simply with that scheme:

{
    ID: string
}

Now, I have two further lists of items of type string.

Here all three lists:

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

I want to sort them according to this scheme:

  • Always keep initial order of items
  • If in assigned, put it to the end but keep initial order of items
  • If in disabled, put it to the end behind assigned, but keep initial order of items

Would resolve my lists into this sorted output:

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

I achieve this by applying these two comparators to my list sorting:

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)

But the sorting is quite slow and blocks my site, the dev console tells me that I have a recursive mutation and this causes blocking of javascript.

Any idea how to improve this?

typescript comparator recursion blocking javascript
2 Answers

There is no need to sort here since that would take O(n log n) time. You can filter out the disabled and assigned items, then concat just those items:

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))
);
user_13481950

I came up with an interesting approach, came back to post it, and saw that Benjamin Gruenbaum had given a much better answer.

But this is still interesting, and I think might be useful for a number of scenarios, so I'll still post it:

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}

Here we use a table lookup on simple keys derived from the assigned and disabled categories (under the assumption that they are mutually exclusive).

To handle the cases where we have two in the same category, we take advantage of the fact that all modern JS engines are stable and just return 0.

Clearly we could do this with an array of arrays instead of the category letters, but I think this is clearer, and it would allow us to be more explicit if we like, choosing to use "assigned"/"derived"/"neither" in place of "a"/"d"/"_". In any case the matrix of results needs to be anti-symmetric to make sense.

It's easy to imagine a generalization of this that accepts a function that generates a key and a table explaining the sort result for any pair of categories. But since Benjamin already gave the definitive answer, I'll leave that for another day.

user_12436410
Related