Live data from Hacker News

Topics in Advanced Data Structures [pdf]

web.stanford.edu

71–80 of 89 posts

Re: Topics in Advanced Data Structures [pdf]

#71
post #5

Does anyone in their work find that they are able to employ data structures like this, and if so, what do you work on? I've almost always had to delegate all my state to a database using default indexes, etc., which is productive, yet a little disappointing, because I'm always applying my brain power instead toward more mundane tasks.

Though my use of stranger data structures is relatively rare in my line of work, I enjoy learning them because they keep revealing new ways to approach problems. It's less "I use CRDTs" and more "CRDTs have changed what I think is feasible", similarly for stuff like bloom filters (no-false-negatives can be very powerful) and locality-sensitive hashing (don't search for all X every time, pre-compute a simpler version so you only check promising items). Concurrent data structures have also been pretty fruitful, since they're also often "how can we guarantee X in our distributed system, and what primitives do we need" strategies / solutions.

(obviously some of this is "I learned a tangential thing while learning about X", but that's kinda the point. you may never use a rope, but you might be introduced to a new idea in the process of learning about it)

Re: Topics in Advanced Data Structures [pdf]

#72
post #69

This kind of stuff fascinates me. General software engineering seems comparatively boring. I was considering going back to university to do a phd in cs and this is making me realize that research in algorithms/data structure would actually be viable (still lots of stuff to discover). Does anyone here know what it is like doing research in these areas? Any general advice?

I've got a PhD in CS, and these structures fascinate me as well. The Bloomier Filter reads amazing. Unfortunately, day to day job has almost nothing to do with these algorithms, but mainly software architecture and maintainability. I think the majority of these algorithms are not really something you will find implementing in day to day work. And at most I can see myself using a library with one of those. Even if you…

> I think the majority of these algorithms are not really something you will find implementing in day to day work. And at most I can see myself using a library with one of those.

That's true but if you don't know what's possible, it's likely that you don't even look for it or stumble over it randomly.

So you should know about them, even if you never implement them. You wouldn't need to know about them in that detail for that but it's just plain fun to learn stuff like this. :-)

Re: Topics in Advanced Data Structures [pdf]

#73
I love learning Algorithms and Data Structures. The issue is that I don't get to use these frequently, not even basic DS. Most of what I need exists in the language or some framework, and if I am to implement it from scratch, I am sure I will do worse. The only time I really use this knowledge is during interviews.

Re: Topics in Advanced Data Structures [pdf]

#74
post #73

I love learning Algorithms and Data Structures. The issue is that I don't get to use these frequently, not even basic DS. Most of what I need exists in the language or some framework, and if I am to implement it from scratch, I am sure I will do worse. The only time I really use this knowledge is during interviews.

I (did) feel excatly the same. Now after working for 17 years I realize that I barely ever use this stuff, and when asked this stuff in an interview I do a lot worse than I did straight out of university. I am however a lot better software engineer than I was then.

Re: Topics in Advanced Data Structures [pdf]

#75
post #69

This kind of stuff fascinates me. General software engineering seems comparatively boring. I was considering going back to university to do a phd in cs and this is making me realize that research in algorithms/data structure would actually be viable (still lots of stuff to discover). Does anyone here know what it is like doing research in these areas? Any general advice?

I've got a PhD in CS, and these structures fascinate me as well. The Bloomier Filter reads amazing. Unfortunately, day to day job has almost nothing to do with these algorithms, but mainly software architecture and maintainability. I think the majority of these algorithms are not really something you will find implementing in day to day work. And at most I can see myself using a library with one of those. Even if you…

Just today I finished implementing radix heaps in C# to optimize some of my Dijkstras.. When I googled I saw zero implementations in C#, so I may be the first to write it. It worked well, giving me 3x speedup in practice over DAry heap and very low GC pressure, fortunate as my process was exceeding 256GB ram.

Rolling your own data structures is pretty vital if you're working on algorithms.

Re: Topics in Advanced Data Structures [pdf]

#76
post #57

Earlier quoted context omitted.

>I fully expect to see these tools start to become available over the next decade or so, given the current progress of program synthesis I see in the academic literature. Interesting. I did know about program verification efforts (trying to prove that programs are correct), but had never heard of program synthesis (assuming it is somewhat different from code generation). Do you know of any examples of the kinds of ar…

The best overview of the topic I know of is https://www.microsoft.com/en-us/research/wp-content/uploads/... , which describes the state of the field ~18 months ago. The major field where it's already being applied is in automating the conversion of data--building the program that can take "John Doe" and turn it into " John Doe " just by example. You can also do similar generalization to automate things like construct…

Those applications sound cool. Will check out that paper. Thanks.

Re: Topics in Advanced Data Structures [pdf]

#77
post #63
post #5

Does anyone in their work find that they are able to employ data structures like this, and if so, what do you work on? I've almost always had to delegate all my state to a database using default indexes, etc., which is productive, yet a little disappointing, because I'm always applying my brain power instead toward more mundane tasks.

I managed to use DAWGs (Directed Acyclic Word Graphs) in a search engine, and later HyperLogLog+ and a Bloom Filter for a scalable distributed Multi-Armed Bandit implementation. Otherwise I find that the built-in Clojure data structures are so good for all-round use that it's difficult to justify the time to use anything else, except in extreme cases.

>Otherwise I find that the built-in Clojure data structures are so good for all-round use that it's difficult to justify the time to use anything else, except in extreme cases.

I don't know Clojure, so can't compare it's data structures with those of Python, but I've read a few times that Python's built-in data structures are so useful that for many applications, it suffices to just use them as is, or in combinations (e.g. lists of dicts, dicts of lists, ...), instead defining your own custom ones using classes. More so when used in combination with other Python features like {list,dict,set} comprehensions and libraries like itertools.

And I've found that to be somewhat true in my own Python work.

Re: Topics in Advanced Data Structures [pdf]

#78
post #62

I was going to roll my eyes about stuff no one will ever hear of, much less use in their day job, but there are some really relevant structures here. Finger trees, cache-oblivious structures, R-trees, etc., just to name a couple from a random page or two. The "why they're worth studying" summaries are gold. Thanks!

> much less use in their day job Yes, some are indeed very relevant. In one of my previous businesses, we built a search engine where we used DAWGs (Directed Acyclic Word Graphs) [I didn't do this part]. And they worked really, really well, in fact they work well to this day.

Good to hear they do. :)

Re: Topics in Advanced Data Structures [pdf]

#79
post #5

Does anyone in their work find that they are able to employ data structures like this, and if so, what do you work on? I've almost always had to delegate all my state to a database using default indexes, etc., which is productive, yet a little disappointing, because I'm always applying my brain power instead toward more mundane tasks.

I do plasma simulations and recently had the problem of finding the distance to the nearest neighbor for every of the particles in the simulation. Doing that naively is O(n^2) and took hours even for small test problems. Building an R-tree once and using if for nearest-neighbor look-ups brought that down to 5 minutes. libspatialindex lacks documentation, but worked really nicely. The rtree interface in python is much…

There is a library called flann that does approximate nearest neighbors using a kd-tree and best bin first method. It is typically used not only for nearest neighbors but finding them in higher dimensions.

Re: Topics in Advanced Data Structures [pdf]

#80

I was going to roll my eyes about stuff no one will ever hear of, much less use in their day job, but there are some really relevant structures here. Finger trees, cache-oblivious structures, R-trees, etc., just to name a couple from a random page or two. The "why they're worth studying" summaries are gold. Thanks!

A doctor has to mostly always treat common cold, and influenza. But that's no excuse for her / him to not know the purpose of the left pulmonary vein. The more basics they know, the better doctors they are. Sorry if this analogy is a bit extreme, but I want to make a point.
Post reply on HN