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/...

@SortOfTested wait, are you thinking about arrays as unordered sets or as ordered sets? Because for ordered set (where order matters) the comparison will be O(n): check each item 1 by 1 until you find a first non equal pair.

also, I'm not aware of how JS function Set() works. Does it remove all repeating elements? In that case your function probably has a bug if arrays have several but different amount of each element.

No, I've checked. Set() probably makes pairs of <element, amount>

@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.

@SortOfTested unsorted does not imply unordered ;)

Like, in most contexts [1,2,3] is not equal to [3,2,1] as in your example, but [1,2,3] is equal to another array containing [1,2,3] in the same order

@SortOfTested actually, I've made some tests with your code, and was not able to reproduce the defect I was thinking about.

Not sure how those functions work in JS, so that's that.

@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/...

@SortOfTested wow, that's pretty complicated looking function. But looks pretty effective to me: O(n) for each Array->Map transformation and O(n) for comparing. I don't understand where log(n) comes from. I'm missing something.

Overall the task seems like those arrays should have been maps in the first place. 🤔

@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).

@SortOfTested I don't get your last snippet. It has a lot of TS syntax I don't know (never worked with TS). And what's that about evenness?

@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

@SortOfTested I don't get why there are three arrays to compare now 🤔🤔🤔

@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"

also, check out this example:

a=[1,1]

b=[2,2]

a.equals(b) will return 'true'

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

It seems to me like the only optimal solution would be to transform arrays into sets and then compare them. If you want to compare several, then compare every one to the first array and you'll get everything in one pass.

@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.