5 ms·

Ask HN: What is your favourite algorithm?

16 points by redxblood 13y ago

cpncrunch 13y ago
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.
- cheery 13y ago
  Really? Which algorithm have you invented?
- cpncrunch 13y ago
  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.
blubbi2 13y ago
Dijkstra's algorithm ( http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm ) 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 :(
- jogzden 13y ago
  The gif on wikipedia (http://i.imgur.com/ZQMaGhj.gif http://i.imgur.com/ZQMaGhj.gif) was actually a very good example. Thanks! :D
tbirdz 13y ago
It's more of a method than an algorithm, but I'm a big fan of Dynamic Programming.
alok-g 13y ago
Chart parser, http://en.wikipedia.org/wiki/Chart_parser http://en.wikipedia.org/wiki/Chart_parser
sharemywin 13y ago
Restricted Boltzmann Machine
Rickasaurus 13y ago
Gale–Shapley algorithm (for the stable marriages problem) http://en.wikipedia.org/wiki/Stable_marriage_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-algorithm/ http://cse331.wordpress.com/2009/09/11/lect-4-gale-shapley-a...
WasimBhai 13y ago
Viterbi. Beauty.
junto 13y ago
I like the Monte Carlo algorithm: http://en.wikipedia.org/wiki/Monte_Carlo_algorithm http://en.wikipedia.org/wiki/Monte_Carlo_algorithm
LarryMade2 13y ago
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...
mistabrando 13y ago
Sleepsort of course #!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done wait
lsiebert 13y ago
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.
helpermethod 13y ago
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.
andrewhillman 13y ago
I really dig AI algorithms like... http://www.norvig.com/spell-correct.html http://www.norvig.com/spell-correct.html Simplicity is beautiful.

16 points by redxblood 13y ago

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.

cheery 13y ago
Really? Which algorithm have you invented?
cpncrunch 13y ago
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.

blubbi2 13y ago

Dijkstra's algorithm ( http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm ) 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 :(

jogzden 13y ago
The gif on wikipedia (http://i.imgur.com/ZQMaGhj.gif http://i.imgur.com/ZQMaGhj.gif) was actually a very good example. Thanks! :D

tbirdz 13y ago

It's more of a method than an algorithm, but I'm a big fan of Dynamic Programming.

alok-g 13y ago

Chart parser, http://en.wikipedia.org/wiki/Chart_parser http://en.wikipedia.org/wiki/Chart_parser

sharemywin 13y ago

Restricted Boltzmann Machine

Rickasaurus 13y ago

Gale–Shapley algorithm (for the stable marriages problem) http://en.wikipedia.org/wiki/Stable_marriage_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-algorithm/ http://cse331.wordpress.com/2009/09/11/lect-4-gale-shapley-a...

WasimBhai 13y ago

Viterbi. Beauty.

junto 13y ago

I like the Monte Carlo algorithm: http://en.wikipedia.org/wiki/Monte_Carlo_algorithm http://en.wikipedia.org/wiki/Monte_Carlo_algorithm

LarryMade2 13y ago

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...

mistabrando 13y ago

Sleepsort of course #!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done wait

lsiebert 13y ago

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.

helpermethod 13y ago

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.

andrewhillman 13y ago

I really dig AI algorithms like... http://www.norvig.com/spell-correct.html http://www.norvig.com/spell-correct.html Simplicity is beautiful.