4 ms·
Recursion isn't the problem. Not keeping track of seen tweets is the problem. Recursion can be used to detect cycles and traverse a cyclic graph in a way that d
by anonytrary 6y ago
Recursion isn't the problem. Not keeping track of seen tweets is the problem. Recursion can be used to detect cycles and traverse a cyclic graph in a way that doesn't blow up.
- eyelidlessness 6y agoBut you wouldn’t do that if your assumption is that the graph doesn’t cycle. Edit: child comments are correct and I regret my oversight
- ulber 6y agoFor traversing a DAG you probably still would to avoid exploring an exponential number of paths (consider a chain of diamonds [1]). 1: https://www.researchgate.net/figure/A-diamond-shaped-DAG_fig3_226524067 https://www.researchgate.net/figure/A-diamond-shaped-DAG_fig...
- zemnmez 6y agoIt’s a lot easier to just have a depth limit on such non-cyclic graphs than keep an in-memory list of previously seen nodes. its interesting for sure! but a much rarer edge-case imo
- tyrust 6y agoBut a diamond cannot occur in a Twitter-reply graph, right? It would require a Tweet to be able to reply to more than one tweet.
- anonytrary 6y agoIt can because the assumption is that we are crawling embedded links as well as native parents.
- delecti 6y agoYou can reply to one tweet while quote-retweeting another. Depending on how links are defined that could result in a diamond.
- smt1 6y agoof course, it depends on 'what' you are perceiving the computation of and if you were trying to stabilize the effects other surrounding (this would be like a pfaffian), just create a equivariant gauge relative to whatever your senses, just pretend to be like a "solenoid". knowing about a renormalization procedure to a set of pre-known "cardinals", like the lithium-defn (adiabatic "approximation") of seconds or unicode, knowing how they cross convolve or cross correlate. Almost all of these is pretty easy to directly infer or calculate in the discrete digital logical world (or reduce it to a branch and cut problem or SAT), but there seem to be limits to MOSfet technology.
- anonytrary 6y agoGraph doesn't need to cycle to hit a node twice. Good code does not visit the same node twice.
- deleted 6y ago[deleted]
- patates 6y agoWhen doing recursion (Postgres recursive CTE) I keep a path on the latest edges and check to see new edges aren't already visited, so same nodes can appear in multiple branches but not on the same branch. Works flawlessly.
- pfarrell 6y agoCan you provide an example of this? I’d like to understand this technique. Edit: is this an example? https://stackoverflow.com/a/1757915 https://stackoverflow.com/a/1757915
- dheera 6y agoIrritation would probably better in terms of not blowing up your memory requirements. Just keep hashes of all visited nodes and a stack or queue of to-be-visited nodes and loop until you have no more to-be-visited nodes.
- waterproof 6y agoI think you meant "iteration", not "irritation".