5 ms·
I'm confused. What is this?
by Kinnard 11y ago
I'm confused. What is this?
- detaro 11y agoAn automated parody of HN, OP explains above: https://news.ycombinator.com/item?id=10248803 https://news.ycombinator.com/item?id=10248803 > I've pulled every comment and story from HN through the API and make a bunch of Markov chains to produce story titles and comments.
- Kinnard 11y agoI see. Cool. I'm building an HN clone now. Hierarchical comments are a fun challenge. Any tips?
- orf 11y agoPostgres recursive queries make them pretty simple to deal with. This[1] is the query I used to pull a list of all a stories children recursively. 1. https://gist.github.com/orf/5565a572c6ddda039d6f https://gist.github.com/orf/5565a572c6ddda039d6f
- Kinnard 11y agoHmmm, I'm trying to decide between this recursive query or something using ltrees. Can't make up my mind . . . [1] https://truongtx.me/2014/02/28/tree-structure-query-with-postgresql/ https://truongtx.me/2014/02/28/tree-structure-query-with-pos... [2] http://stackoverflow.com/questions/603894/is-postgresqls-ltree-module-a-good-fit-for-threaded-comments http://stackoverflow.com/questions/603894/is-postgresqls-ltr...
- Kenji 11y agoYeah. If you store them in a relational database you will grow a couple of grey hairs because you're essentially forcing a tree structure into a table structure. The concepts clash and it's kind of a pain, but possible since every post has 1 unique parent, so you can make upwards references and rebuild a tree from that.
- martin-adams 11y agoA great technique I've used for many years to store hierarchical data is by using a Nested Set Model (https://en.wikipedia.org/wiki/Nested_set_model https://en.wikipedia.org/wiki/Nested_set_model) It works a treat as you can query the whole tree in one SQL statement but preserve the nesting for formatting.
- Kenji 11y agoThank you sir for pointing that out. This looks very interesting and I might even implement that in my own blog at some point in time. I thought about doing something similar to that (without actually knowing this technique) but I shyed away precisely because of the price you pay at insertion time. EDIT: I've been thinking some more about this. Another possibility would be to limit the depth of the tree to, say, 8 (which should be reasonable) and then make 8 fields, one for each ancestor (parent, grandparent, and so on). Changing the tree will become a nightmare but all queries for subtrees will be blazingly fast.
- MichaelGG 11y agoSince individual comment threads are never that big, just store the root parent ID and query on that. Then reconstruct in code.
- toupeira 11y agoThe "closure table" approach works best if you have frequent reads and writes, see e.g. https://coderwall.com/p/lixing/closure-tables-for-browsing-trees-in-sql https://coderwall.com/p/lixing/closure-tables-for-browsing-t...
- Kinnard 11y agoHmmm, toooo many options. How do I decide between them. Sort of a DB noob.
- krapp 11y agoA simple method (a modified adjacency list) I've used just stores the root id, parent id and id of each post together. You can get the entire tree from any root post easily (everything shares the same root id) but getting the whole subtree beyond immediate children takes recursion. I find that you don't even have to worry about treating the data as a tree in most cases until the very end. What you want to actually deal with is a flat array with the ids (root,parent,id) arranged in rendering order, and to have the tree built in the HTML. The data set from the DB doesn't even have to represent the tree structure directly, as long as you can sort it elsewhere. You can even have two arrays - one (say, an associative array) with the data, and another basic array with the ids. Sort just the array with the ids, then use those as keys to iterate the data array when building the html, so you can avoid ever having to sort the larger array (which as luck has it just happens to be optimized for non-linear access anyway.) I should probably mention, I thought this was terribly clever when I did it in PHP, before I was aware that all arrays in PHP are basically the same, so it was mostly pointless overoptimization. Building something like an unordered list in HTML from that array then becomes a matter of adding or removing <UL> elements based on the relative change in depth for each subsequent id. Depth is easy to find by checking if an item's parent is (or isn't) the same as the id of the previous element. The actual tree never exists in code until the unordered list is rendered in the browser. Also here's a good reference on Stack Overflow of different methods to do the same thing: https://stackoverflow.com/questions/2175882/how-to-represent-a-data-tree-in-sql https://stackoverflow.com/questions/2175882/how-to-represent... If you actually know what you're doing beforehand, probably ignore everything I just said and go with nested sets. My method is, admittedly, naive and better programmers are probably chuckling at it over the beverage of their choice, but it does work and it seems to be decently fast.
- tajen 11y agoDoes that mean that there is no deep learning here, only statistics and randomization?
- minimaxir 11y agoNothing wrong with statistics and randomization. :)
- 6502nerdface 11y agoMarkov chains do learn in the sense that they model distributions of strings, can be trained on observed strings and used to generate strings, assign probabilities to strings, classify strings, etc. They have well developed treatments in multiple frameworks of computational learning theory, including Gold learnability and PAC learnability. Is "deep learning" more than statistics and randomization?
- jacques_chester 11y ago> Does that mean that there is no deep learning here, only statistics and randomization? Correct. It is a perfect simulation of HN.
- nrivadeneira 11y agoNormally I don't like comments that are just jokes, but this one was too perfect. Well done. And to add just a slight bit more substance to my comment, while I was reading through all the comments here my wife asked why I was laughing so hard. I found it really difficult to convey why, but I guess that's the nature of this type of humor.
- gwern 11y agoThere isn't, but I don't think it should be difficult to feed this into 'char-rnn' if you wanted to do it with RNNs rather than Markov chains. The interface, such as it is, to char-rnn is very simple; you dump everything into a text file 'input.txt'.
- 11y ago