Ask HN: What is your favourite algorithm?
13 comments
The gif on wikipedia (http://i.imgur.com/ZQMaGhj.gif) was actually a very good example. Thanks! :D
Gale–Shapley algorithm (for the stable marriages problem) http://en.wikipedia.org/wiki/Stable_marriage_problem
It's a beautifully simple algorithm with uses in almost every field.
Here's a more informative link http://cse331.wordpress.com/2009/09/11/lect-4-gale-shapley-a...
It's a beautifully simple algorithm with uses in almost every field.
Here's a more informative link http://cse331.wordpress.com/2009/09/11/lect-4-gale-shapley-a...
My favourite would have to be one that I invented myself. I guess like a lot of people here I occasionally end up having to figure out algorithms to solve particular problems. That is one of the most rewarding aspects of being a programmer.
Not sure why cheery was downvoted - it was a legitimate question. Seems like he/she's been hellbanned for no apparent reason.
Anyway, to answer your question I haven't invented anything particularly groundbreaking, just still I need to do my job. Things like 3d collision detection, line-of-sight detection, etc.
As a more concrete example, in the days before broadband I had a problem with transmitting the positions of multiple players in a multi-user game environment. Say you have hundreds of users on dial-up, some with 10ms ping time and others with 100ms. The 10ms users will be able to transmit their position 100 times a second, but the 100ms users can only transmit 10 times a second (assuming they wait for a reply). It doesn't make sense to transmit 100 movement updates to the slow clients, as you'll just overload their connection with unnecessary data. So what is the best solution? The algorithm I came up with is this:
- server maintains "last position" coords plus timestamp for each client - whenever server receives a position update from a client x, it sends the positions of any clients who have sent updates since client x last sent an update
Not groundbreaking, but it took quite a lot of thought to come up with it. The beauty is that it only transmits the data that is needed - the fast clients get fast updates (but without sending any duplicated data), and the slow clients get slow updates. It's simple, elegant and efficient, which is the best type of algorithm.
PS, I don't work in the games industry or with 3d graphics - all that stuff was really just my hobby. I'm pretty sure I've had to come up with some algorithms for the stuff that pays the rent (which is also pretty interesting), although I can't think of any off the top of my head. I did come up with a sound compression algorithm using FFTs, but abandoned it for an off-the-shelf one that worked much better. For the most part it is better to use algorithms that someone else has already figured out and turned into code rather than reinventing the wheel.
Anyway, to answer your question I haven't invented anything particularly groundbreaking, just still I need to do my job. Things like 3d collision detection, line-of-sight detection, etc.
As a more concrete example, in the days before broadband I had a problem with transmitting the positions of multiple players in a multi-user game environment. Say you have hundreds of users on dial-up, some with 10ms ping time and others with 100ms. The 10ms users will be able to transmit their position 100 times a second, but the 100ms users can only transmit 10 times a second (assuming they wait for a reply). It doesn't make sense to transmit 100 movement updates to the slow clients, as you'll just overload their connection with unnecessary data. So what is the best solution? The algorithm I came up with is this:
- server maintains "last position" coords plus timestamp for each client - whenever server receives a position update from a client x, it sends the positions of any clients who have sent updates since client x last sent an update
Not groundbreaking, but it took quite a lot of thought to come up with it. The beauty is that it only transmits the data that is needed - the fast clients get fast updates (but without sending any duplicated data), and the slow clients get slow updates. It's simple, elegant and efficient, which is the best type of algorithm.
PS, I don't work in the games industry or with 3d graphics - all that stuff was really just my hobby. I'm pretty sure I've had to come up with some algorithms for the stuff that pays the rent (which is also pretty interesting), although I can't think of any off the top of my head. I did come up with a sound compression algorithm using FFTs, but abandoned it for an off-the-shelf one that worked much better. For the most part it is better to use algorithms that someone else has already figured out and turned into code rather than reinventing the wheel.
I don't know that I have favorites. That said, Radix sort is kinda cool. It's O(n * k), where k is the number of digits in the number, but it's possible to have k be a constant if there is a limit (like an int can only be so big) meaning you can have an O(n) sort.
Sleepsort of course
#!/bin/bash
function f() {
while [ -n "$1" ]
do
wait
#!/bin/bash
function f() {
sleep "$1"
echo "$1"while [ -n "$1" ]
do
f "$1" &
shift
wait
I really dig AI algorithms like...
http://www.norvig.com/spell-correct.html
Simplicity is beautiful.
http://www.norvig.com/spell-correct.html
Simplicity is beautiful.
I like the Monte Carlo algorithm: http://en.wikipedia.org/wiki/Monte_Carlo_algorithm
Chart parser, http://en.wikipedia.org/wiki/Chart_parser
LSL LSR
PHA PLA
BYT BYT BYT
Shift to the left, Shift to the right, Push-a, Pull-a Byte, Byte, Byte!
Sorry, I just couldn't resist...
Shift to the left, Shift to the right, Push-a, Pull-a Byte, Byte, Byte!
Sorry, I just couldn't resist...
Restricted Boltzmann Machine
It's more of a method than an algorithm, but I'm a big fan of Dynamic Programming.
Viterbi. Beauty.
Insertion sort. Easy to implement (easier than BubbleSort), very fast for small data sets. Can be used in merge sorts / quick sorts when the set size becomes small.
It is a really elegant algorithm and addresses a real-world problem. A teacher of mine once showed us the basic idea behind it:
He connected various bits of wood (=nodes) using strings (=edges). Then he picked up one bit of wood (=starting node) and slowly moved it upwards. Every time when a new node moves, it is an indication that the shortest path between the start node and the new node has been found. He did this until he reached the desired end node. The shortest path between the two nodes is in the end clearly visible, because the path between two nodes A and B that are part of the path between the start and end node is always the shortest path possible.
It is really simple if you think of it as a physical model, unfortunately I could not find a picture of it online :(