Re-instantiating the interesting bits from the other thing:

Time complexity of unsorted array equality operations. Go!

@iiii
O(n log n)
https://stackblitz.com/edit/...

@iiii
As stated in the question, unsorted ;)

Set is naturally deduplicating in js. It's an iterable with O(1) lookup. So yeah, needs to be isolated. Need to have an identity as well.

@iiii
True. Though this is a mutable array context.Trying to build a comparator is going to be naive or get complex rather quickly. Probably need to include a strategy and comparator for each as well to make it flexible.

@iiii
Modified it to make it a little more robust. This doesn't implement strategies or ordered, but will conform to the "equals" definition most equals algorithms use: all members in the left array are present in the right.

Runs in O(3n log n) time, but that's still n log n ;)

The fun bit here is using maps to create a monoid index of both sides, since the unordered comparison still needs to check a pairwise identity of (value, cardinality).

https://stackblitz.com/edit/...

@iiii
Maybe, it's late AF, I'll have to paper it out in the morning. Just watching some load testing. There's also a stupid math novelty version as well:

https://stackblitz.com/edit/...

If you assume that the cardinalities must match, but the order doesn't matter, then you know a few things for certain:

- the length of all items in all arrays must be divisible by the number of sources evenly (obv, they're just pages at that point)
- the number of times each value appears must also be evenly divisible by the number of sources

With that in hand, you get the example in the link. It can compare two arrays. It can also compare n-arrays.

Could use an identity selector to deal with complex objects, or custom definitions, but that's fine. And potentially breaking. But fine.

How is this different then sorting the array?

case1: there are exactly 2 equal elements, in an nlength non sorted array. find it.
case2: there aren't any equal elements in an nlength non sorted array.
case3: there are k equal element pairs in an nlength (n>=k) no sorted array. find all k pairs.

reduce as follows: sort (nlogn) then iterate and compare adjacent elements (n) - done in O(nlogn).

@magicMirror
The topic was array equality. They're different algorithms. The last solution is O(n+m).

@iiii
The even var was an intermediary analysis step I forget to delete :p Stackblitz doesn't have dead code location.

Basically just roll through, perform some checks, produce a tuple of val,instance count for each distinct value. If any values have less than evenly divisible instance count, it doesn't match.

Consider these two array series
set a: [1,1,2,2] [2,2,1,1] (positive case)
set b: [1,1,2,2] [2,2,1,1] [2,3,2,1] (negative case)

To determine if they're memberwise equal, ignoring their order:

- the sum cardinality of all members must be evenly divisble by the number of arrays:

a: 4,4 -> 8 -> 8 mod 2 -> 0 = evenly divisible
b: 4,4,4 -> 12 -> 12 mod 3 -> 0 = evenly divisible

- the sum instance count of all members must also be evenly divisible by the number of arrays

a: 1,1,2,2,2,2,1,1 -> [1,4],[2,4] -> [4,4] -> [4 mod 2, 4 mod 2] -> [0,0] = evenly divisible
b: 1,1,2,2,2,2,1,1,2,3,2,1 -> [1,5],[2,6],[3,1] -> [5,6,1] -> [5 mod 3, 6 mod 3, 1 mod 3] -> [2,0,1] = not equal

@iiii
Because I was bored in the middle of the night working late. Why stop with "are 2 arrays equal" when you can have "are n arrays equal"

@iiii
Good catch, need to handle the basal case. Sleepy code is sleepy. This is exploratory :)

@iiii
That's the bit that I was missing. Any parity also fails. Ah, well, previous case still works thankfully. Just needs to be unique to a given array:

[1,1,1,2].equals([1,2,2,2]).dump(v => `expect false: ${v}`);// is true, derp

@iiii
Yep, that was solution 2/5. I'm just bored-noodling the extents of the problem domain searching for relational novelty.