Slashdot Mirror
Advanced Data Structures?
mdf356 asks: "It's been 5 years since I left graduate school and started designing and writing software for a living. After 5 years of writing operating systems code, I feel like I've forgotten some of the more advanced data structures I used to know. The next time an interesting problem arises, I'd like to have more in my toolbox than hashes, linked lists, heaps and various binary and n-way trees. I'd like something short and sweet, more in the line of the standard C book. Algorithm Design by Kleinberg and Tardos looks likely to be too basic, but I haven't read it (I'd like to avoid paying $90 for something that won't meet my needs). CLR is far too large and almost exclusively covers basic territory. Tarjan's Data Structures book looks like it has potential, but seems focused on network algorithms, which are unlikely to be applicable to the kernel programming I do. What are some good reference books on more advanced data structures and algorithms, particularly ones with potential applicability to an operating systems kernel?"
Well, let's be fair, when you get to advanced data structures, it's kind of up to you to really do all the imagining that makes them great. Don't dismiss CLR too quickly, as the book has a lot of great concepts that, if you're serious about algorithms and data structures, are quite useful as a starting toolbox.
Honestly though, when I went through college, the very last thing they tried to shove down my throat wasn't advanced data structures but instead Design Patterns. I'm not talking about algorithm design but instead just designs in general. This book might not do it in C but the ideas are pretty language independent. It's your 'cookbook' of designs laid out in class diagrams and sometimes more documentation is provided. Anyways, what I would actually suggest is that you combine a book that covers C structures with book and what you would have is a way for you to make a set of complex classes that emulate a proxy. Or you have an adapter class that is a "advanced data structure." I guess what I'm trying to say is that I don't see the point of paying attention to advanced data structures when it's really the way these data structures interact that is complex and important.
The big problem is that, in order to make design patterns work for you, you have to go through a lot of documentation and diagrams. Take this for example, you're writing an OS code and there's a part of the operating system that's going to be changing frequently depending on processor (I don't know a lot about OS development), let's say the scheduler. So what do you do? Do you just willy-nilly throw the scheduler and start going? Well, what would be best is that if you encapsulated the scheduler inside a package or library so that it could easily be exchanged for another one. You try to keep it small and modularize the classes and data structures that change from those that don't. Then, a new processor comes out that might demand a new scheduler and you open up this mini-project, edit/debug it and roll it out as something that just replaces the classes and libraries on all your deployed versions. Sounds like common sense, right? Well, for some it is and for some it isn't but to me this interaction is a complication of data structures and I think that the answer you're looking for isn't necessarily a book called "advanced data structures" just a few that explain how they work.
My work here is dung.
Algorithms in C, Parts 1-5 (Bundle): Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms (3rd Edition) by Robert Sedgewick
The Art of Computer Programming, by Donald E. Knuth
Two seminal works on the subject. It really depends on your needs however. Nearly anything you would need can be built off of the subjects in those books, but for more specialized datastructures you will probably have to move to specialized books.
You use linked lists in your kernel?!?
"No matter where you go, there you are." -- Buckaroo Banzai
Data Structures and Algorithms (ISBN 0201000237) by Aho, Ullman and Hopcroft is a classic that belongs on every programmer's bookshelf (hell, keep it on your desk!).
Wikipedia has a nice collection of data structures. Maybe that's what you're looking for?
r es
http://en.wikipedia.org/wiki/List_of_data_structu
"It's too bad that stupidity isn't painful." - Anton LaVey
And most programmers do. Read some code out in the industry and you'd think that 90% of the programmers out there never took a data structures class. Even if you're using a language like Java or C++ you really should know the implementation details of each so you can make informed decisions about the trade-offs in performance and maintainability. If you can't visualize the layout of your data and how you'll be accessing it, you really won't be able to pick the best structure for the job (Or roll your own if none of the usual ones fit.)
I can't think of a C project I've worked on where I didn't have to write a basic data structure like a stack or a linked list. On a couple of them the programmer passed data around as char data and used offsets to get at the data in them. On one, the programmer didn't even know about structs (Or null string termination.)
Having a "Convenient" language really isn't much of an excuse for not knowing this stuff. My data structures prof deliberatly chose an inconvenient language (BASIC) to show data structure implmentations. You can implement any structure in terms of array if you have to.
It'd be nice if more programmers would actually put some thought into their code before they go and start writing stuff. I wouldn't seek to discourage that...
I'm trying to teach myself to set people on fire with my mind... Is it hot in here?
"Lisp uses only nested linked lists, that can be interpreted as binary trees."
As much as people keep saying it, this is totally false... Common Lisp does not even have lists as an intrinsic type. What it does have are cons cells, several kinds of numbers, symbols, characters, strings, several kinds of vectors and arrays, hash tables, structures, instances, and lexical closures among other types native to the language.
Lists are to Lisp what Strings are to C: a convention built upon more basic structures. In the case of C, a string is a convention built up on null terminated arrays of characters. In the case of Lisp, a list is a series of chained together cons cells.
Purely Functional Datastructures by Okasaki.
Doesn't it make you feel good to know that our freedoms are protected by politicans, lawyers and journalists.
> As much as people keep saying it, this is totally false... Common Lisp does not even have lists as an intrinsic type.
Funny how LISP stands for LISt Processing. And this thread is about data structures, not data types. The cons cell might be the central data type in LISP, but the nested list is the central data structure.
Just think about it. '(a b c) will be recognised as a 3 element list by any LISP programmer, and not as 2 cons cells plus 3 atoms (which would be equally correct). Now you can also construct binary trees with cons cells, but that is more complicated and therefore a bit rare.
Thomas
"Just think about it. '(a b c) will be recognised as a 3 element list by any LISP programmer, and not as 2 cons cells plus 3 atoms (which would be equally correct). "
Actually no... it's 3 cons cells. The syntax (a b c) is shorthand for (a . (b . ( c . ()))). This kind of misunderstanding is precisely why any competent (key word) LISP programmer understands the difference between lists and cons cells I was referring to in my original post. The closest structure with only two cons cells is this (a b . c).
Now, As long as we're being pedantic, what you actually wrote, '(a b c), is shorthand for (quote (a b c)). The numbers of cons cells and atoms in that case is a 'exercise for the reader', but suffice it to say that both your numbers are wrong.