Basic Data Structures and Algorithms in the Linux Kernel
cstheory.stackexchange.com
cstheory.stackexchange.com
EDIT: Removed part of my comment, per the blog author's response below.
I didn't meant to blog spam, not sure why the submitter didn't link to the original content.
In addition to getting a better understanding the standard data structures, hearing a candidate say "well the Java collections library uses this strategy..." is a strong positive signal.
[1]: http://codingforinterviews.com
[2]: He suggested reading the libraries here: http://www.docjar.com/html/api/java/util/HashMap.java.html
I encountered many of these while reading through Understanding The Linux Kernel [0] and The Linux Programming Interface [1].
Both are great books which are primarily about the "how" of the kernel, but cover a lot of the "why" of the design and algorithms as well.
I actually have that book as well. I don't know how I forget to mention it. As I recall, it was bit less dense than the other two.
After buying it I found The Linux Programming Interface... and I certainly regretted having bought the former rather than the later. But for beginners I recommend the first.
So this whole e-NFA / NFA / DFA / regex topic is at least one provably complete way you can translate from 'ls *.html' into a whole bunch of gates and FFs in hardware.
There are of course usually ways a smart-ish human can make a faster less general more specific hardware implementation. But its real handy for language designers etc to know that based on CS theory its impossible to write a regex that can't, eventually, be turned into operating hardware.
Now you can add features to regex until you screw that up, if you try hard enough, but I can't think of any good examples at this time. And not all added features screw it up either, some pretty obvious syntactic sugar homomorphisms don't do anything other than make regexes easier for humans to write and understand.
Can anyone provide one such example, please?
http://en.wikipedia.org/wiki/Powerset_construction#Complexit...
It's not really french though, more like french words that are used and are now part of the english language.
Raison d'être just means 'why is it there'.
I know what you mean, but this is correct french, as in the french use it to denote the exact same thing.[1] There are many French phrases that change meaning as they are ported to English, but this is not one of there.
[1] http://fr.wikipedia.org/wiki/Raison_d%27%C3%AAtre_(homonymie...
My other problem with algorithms textbooks is that I get into arguments with other developers about how much we need them. At least here, I can say "Look bucko, the Linux kernel itself uses them."
I decided we can do programming at the API level and never have to think to how that API gives us the right answer. Lower-level programming is responsible for optimization when our number of data points gets larger.
And we could go even lower level and ask why the algorithms work in the first place - which is the computer science aspect. I routinely deal with developers who feel they do not have time for this.
Also, if the data is small enough scale, we can brute-force it and nobody will notice.
Up to that point, this (new) headmaster was seen by the students as "that non-tech guy here to administrate the school" and he was opening my eyes on the biggest codebase residing on my own computer that I never bothered looking through: the Linux kernel code.
As someone says further down the comments, this is not a specific Linux thing: looking at how Java HashMaps works or how Ruby implements "map" are great resources and you'll always get bonus points in an interview for referencing algorithms from "proven" source codes.
I wonder what I missed out on by glossing over things like red-black trees.
You can use GPL'd code for your work?
embedded work is different, in that you often embed your container in your data-structure, so you end up with something like:
typedef struct {
int x;
int y;
Point *next;
} Point;
Point* find_list(Point* p, int x, int y);He meant that GP is so dumb that he is forced to use Linux .h in his project (along with all arch dependencies) rather than to take 5 minutes and code it from scratch. And that he is ignorant of licensing matters of GPL'd code or, more likely, he just doesn't give a f_ck about them. That'd be the gist of what ExpiredLink meant.
Each frame the particles move a little bit, and the camera moves a little bit.
That means that in a given frame most, if not all, of the particles are probably already sorted. In addition, if the sort order has changed, it's probably only requires swaps of adjacent particles.
Because of this, bubble sort is often best sort to use for this operation.
you have a small (3-5) fixed size array that you need to sort with very simple code.
A classic case is to enforce a defined lock ordering when you have more than two locks in dynamic objects that you all need to acquire. In this case open coded bubble sort is good and beats calling a complicated library function.
The other case is your objects are known to be nearly already sorted. In this case bubble sort is a very good algorithm too (although it may be better to avoid a full sort then)
In short bubble sort is often a good choice when anything else would be over engineered.
To expand on this point: simplicity ("just do what you need") is often under valued.
One simple data structure trick I learned recently (from Knuth) is: people often use complicated balanced tree libraries like b or rb. You only need a balanced tree library when the sort keys are in-balanced. One simple trick is to hash the input keys. As long as your hash function is good enough, the keys will be already spread out and you can then use a much simpler non balanced tree.
Come on guys, we need to save valuable and expensive disk space for those oh so precious "http://lmgtfy.com/" questions.
You can find on topic high detail accurate cited analysis of technical questions everywhere else on the internet (insert sarcasm); stack exchange is not for that; its for people who are somehow smart enough to use SE but not smart enough to use google.
And that's the value of this HN article; SE has made itself irrelevant, so when a valuable gem floats by in its sewer, unless someone points the gem out, no one will ever see it again.
Its too bad, the tech behind SE, and some of its ideas, and obviously the subject matter, could obviously create a better site than SE.
How sad. How sad and lame.
I recently asked for an opinion on the fastest algorithm to layout elements on a webpage (something I consider should be Web Developers 101 and actually didn't found anything on google) and my question got closed promptly because 'it was not constructive'. Come on...