Hacker News Reader

Comment by kelseyfrog | Hacker News Reader

Not just groups, magmas, semigroups, monoids, &c.

I acquired a taste for algebraic structures and category theory by way of Scala+cats. While I no longer work in that space, the concepts are universally applicable.

Just last week, I shared with teammates in our weekly symposium how merging counts was an associative operation, and how knowing that directly relates to being able to divide and conquer the problem into an implicit O(log n) operation. Being able to identify the operation as forming a semigroup directly contributed toward being effective in that problem space.

The abstractness of the concepts is a double-edged sword. It allows them to be broadly applied, but it also requires more effort on the part of the observer to form the connection.

View on HN

Can you expand a bit on what the problem was and what the discussion was like and solution, if possible.

Thanks!

For sure. The problem was writing an np.unique[1] that could handle large datasets. Specifically, the solution involved chunking the dataset, mapping np.unique across chunks, and then combining chunks. Merging the counts result is an associative operation and merging them in a tree-like computational graph implies O(log n) merges. The end result was being able to perform the calculation in seconds whereas the previous duration was days to weeks. Going from O(n) to O(log n) is magic.

Specifically this is work related to implementing large dataset support for the dedupe library[1]. It's valuable to be able to effectively de-duplicate messy datasets. That's about as much as I can share.

1. https://numpy.org/doc/stable/reference/generated/numpy.uniqu...

2. https://github.com/dedupeio/dedupe/blob/main/dedupe/clusteri...

Actually what you are using is an equivalence relation and you are generating the equivalence classes of your set, "your" associativity is transitivity. Whenever you are comparing something it's almost always better to think of it as a relation instead of an algebraic structure. So you already know beforehand that your algorithm should be reflexive, symmetric and transitive (in theory, of course with computers there is numerics involved ;)

The steps to the solution are something like:

- I need all distinct elements of X

- Oh, that's a quotient set (the partition) of X by a/the equivalence relation (`==`)

- so my algorithm must be reflexive (yeah, trivially), symmetric (not so helpful) and transitive - now this I can use (together with the symmetry)

It's generally easier if you know beforehand that it must be e.g. transitive.

Why do you need to merge counts if you look for unique elements? Isn't the count always 1 for each element present? Isn't the key to shard your chunks so each element can appear in at most one chunk?

> merging them in a tree-like computational graph implies O(log n) merges.

Intuitively this doesn't make sense to me. You have a tree that has N leaves, and you have to perform a merge for each parent. There are however N-1 parents, so you'll still perform O(N) merges.

Reply on news.ycombinator.com