17 ms·
What are the lesser known but useful data structures?
- deleted 13y ago[deleted]
- jboggan 13y agoBloom filters and count-min sketch are awesome. http://en.wikipedia.org/wiki/Bloom_filter http://en.wikipedia.org/wiki/Bloom_filter http://en.wikipedia.org/wiki/Count%E2%80%93min_sketch http://en.wikipedia.org/wiki/Count%E2%80%93min_sketch
- hyperpape 13y agoLooking at these lists, I strongly suspect that people upvote based on whether they personally recognize the data structure. It goes against the intent of the original question, but iIt's almost ideally designed to make you feel good--you get the rush of knowledge then nerd sniped as you head to wikipedia.
- andrewflnr 13y agoLest people think this is useless negativity, the point is that you need to scroll down and look at the other pages to see the really interesting ones. :)
- batbomb 13y agoI 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 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...)
- codezero 13y agoHTM 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.
- tikhonj 13y agoThere'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 trie in memory but still use it. I also like this[3] series of blog posts leading up to wavelet trees. These certainly count as obscure data structures, unlike many of the ones listed on SO. I had never even considered the idea of compressing data in memory like this, much less encountered actual examples of succinct data structures! I have to thank Edward Kmett for introducing me to the whole field. These data structures are important not just because they're neat themselves, but because they got me to think a new way. In particular, I realized that using pointers all over the place--to represent things like trees--is not always efficient. Instead of parsing data, it might be better to store it as a blob of some sort with a binary index. Just starting to consider details like that is valuable all on its own. [1]: http://en.wikipedia.org/wiki/Succinct_data_structure http://en.wikipedia.org/wiki/Succinct_data_structure [2]: http://stevehanov.ca/blog/index.php/?id=120 http://stevehanov.ca/blog/index.php/?id=120 [3]: http://alexbowe.com/rrr/ http://alexbowe.com/rrr/ and http://alexbowe.com/wavelet-trees/ http://alexbowe.com/wavelet-trees/
- siganakis 13y agoThe 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 just be that all my implementations have sucked, but even in playing around with libcds[1] didn't yield the kind of performance expected. If anyone knows of a fast implementation of Wavelet Trees, I'd love to see it. [1] https://github.com/fclaude/libcds https://github.com/fclaude/libcds
- matt4711 13y agoI'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/ https://github.com/simongog/sdsl-lite/ [2] http://people.eng.unimelb.edu.au/sgog/optimized.pdf http://people.eng.unimelb.edu.au/sgog/optimized.pdf
- nilkn 13y agoI don't really consider tries and bloom filters all that poorly known. These commonly come up in interviews for fresh graduates at Google/Facebook. Zippers, skip lists, ropes, round-robin databases, etc. are more genuinely not known I think.
- ww520 13y agoExtendible hashing is amazing in space utilization while retaining the performance of hashing.
- kintamanimatt 13y ago> This question exists because it has historical significance, but it is not considered a good, on-topic question for this site, so please do not use it as evidence that you can ask similar questions here. Yet it's one of the best questions on SO. Something's very wrong with SO if this isn't considered a good, on-topic question for a programming Q&A site.
- YZF 13y agoHow 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...
- kintamanimatt 13y agoHow 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 have a preference of some kind. I don't necessarily see this one as a particularly subjective discussion anyway, or why you think I'm trying to make SO be something it's not. In any event, why are marginally subjective discussions are a horrible thing anyway in a Q&A site?
- alanctgardner2 13y agoThe problem is that SO is not for entertainment. It's not even really for education. They (the site's operators) want it to be an injective mapping of google queries to solutions. You don't need to become a better programmer. You need to keep coming back to SO to ask more questions. On the other side they need to supply a steady stream of middling difficulty questions, because everyone isn't John Skeet. Nobody is going to be working on a project and say "My client requires the use of obscure data structures, better Google some!". You can bash the multitude of jQuery questions, but having worked in a variety of settings, some people need things spelled out for them. You need a lot of simple questions with alternate wordings, different permutations of libraries, etc. Even though you can generalize these answers, they're hard to find from Google, and a lot of people will read "Undefined variable foo? Nonsense, my undefined variable is baz. Better open a new ticket".
- bazzargh 13y agoIt's not highlighting one thing, but Chris Okasaki's book on Purely Functional Data Structures, and this brilliant top answer to a question about functional data structures published since the book will keep you in reading material for a while: http://cstheory.stackexchange.com/a/1550 http://cstheory.stackexchange.com/a/1550 (it was all 'lesser known' to me when I started using haskell not so long ago)
- dllthomas 13y agoI second the plug for Purely Functional Data Structures - brilliant stuff!
- halfdeadcat 13y agoCup-a-bits
- lifthrasiir 13y agoI found the following page in the Concatenative wiki particularly interesting: http://concatenative.org/wiki/view/Exotic%20Data%20Structures http://concatenative.org/wiki/view/Exotic%20Data%20Structure... (Note that the page itself is not related to the concatenative languages.)
- deleted 13y ago[deleted]
- krisgee 13y agoI was going to say Trie but it was the first response to the SO thread so I guess it wasn't as little known as I thought. I implemented it because I was making a game that had scrabble elements in it and needed to check ahead to see if the player had a word that could still take letters (a prefix) or if they'd hit a dead end. Fit the whole SOWPODS into a remarkably tiny space with millisecond lookups. Probably my favourite part of the project.
- serge2k 13y agoIt's mentioned in the link, but circular/ring buffers. I've been grappling with decoding/playing back an audio stream and wouldn't have gotten it working if I hadn't found out about boosts lockfree ring buffer.
- dllthomas 13y agoRecently I learned that if you're using a ring buffer for message passing, the clflush opcode (after sending and after receiving) can dramatically reduce cache misses.
- WWKong 13y agoMe and my friend were pretty serious about creating a new data structure called "drum". A drum is a one way store. You write to it but can't read from it. We put it off till we figured a practical use.
- akurtzhs 13y agoBackups? People tend to treat them that way anyways.
- justforonereply 13y ago/dev/null is a nice implementation.
- statusgraph 13y agoAn append only log? The value of writing data is that you can read it, otherwise your structure is semantically equivalent to not writing at all.
- dllthomas 13y agoOr reading some information computed from it, I suppose. Something needs to read it, ever, for that of course, but it doesn't necessarily need to be exposed in the interface.
- nl 13y agoBloom Filters: http://en.wikipedia.org/wiki/Bloom_filter http://en.wikipedia.org/wiki/Bloom_filter Hamming Codes: http://en.wikipedia.org/wiki/Hamming_code http://en.wikipedia.org/wiki/Hamming_code
- chas 13y agoI'm happy to see finger trees got mentioned. Finger trees[0] are extremely useful and general data structure that can be used to implement persistent sequences, priority queues, search trees and priority search queues. (Haskell's Data.Sequence[1] uses specialized 2-3 finger trees internally) They can form the basis of all sorts of interesting custom structures by supplying the appropriate monoid[3], but this does make them harder to approach if you are not familiar with the abstractions. [3] A monoid is any structure that has members that can combine associatively. In addition, it must have an element that can combine with any other element and result in the other element. Some examples: (strings, string concatenation, the empty string); (integers, addition, 0); (natural numbers, max, 0); (booleans, and, True); (functions, composition, the identity function). The functional pearl[2] that describes the design of Haskell's diagrams library[4] goes into much more detail if you are interested in their application to programming. [0] http://apfelmus.nfshost.com/articles/monoid-fingertree.html http://apfelmus.nfshost.com/articles/monoid-fingertree.html [1] http://hackage.haskell.org/package/containers-0.5.4.0/docs/Data-Sequence.html http://hackage.haskell.org/package/containers-0.5.4.0/docs/D... [2] http://www.cis.upenn.edu/~byorgey/pub/monoid-pearl.pdf http://www.cis.upenn.edu/~byorgey/pub/monoid-pearl.pdf [4] http://projects.haskell.org/diagrams/ http://projects.haskell.org/diagrams/
- dllthomas 13y ago"In addition, it must have an element that can combine with any other element and result in the other element." Aka, an identity element. Monoids that have inverses (that is, every element has another element that, when combined, produces the identity element) are "groups". Of the examples you gave: "Strings over composition" does not form a group - there's nothing you can concatenate with a non-empty string to get an empty string. "Integers over addition" does form a group. The inverse of x is -x. "Natural numbers over max" is not a group. Once you get above 0 you cannot get back to it just by applying max. "Booleans over and" is not a group. Once you have false you can't get back to true. "Functions over composition" is not a group. Many functions have inverses, but some do not. If you restrict the set to "functions with inverses" then you do have a group.
- chas 13y ago
- pnathan 13y agoI recently learned about the spatial index tree family in connection with data mining. I hope to implement a data-mining centric X tree (n-dimensional) solution for a data analytics package I'm writing soon. That family is is how you efficiently handle KNN lookups, afaict.
- VexXtreme 13y agoI love how the question was locked because "it is not considered a good, on-topic question for this site". It's crazy. Unless an extremely specific concrete answer can be given, a question immediately gets killed. SO has turned into such a turd of a website.
- joelthelion 13y agoSpeaking of which, is there a good alternative site for questions that are forbidden on SO?
- jzwinck 13y agoThere are other sites in the StackExchange network like Programmers and Code Review and some others for math and other things. But I'm not sure which site (SE or otherwise) would be the best for this particular topic.
- sherwin 13y agoProbably the CS stackexchange (http://cs.stackexchange.com/ http://cs.stackexchange.com/), or CStheory (http://cs.stackexchange.com/ http://cs.stackexchange.com/). Unfortunately, neither are anywhere near as popular as StackOverflow, so the chances of getting a good discussion are lower.
- oneeyedpigeon 13y agoYahoo answers.
- oneeyedpigeon 13y agoI was shooting for 'brevity is the soul of wit' but fear I might have hit 'sarcasm is the lowest form of humour' and completely failed to get my point across, to wit, stackoverflow is designed for productive, informative, objective q&a, and alternatives that are less prescriptive, such as Yahoo answers, often end up as a source of unending crap.
- 13y ago
- youWontLikeThis 13y ago.............. locked by Robert Harvey♦ Mar 15 '12 at 18:42 This question exists because it has historical significance, but it is not considered a good, on-topic question for this site .............. Seriously, who's the responsible for putting this kind of guy in charge.
- shurcooL 13y agoDoes anyone know of an implementation of rope in golang? Something a little more feature complete than https://github.com/christianvozar/rope https://github.com/christianvozar/rope.
- abcd_f 13y agoXOR linked list: http://en.wikipedia.org/wiki/XOR_linked_list http://en.wikipedia.org/wiki/XOR_linked_list It's a double-linked list with just one link per node. However, to start traversing it you have to know at least two adjacent nodes. PS. May not be useful per se, but interesting nonetheless.
- aaronem 13y agoThe XOR swap is interesting, too. But I wouldn't want to see one in code someone wrote today, and which wasn't targeted at an embedded platform -- and a heavily constrained embedded platform, at that. (MSP430? Sure. ARM Cortex-M3? You've got enough space to do it properly.)
- dllthomas 13y agoIt's not just "you've got enough space" - it's only relevant if both operands are in registers already. If they're both in memory, then the xors are entirely redundant (first things you'd have to do is read values into two registers, at which point you can just write it back the other way). I wouldn't object to seeing it in a critical section in high performance code with substantial register pressure, but ideally it could be inserted by the compiler!
- swah 13y agoLet me just drop this video that is on my watchlist: http://www.youtube.com/watch?v=-sEdiFMntMA&feature=share&list=PLFDnELG9dpVxEpbyL53CYebmLI58qJhlt http://www.youtube.com/watch?v=-sEdiFMntMA&feature=share&lis... (Erik Dermaine is the lecturer)
- teddyh 13y agoEven though they are included in the GNU C library, most people do not seem to know about Obstacks: An "obstack" is a pool of memory containing a stack of objects. You can create any number of separate obstacks, and then allocate objects in specified obstacks. Within each obstack, the last object allocated must always be the first one freed, but distinct obstacks are independent of each other. Aside from this one constraint of order of freeing, obstacks are totally general: an obstack can contain any number of objects of any size. They are implemented with macros, so allocation is usually very fast as long as the objects are usually small. And the only space overhead per object is the padding needed to start each object on a suitable boundary. https://www.gnu.org/software/libc/manual/html_node/Obstacks.html https://www.gnu.org/software/libc/manual/html_node/Obstacks.... Sure, they’re not very interesting, but the point is that you get them for free in the GNU C standard library.
- dllthomas 13y agoThe FIFO equivalent can also be useful.
- teddyh 13y agoI’m not sure what you are referring to, do you have a link?
- deleted 13y ago[deleted]
- deleted 13y ago[deleted]
- dllthomas 13y agoI don't have a link, but it's an obvious transformation - basically, using a ring buffer for allocations where I can guarantee that older things will be freed before newer stuff.
- keefe 13y agoimho most DS & Algo are like kihon - the basic principles t'werk just fine, it's about augments and applications.