Advanced Data Structures? 118
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?"
Canonical Terms of Academia (Score:5, Insightful)
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 [amazon.com]. 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.
Re: (Score:3, Interesting)
Good point. While it doesn't cover everything, it is hardly an "Introduction". I've been programming for 20 years (including kernels). This book fits the 80/20 rule - covering 80% of what I've need
Re: (Score:2)
I didn't get this too much in college, and got a little in grad school, but I went on to some self discovery afterwards and I gotta tell ya, Design Patterns are a must when it comes to doing OO design. Design patterns can be used in any structured design method as well, it just takes some creativity... I use this online link [dofactory.com], which is really co
Re:Canonical Terms of Academia (Score:5, Insightful)
Design patterns is a book about Object Oriented design, aimed at the C++/Java level of abstraction. In low level languages it is clumbsy to write them, and in higher ones, unnecessary.
Re: (Score:2)
What an interesting statement.
Seriously? No design patterns are useful in "higher level" languages?
Could you please elaborate?
Re: (Score:1)
Different patterns for different machinery (Score:1)
Re: (Score:2)
Design patterns are almost all obvious to a decent programmer--you probably invented them before you ever heard of them. Knowing design patterns means that you and I can discuss Iterators without redefining what they mean each time we talk to someone new.
How is that need replaced by these new languages?
Also, you say the need for "Design Patterns" is eliminated??? Every s
Re: (Score:2)
Re: (Score:2)
16 of 23 patterns have a qualitatively simpler implementation in Lisp
-Visitor is unnecessary in Multi-dispatch polymorphism (as mentioned in the book it is a hand written implementation)
-To be cheeky singleton is unnecessary when you have globals
Re: (Score:3, Insightful)
The patterns aren't about how to implement something--they are all trivial to implement, I've yet to see one that I didn't create and implement myself before the books were even concieved of.
The big things about design patterns are that you have a common name for a pattern and some code smells to look for that indicate the need for a pattern. Because yo
Re: (Score:2)
Well, it's about generalization, loose coupling and that kind of stuff. Lots of polymorphism. Orthogonal to algorithm work, and not always something you want to invest programming time and CPU cycles info.
Re: (Score:2)
The things commonly known as "Design Patterns" are really just several implementations of one of the two real patterns: The Human Compiler at Work. You have to do that stuff by hand because your language is not powerful enough.
The other real pattern, is macros (as in lisp macros). That is, extend your language to do that stuff for you.
Re: (Score:1)
Design Patterns might not be what he's looking for. Design Patterns (in my experience) tend to map well to OO concepts and/or are described in OO concepts, kernel programming, however, does not fit well with the OO concept. I think he might be better of sticking to advanced data structures and algorithms rather than patterns if he wants to appl
data structures books (Score:4, Informative)
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.
Re: (Score:2)
I highly recommend this book (all of its volumes). From what the original poster wrote I believe that is what he is looking for.
There is a limit of precooked data structures that you will find in books but reading Knuth works (anyone of them) will make allow you to develop a highly abstract thinking that will allow you to create the *right* structure for your work. I would also recommend his "Concrete Mathematics" book.
Re: (Score:1)
Re: (Score:1)
Re: (Score:1)
If you want design patterns, the seminal book is Gamma, Helm, Johnson, and Vlissides text "Design Patterns: Elements of Reusa
Re: (Score:1)
Re: (Score:2)
Re: (Score:1)
I have to completely agree with this. I don't use Knuth much because he is heavy on the math, but Sedgewick pared all that down and said use this if you are doing this, and use this other thing if your going to be doing this.
Even if you aren't using C, I recommend "Expert C Programming: Deep C Secrets" by Peter van der Linden. It is simply the best programming book I have ever read. Clear, funny, and full of explanations of all those things that aren't explained in classes or other books that have you
If you can use C++ I recommend the STL (Score:2, Insightful)
Are you trying to code a linked-list, or are you trying to solve a problem?
Re: (Score:2)
Dang kybard!
*Yes, that's a Dilbert reference*
Re: (Score:1)
Re: (Score:2)
Re: (Score:2)
Why not? It's not like you have to use STL, MFC, multiple inheritance, and covariance just because you happen to use C++. C++ offers several advantages over C, and which features you decide to use, and where, is up to you. C is not perfect. There's little reason to stick to it, except tradition. C++ certainly isn't perfect either, but it has some advantages over C.
Unix succeded pretty much because it was one of the first OS-kernels that was not
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
As far as structu
Okasaki book (Score:3, Informative)
Link lists? (Score:4, Funny)
Re:Link lists? (Score:5, Insightful)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
The great thing about programming for the virtual memory manager is that arrays that take up a few TB aren't wasteful of anythig except effective address space.
Cheers,
Matt
Re: (Score:2, Funny)
Re: (Score:2)
Re: (Score:1)
It has been years since I actually looked at the code, but certainly back in the 2.4.x days the Linux kernel scheduler made use of linked lists (along side some clever pointer arithmetic that made for interesting reading.)
Re: (Score:1)
Re: (Score:2)
Just kidding... You can stop having a hearth attack...
Re: (Score:2)
Re: (Score:2)
In the object-oriented, application world, if-then-else is the new GOTO. Most if's I see today could be replaced with inheritance.
Re: (Score:2)
Re: (Score:1)
Using GOTO can be useful to "linearise" the execution flow such as in
Re: (Score:2)
Re: (Score:3, Interesting)
KISS! (Score:3, Insightful)
WTF? People who try to move cleverness in low-level critical code should be shot. Look, there's a time and a place for everything, but this is the wrong approach for the problemspace you're working in. You didn't say which kernel you're working with, but odds are extremely good that it already comes with a set of pre-defined macros or functions for handling data structures. Use them. They're much better tested and understood than the stuff you want to play with, and much less likely to make your codevelopers hate you.
I don't want to be a stick in the mud, but seriously, this just isn't the place to start experimenting.
Re: (Score:2)
Re:KISS! (Score:5, Informative)
http://en.wikipedia.org/wiki/List_of_data_structu
Re: (Score:2)
Out of curiosity, what problem are you trying to solve that is not covered by an existing data structure?
What are you missing? (Score:2)
You forgot arrays (very useful!), but maybe that is just too trivial. Anyway, what exactly are you missing? Most problems I know can be solved using these basic data-structures, or a combination thereof.
If you really want to, you can actually get by with just one data-structure:
Lisp uses only nested linked lists, that can be interpreted as binary trees.
Perl only really knows hashes. Arrays and lists
Re: (Score:2)
Re: (Score:2)
Re: (Score:2, Insightful)
The only way to improve on this in slower data structures is to use radix-style keying to cheat, so that your lookup keys tell you exactly how to find the value you're looking for. But this isn't really an "advanced" data structure, just an optimization of a basic one. (In fact, a lot of "advanced" data structures are just such application-specific optimizations; radix keyin
Re: (Score:2)
It depends on which operations have to be O(lg n). Operations that don't traverse the entire structure can be more efficient.
Re: (Score:3, Interesting)
Now if what you are actually looking for is some fun how about embedding neko [nekovm.org] in the kernel, because while you can add some cool things like say tries (prefix trees) the real performance bottleneck is between apps and the kernel. Neko could safely ca
Re:What are you missing? (Score:5, Interesting)
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...
byte-order independence (Score:2, Interesting)
Although mentioned in a negative light,
This technique is important when you have to move data between big-endian and little-endian processors. It lets you write portable I/O routines.
Re:What are you missing? (Score:5, Informative)
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.
Re: (Score:1)
A list is typically just a value and another list. A cons cell *is* a list that just happens to support some extra operations.
Re:What are you missing? (Score:4, Informative)
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
Re:What are you missing? (Score:4, Informative)
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.
Re: (Score:3, Funny)
Dude, I was arguing on Slashdot about the number and proper usage of data types in Lisp, of all things... I think looking like an ass was pretty much a part of the deal from the get go.
Re: (Score:1)
But you wear it so well!
Based on your argument C doesn't have arrays, just pointers with some syntactic sugar.
Re: (Score:3, Insightful)
Well, we're all 'special' in our own unique ways.
To be frank, I wouldn't have been quite so harsh (ass-like, if you wish) if he hadn't just happened to make one of mistakes that proved exactly my point about the difference between cons cells and lists.
"Based on your argument C doesn't have arrays, just pointers with some syntactic sugar."
I'd actually agree with that.... A bit of trivia: in C, what's the difference between a[b] and b[a]?
Re: (Score:2)
So you posted to let me know that I was posting in spite of the fact that, as I posted, the original poster was no longer posting. Does that about sum it up?
Lewis & Denenberg (Score:2)
Not an encyclopedia, like CLR(S) or Knuth, but rather a tutorial of many useful data structures and algorithms. Doesn't have the breadth of the "encyclopedic" books but what it covers, it covers very well.
The drawback of this book, from your perspective, is that it isn't C-specific. It's usually transparent how to translate the code into C (or anything similar) but you can't just paste it into your code.
Red-Black Trees Not Good Enough? (Score:1)
And as someone already pointed out, use the predefined macros. Failing that you can always check out
http://lxr.linux.no/ [linux.no]
And to who ever made the comment about using lists in kernel source... *sigh* probably not worth it.
Re: (Score:2)
There have been times when red-black trees are too expensive, because they have 2 pointers per node and I can't afford the memory overhead. It's amazing how much memory gets wasted when you add an 8 byte pointer to a 0x10 byte struc
Re: (Score:2)
Too expensive is relative. You can optimise most of the overhead away, but you still have to store 0x10 byte per structure. Investing a lot of work just to reduce the memory usage by 30% is *usually* not worth it, although there are cer
Re: (Score:2)
Eh, that only works if you're traversing the list, not if you can possibly jump into the tree from a direct pointer to the object.
Of course, for things where you really only always just traverse the list, this would be fine...an interesting concept actually. Guess it's another instance of "use the correct tool for the task at hand."
Computer Algorithms / C++ (Score:2, Informative)
"patterns" (Score:2)
Data Structures and Algorithms (Score:5, Informative)
Re: (Score:1)
Re: (Score:2)
Be grateful he was asking you to design it and not execute it.
--MarkusQ
P.S. For that matter, it should be pretty easy to design an algorithm that does this, based around a wave front (work out from one end, kill all paths when they reach the other end, unless there is only one, which is the longest).
Re: (Score:2)
Re: (Score:2)
My parenthetical comment was just a sketch; obviously (by the usual meaning of "longest path") you wouldn't ever use the same arc twice, so cycles don't matter.
--MarkusQ
Network algorithms (Score:3, Informative)
E.g., my professor used network algorithms when writing the software that matches medical schools and students. Each school prioritizes it's candidate students, each student prioritizes his schools. The program finds the best matches. He said it had taken many hours (12 hours?) to do originally, but with the network flow it was a few minutes on an old kaypro.
Another example was determining when teams are mathematically eliminated from playoffs. It sounds like a simple problem, but it isn't since a team could lose a game yet remain in the running because a different team lost its own game.
A decade ago these algorithms would be overkill for a kernel. Today... I can definitely see how these algorithms could make a difference in some places.
Re: (Score:2)
Why is that hard? I was wondering how baseball magic numbers were calculated recently, and it only took me about 2 minutes to figure it out.
Magic Number = Games in Season - Wins by First Place team - Losses by 2nd place team + 1
As long as that is above zero, the 2nd place team
Re: (Score:2)
We'll not even mention tie breaker rules that m
Amazon referer (Score:1)
Good idea, wish I thought of it first.
Really advanced data structures... (Score:2)
If you are just looking to refresh your memory, or learn a
Algorithms and Data Structures in C++ (Score:2)
Judy Arrays (Score:2)
If you make a few macros or inline functions for them, then using them everywhere becomes practical.
A complete book online for free (Score:4, Informative)
Tomes of delphi (Score:2)
The Handbook of Algorithms and Data Structures (Score:1)
The Algorithm Design Manual (Score:1)
Goodrich and Tamassia (Score:1)
Algorithm Design Manual (Score:2)
Handbook of Algorithms and Data Structures (Score:1)
http://www.amazon.com/Handbook-Algorithms-Data-St
quit trying to be clever (Score:2)
Make stuff ONLY as complex as it NEEDS to be. That's the job of a good engineer.
If you're bored, perhaps you're struggling with the fact that 80% of what is done with computers today ONLY requires linked lists, hashes, and that dull "generic" stuff to get the job done.
No need to build the Golden Gate Bridge to span the 10 foot wide creek in your back yard. In fact,
MOD PARENT UP (Score:1)
Book reviews (Score:2)
Look at the ACCU book reviews [accu.org], preferably by subject [accu.org] for books on Algorithms [accu.org] and Data structures [accu.org] (there's a lot of overlap).
Judy Arrays (Score:1)
Flamebait or fact (Score:1)
Sounds to me like you're looking for a cookbook. Not to learn. Programming is an art and a science. You have to learn how to walk before you run and run before you fly. You cannot become a kernel programmer just by learning only those things you THINK are needed to program a kernel.
That's li
Algorithm Design (Score:1)