←back to thread

-2000 Lines of code

(www.folklore.org)
499 points xeonmc | 4 comments | 25 Jun 25 19:53 UTC | HN request time: 0.753s | source
Show context
bironran ◴[25 Jun 25 22:55 UTC] No.44382555[source]▶
One of my best commits was removing about 60K lines of code, a whole "server" (it was early 2000's) with that had to hold all of its state in memory and replacing them with about 5k of logic that was lightweight enough to piggyback into another service and had no in-memory state at all. That was pure a algorithmic win - figuring out that a specific guided subgraph isomorphism where the target was a tree (directed, non cyclic graph with a single root) was possible by a single walk through the origin (general) directed bi-graph while emitting vertices and edges to the output graph (tree) and maintaining only a small in-process peek-able stack of steps taken from the root that can affect the current generation step (not necessarily just parent path).

I still remember the behemoth of a commit that was "-60,000 (or similar) lines of code". Best commit I ever pushed.

Those were fun times. Hadn't done anything algorithmically impressive since.

replies(13): >>44382607 #>>44383577 #>>44383660 #>>44384143 #>>44384528 #>>44384875 #>>44385261 #>>44385550 #>>44385861 #>>44386549 #>>44386714 #>>44386823 #>>44388515 #
1. ninetyninenine ◴[26 Jun 25 12:36 UTC] No.44386823[source]▶
Am I mistaken? Is what you say even possible?

Given two graphs one is a tree you cannot determine if the tree is a subgraph of the other graph in one walk through?

It’s only possible if you’re given additional information? Like a starting node to search from? I’m genuinely confused?

replies(2): >>44388505 #>>44390732 #
2. jcynix ◴[26 Jun 25 15:43 UTC] No.44388505[source]▶
Take a look at Carl Hewitt's Same-Fringe solution, which flattens structures concurrently and compares the final (aka leave) nodes:

http://www.nsl.com/papers/samefringe.htm

If you flatten both of your trees/graphs and regard the output as strings of nodes, you reduce your task to a substring search.

Now if you want to verify if the structures and not just the leave nodes are identical, you might be able to encode structure information into you strings.

replies(1): >>44388735 #
3. ninetyninenine ◴[26 Jun 25 16:08 UTC] No.44388735[source]▶
Thanks. Good solution.

I was thinking in terms of finding all subgraph isomorphisms. But this definitely is O(N) if all you need is one solution.

But then I thought about it even further and this reduces to sliding window problem. In this case you still need to travel to each node in the window to see if there’s a match.

So it cannot be that you traverse each node once. Not if you want to find all possible subgraph isomorphisms.

Imagine a string that is a fractal of substrings:

     rrrrrrrrrrrrrrrrrrrrrrrrrrrr
And the other one:

     rrrrrrr
Right? The sliding window for rrrrrrr will be 7 in length and you need to traverse that entire window every time you move it. So by that fact alone every node is traversed at least 7 times.
4. bironran ◴[26 Jun 25 20:00 UTC] No.44390732[source]▶
I oversimplified. See https://news.ycombinator.com/item?id=44390701