4 ms·
Exotic Data Structures (2011)
- pagnol 9y agoThis website seems like a real gem. Thanks for posting!
- evincarofautumn 9y agoConcatenative programming is definitely an overlooked paradigm. Factor and Forth(s) are worth trying out, if only for how they influence your thinking about software architecture in a minimal, compositional style.
- MichaelMoser123 9y agoCompact dynamic array is an std::deque right? What's so exotic about that?
- pja 9y agoOnce you get down to PMAs and van Emde Boas trees I think those are fairly exotic by the standards of most programmers - you won't meet them in your standard undergrad CS course IIRC.
- evincarofautumn 9y agoSeems like one possible implementation of std::deque, yeah. Dunno off the top of my head if the described implementation matches the requirements, though. IIRC C++ standard library implementations tend to use fixed-size chunks, except maybe the first and last chunks.
- wfunction 9y agoNo, std::deque has O(n) space overhead... the goal here is to get that to O(sqrt(n)), and in the worst case too.
- MichaelMoser123 9y agostd::deque has the following constraints * Random access - constant O(1) * Insertion or removal of elements at the end or beginning - constant O(1) * Insertion or removal of elements - linear O(n) Also in glibc/libstdc++ it is one https://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a01503_source.html https://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a015...
- wfunction 9y agoO(n) in my comment refers to space overhead. You're talking about time.
- MichaelMoser123 9y ago[1] does not mention a linear space requirement, it mentions O(1) time for random access and removal of elements. Both major implementations implement std::deque in this way libstdc++ [2] and libc++ [3], but you say it can't be so. Well well. [1] http://en.cppreference.com/w/cpp/container/deque http://en.cppreference.com/w/cpp/container/deque [2] https://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a01503_source.html https://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a015... [3] https://github.com/llvm-mirror/libcxx/blob/master/include/deque https://github.com/llvm-mirror/libcxx/blob/master/include/de...
- wfunction 9y agoI don't get what you're arguing against, if anything. Can you make an actual claim and tell me where I'm wrong? Literally all I've been saying so far is that std::deque does not meet the O(sqrt n) space overhead of compact dynamic arrays. i.e.: yes it is more exotic than a mere std::deque, which is precisely the question you were asking and I was answering initially. So you're saying I'm wrong, or what? If you're saying I'm wrong, which implementation of std::deque do you think meets that overhead spec?
- MichaelMoser123 9y ago
- jzwinck 9y agoNo. std::deque is like a vector of small arrays. Small meaning 32 to 512 bytes or one T if larger. Compact dynamic arrays have sub-arrays which can be larger and can be dynamically sized. The small fixed size of the sub-arrays in std::deque is basically a defect making the container a lot less useful.
- _asummers 9y agoThe MIT OCW Advanced Data Structures course goes over these in pretty good detail. Definitely worth a watch.
- bubaflub 9y agoAre you referring to https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/ https://ocw.mit.edu/courses/electrical-engineering-and-compu...?
- _asummers 9y agoYup! YouTube playlist: https://www.youtube.com/playlist?list=PLUl4u3cNGP61hsJNdULdudlRL493b-XZf https://www.youtube.com/playlist?list=PLUl4u3cNGP61hsJNdULdu...
- HugoDaniel 9y agoIs there any language that has implementations of all of these ?
- nayuki 9y ago"1. Compact dynamic array" has a rather strange name of https://en.wikipedia.org/wiki/Hashed_array_tree https://en.wikipedia.org/wiki/Hashed_array_tree
- panic 9y agoWow, that really is a terrible name -- especially now that "hash array mapped tries" are a popular implementation of persistent hash maps. I wonder if there's any way to justify changing the article name on Wikipedia.
- nayuki 9y agoThe name HAT was given by its inventor Edward Sitarski in 1996. It looks like few people are implementing it and/or calling it by a different name. Because of this lack of development, it might not be possible to change the name to a more modern, neutral alternative.