State
What can you tell about modern data structures? We all know classic ones, like trees, tries, stacks, lists, B-trees and so on (I think a Cormen's book is a pretty good list of a "classic ones"). But what about recent researches? I can name at least 2 of them: finger trees and judy arrays. I would like to know more.
That really depends on your definition of "recent." CLRS contains a great number of data structures, but omits many of the structures that had been developed around that time. For example, the van Emde Boas tree, which allows for extremely fast storage and lookup of integers, had been developed by that time but was not mentioned anywhere.
A lot of modern research has been on cache-oblivious data structures, which are structures that take optimal advantage of the memory hierarchy subject to certain reasonable assumptions. Brodal is one researcher in this field who has produced many excellent structures of this sort.
Purely functional data structures which can be used in functional languages (or in imperative languages to guarantee persistence) are also an active topic of research. Chris Okasaki's work in this field has led to developments of new trees and priority queues, for example.
Distributed data structures are of great import these days. Google's BigTable is a great example. Similarly, concurrent or lock-free data structures have found their way into many programming languages (see, for example, Java's ConcurrentHashMap or CopyOnWriteArrayList).
Data structures based on amortization are mentioned tangentially in CLRS, which does focus on the Fibonacci heap. However, the splay tree and skew heap structures also developed around the same time are not mentioned, though they are of great import today.
Probabilistic structures like the treap and skip list have had a lot of research activity, and are a great place to keep exploring. In a related vein, powerful hash tables like the cuckoo hash table or dynamic perfect hash tables are certainly worth looking into.
Data structures for computational geometry have had a look of focus these past few years, though regrettably I don't know about them, well enough to suggest any particular structures.
Data structures for string processing, namely the suffix tree, are extremely relevant in biocomputation and web searches. I don't think CLRS even mentions their existence. You should definitely look into them, though, since they are responsible for much of the new work in genomics.
Many researchers have put effort into building data structures that take advantage of the fact that modern machines can operate on multiple bits in parallel. Some structures like the fusion tree, exponential tree, or y-fast tree exploit these properties to sort and search in arrays of integers faster than the O(n lg n) barriers imposed in a naive comparison model.
There is also a lot of work being done on summary, sketching, and synopsis data structures that try to make it possible to answer questions about a data set without storing the entire set explicitly. The Count-Min sketch is a great example of one of these data structures.
This is just a small sampling of the new and cool structures out there. I hope it's a good starting point!
Some of the relatively recent (as in the last 30 years) data structure innovations have been probabilistic ones, like Skip Lists. I find these particularly interesting, but I don't keep up on research. Reading recent ACM Transactions on Algorithms might help you find some interesting and cutting edge research.
But, most anything "new" is going to be highly specialized. It is only once in a very long while that a new but fundamentally important algorithm/structure is created (like lists, trees, etc).
There are many hundreds of specialized data structures. http://en.wikipedia.org/wiki/List_of_data_structures is a good start.
链接地址: http://www.djcxy.com/p/39846.html上一篇: 哪些数据结构和算法在C中不可实现？
下一篇: 州