Re:Hoare’s Rebuttal and Bubble Sort’s Comeback
by kazinator on Sunday May 31, 2020 @10:39AM
(#23369856)
Intersection is calculable in amortized O(M + N) with hashing.
Build hash table in O(N) of the smaller set, then probe M entries of the larger in the table.
If we rely on sorted order, we can make it a requirement/invariant that these sets are maintained in sorted order. Membership in a group rarely changes; if a user is added to a new group, that can be inserted in order. A binary heap structure could be used to keep these objects in array form, while allowing better than linear insertion.
In such a system, sorting the two sets of IDs allows you to implement an O(N) or O(M log N) algorithm depending on the relative sizes of the two sets. If one set is much smaller than the other, then you can just iterate the smaller set and binary search the larger set. If the two sets are comparable in size you can walk a cursor in each.
These IDs are probably small -- 32 bits will generally do. That's a "pure scalar type that is native to the machine".
Mind you, these are smallish arrays in practice. Typically you might see users with a few hundred group memberships and access controls with a few tens of grants. But you might have many users, and many access controls, so many sorts to perform.