Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What are the lesser known but useful data structures?

stackoverflow.com

Post reply on HN
Print view View original

21–30 of 82 posts

Re: What are the lesser known but useful data structures?

#21

Post by codezero »

batbomb wrote: post #5

I use a Hierarchical Triangular Mesh for indexing gamma ray events from the universe. The data is partitioned in the database according to it's HTM id. http://arxiv.org/pdf/cs/0701164.pdf Currently I use this for indexing ~11 billion gamma ray events. Researchers typically supply a region in the sky, a search radius, and some cuts (energy, event quality, etc...)

HTM is generally good. We used it to index white light data from out satellite. It makes for a very flexible way to store spherical surface data without losing context or information when projecting.

Re: What are the lesser known but useful data structures?

#22

Post by YZF »

kintamanimatt wrote: post #15
YZF wrote: post #13

Earlier quoted context omitted.

How is that one of the best questions on SO? There is always someone who wants SO to be what they want it to be. I'm not saying everything is perfect in SO but I think the standard answer is that if you want a site that is about subjective discussions related to programming you should make one...

How is it not one of the better questions on SO? It's educational, it's on-topic, it's more cerebral than the usual questions about jQuery, it has high quality answers, the question itself is as clear as day, it's interesting, and it's very popular in terms of views and upvotes. There's a degree of opinion in most answers anyway especially as there's often multiple ways to do the same thing and every answerer will ha…

How can anyone answer "really useful but are unknown to most programmers"? They are so useful we don't know about them? Aren't the answers, by definition, known, to a lot of programmers? Useful for what exactly?

I think I heard this criticism of SO for about 1 million times and this is the 1 million + 1 that tripped my fuse, so apologies for that. This question, and the answers, though IMO are bits of trivia and opinions more suited to a blog post.

Does it have some marginal usefulness in exposing some people without background to some random data structures or algorithms- maybe. The question is still there, it wasn't deleted, so SO is acting as the resource that you'd like it to be. If it's your first exposure to data structures I think there are better options out there (text books, online courses). If you are looking to solve some particular problem this is probably not the best resource. So it just stands as a (maybe interesting) bit of computer science trivia.

There are endless subjective topics that are tangentially related to programming and may be fun/amusing/interesting but SO is about things that have answers, not about discussions. I like it that when I have a question I can search and get a good answer for it, not just someone's opinion. For entertainment value and interesting things I go to other places, such as HN...

Re: What are the lesser known but useful data structures?

#23

Post by YZF »

bd_at_rivenhill wrote: post #18
YZF wrote: post #13

Earlier quoted context omitted.

How is that one of the best questions on SO? There is always someone who wants SO to be what they want it to be. I'm not saying everything is perfect in SO but I think the standard answer is that if you want a site that is about subjective discussions related to programming you should make one...

SO has critical mass which would be difficult to replicate in a new site; remember that it was started by Jeff Atwood and Joel Spolsky, who were already established bloggers. "Make your own SO for subjective discussions" would be a good suggestion for someone who already has a large online following, but not for a general programmer. I have yet to see a good argument why these types of questions detract from the main…

Maybe you could get Joel to refer people from SO to your site?

I guess my problem is that Joel and the others running the site don't want it to be a forum for those discussions. This topic has been beaten to death already and the outcome isn't going to change. So "we" need to let go of it. It's like Go and generics... (just kidding)

I can think of a few reasonable arguments. A lot of subjective discussions tend to degenerate into holy wars or popularity contests. It's hard to tell what's a good answer and what's not and it can get annoying both for people participating and people reading.

Even if you mark those as subjective they would clutter the front page. Whenever you give people the option you need to consider defaults, if the default is not to see subjective questions then no one will ever see them, if the default is to see them we're back to square 1. What about search engines?

EDIT: It also so happens that some of the "good" subjective questions do seem to hang around, get attention, and get cool answers, so the system does seem to be working.

Re: What are the lesser known but useful data structures?

#24

Post by kintamanimatt »

YZF wrote: post #22
kintamanimatt wrote: post #15

Earlier quoted context omitted.

How is it not one of the better questions on SO? It's educational, it's on-topic, it's more cerebral than the usual questions about jQuery, it has high quality answers, the question itself is as clear as day, it's interesting, and it's very popular in terms of views and upvotes. There's a degree of opinion in most answers anyway especially as there's often multiple ways to do the same thing and every answerer will ha…

How can anyone answer "really useful but are unknown to most programmers"? They are so useful we don't know about them? Aren't the answers, by definition, known, to a lot of programmers? Useful for what exactly? I think I heard this criticism of SO for about 1 million times and this is the 1 million + 1 that tripped my fuse, so apologies for that. This question, and the answers, though IMO are bits of trivia and opin…

> The question is still there, it wasn't deleted, so SO is acting as the resource that you'd like it to be.

Try asking such a question today, or any time in the last couple of years!

> So it just stands as a (maybe interesting) bit of computer science trivia.

Just because you label it trivia doesn't necessarily mean it wasn't important to the asker or the thousands of people that read, commented, and upvoted. Just like people asking about jQuery, the asker had a question in mind and wanted to crowdsource the answer.

> but SO is about things that have answers

An opinion can be an answer too.

> For entertainment value and interesting things I go to other places, such as HN...

Why must the answers on SO be bland as tofu? You seem to give the impression that learning and the SO answers must be plain and dull, and any hint of entertainment must be quickly quashed. I see nothing wrong with being entertained and educated at the same time, especially as things that are entertaining tend to be more readily recalled.

Re: What are the lesser known but useful data structures?

#25

Post by kintamanimatt »

YZF wrote: post #23
bd_at_rivenhill wrote: post #18

Earlier quoted context omitted.

SO has critical mass which would be difficult to replicate in a new site; remember that it was started by Jeff Atwood and Joel Spolsky, who were already established bloggers. "Make your own SO for subjective discussions" would be a good suggestion for someone who already has a large online following, but not for a general programmer. I have yet to see a good argument why these types of questions detract from the main…

Maybe you could get Joel to refer people from SO to your site? I guess my problem is that Joel and the others running the site don't want it to be a forum for those discussions. This topic has been beaten to death already and the outcome isn't going to change. So "we" need to let go of it. It's like Go and generics... (just kidding) I can think of a few reasonable arguments. A lot of subjective discussions tend to de…

> Even if you mark those as subjective they would clutter the front page.

Really simple solution: put a checkbox on the right: "[ ] Hide posts marked as subjective" Make it bold and obvious, and far above the fold.

Re: What are the lesser known but useful data structures?

#28

Post by Shog9 »

kintamanimatt wrote: post #25
YZF wrote: post #23

Earlier quoted context omitted.

Maybe you could get Joel to refer people from SO to your site? I guess my problem is that Joel and the others running the site don't want it to be a forum for those discussions. This topic has been beaten to death already and the outcome isn't going to change. So "we" need to let go of it. It's like Go and generics... (just kidding) I can think of a few reasonable arguments. A lot of subjective discussions tend to de…

> Even if you mark those as subjective they would clutter the front page. Really simple solution: put a checkbox on the right: "[ ] Hide posts marked as subjective" Make it bold and obvious, and far above the fold.

We tried a variation on that fairly early on. It led to endless arguments over how subjective something had to be to be branded subjective. See: http://meta.stackoverflow.com/questions/51627/should-we-perm...

In the end, it was a huge distraction from what we should've been talking about instead: which questions are actually resulting in the creation of something useful?

Re: What are the lesser known but useful data structures?

#30

Post by matt4711 »

siganakis wrote: post #11
tikhonj wrote: post #6

There's a whole set of interesting data structures that are not very well known: succinct data structures[1]. The idea is simple: we want to store data in a compressed form, but also perform certain operations quickly without uncompressing. These can be very useful for certain applications. The article on "Cramming 80,000 Words into a JavaScript File"[2] is a nice example. It shows you how you can store a compressed…

The problem with succinct data structures (and wavelet trees especially, but also rank-select dictionaries) is that while they have excellent performance characteristics when you look at them from a theoretical perspective, they tend to perform relatively poorly in practice. This seems to be due to how much memory is accessed when checking a single bit, and the difficulty in predicting branches. Of course it could ju…

I'm one of the authors of a more complete c++11 succinct data structure library [1] which includes several engineered implementations of wavelet trees, compressed suffix arrays and compressed suffix trees. while you are right that random access is one of the main bottlenecks of succinct data structures, we found that sometimes SDS can be faster than their uncompressed counterparts [2]

The github URL contains some additional resources such as tutorial slides and cheatsheets if you want to check it out.

[1] https://github.com/simongog/sdsl-lite/ [2] http://people.eng.unimelb.edu.au/sgog/optimized.pdf

Post reply on HN