Which algorithms are used most often?
Please write a single algorithm per answer, try to keep your answer short (one or two lines).
10
-
$\begingroup$ Kaveh, maybe you should wait for responses before supplying so many ? :) $\endgroup$– Suresh VenkatSep 3, 2010 at 22:36
-
1$\begingroup$ @Suresh: Sorry. :) $\endgroup$– KavehSep 3, 2010 at 22:44
-
3$\begingroup$ Most often in what sense? (Number of different computer programs that implement the algorithm? Number of installed pieces of software that use the algorithm? Number of executions of the algorithm? Amount of data processed by using the algorithm? CPU seconds used by the algorithm?) Where? (Academia, industry, home PCs?) Is it ever possible to estimate anything like this; can we have ever any data to back any of the answers? $\endgroup$– Jukka SuomelaSep 3, 2010 at 22:45
-
1$\begingroup$ The question is too vague as Jukka Suomela pointed out. Without further clarification, the answers will be no better than the table of contents of a textbook on algorithms. $\endgroup$– Tsuyoshi ItoSep 11, 2010 at 20:50
-
1$\begingroup$ There is a recent book: "Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers" by John MacCormick. See press.princeton.edu/titles/9528.html $\endgroup$– Alessandro JacopsonJan 25, 2012 at 17:53
Comments disabled on deleted / locked posts / reviews
|
Show 5 more comments
22 Answers
$\begingroup$
$\endgroup$
1
Is the Fast Fourier Transform the algorithmic problem solved most times per day by real computer systems? It has to be close. So I'd nominate the Cooley-Tukey FFT algorithm.
-
$\begingroup$ I like this, FFT is overlooked in basic computer science education, but it is certainly an algorithm with a tremendous impact in our modern society, and many modern things around us are crunching FFT all the time. $\endgroup$ Sep 4, 2010 at 10:27
$\begingroup$
$\endgroup$
5
Multiplication.
Perhaps one of the oldest not-entirely-trivial algorithms, and a problem that is solved more often than FFT.
-
$\begingroup$ Multiplication isn't an algorithm, it's a problem with many subproblems solved by different algorithms: fixed-size integer and floating-point, performed by hardware or software; variable-size bignums (modulo or not), matrices, ... $\endgroup$ Sep 4, 2010 at 9:58
-
$\begingroup$ I was referring to the hardware multiplication circuits in modern CPUs (for integers and floating-point numbers; these two aren't that different in the end). My understanding is that they tend to be "just" very cleverly engineered versions of the same basic approach – the "long multiplication" algorithm, which was already known in the Middle Ages. $\endgroup$ Sep 4, 2010 at 10:13
-
$\begingroup$ I think that subtraction (comparison) is used much more often than multiplication, and I cannot see any reason why multiplication counts as an algorithm and addition/subtraction does not. However, I do not know if this qualifies as an answer. $\endgroup$ Sep 12, 2010 at 18:08
-
$\begingroup$ Yes, addition and subtraction are used even more often than multiplication – indeed, the long multiplication algorithm essentially reduces a multiplication to an addition. However, I don't know if there is a single addition/subtraction algorithm that we could nominate here? $\endgroup$ Sep 12, 2010 at 21:02
-
$\begingroup$ @JukkaSuomela: Two's complement addition and subtraction would be a good candidate. $\endgroup$ Jan 16, 2012 at 13:57
$\begingroup$
$\endgroup$
1
Dijkstra and Bellman-Ford shortest path algorithms. There are at least 35,000 Autonomous Systems (AS) active on the Internet as of 2010. Each AS is running either a link-state routing protocol (Dijkstra) or a distance-vector routing protocol (Bellman-Ford). The routers within one AS typically update their tables periodically every few minutes, say 10.
Thus, the number of Dijkstra & Bellman-Ford executions per day amounts to at least 5 million. And that's only from the routers.
We have not counted shortest path computations from Google Maps and the likes which should easily account for 10 times as many. Half a billion executions a day is not far-fetched.
-
$\begingroup$ Half a billion executions a day may sound like a lot, but let's keep in mind that we have, e.g., billions of mobile phones on this planet. What are those things doing all the time? Or what are they doing during each phone call? I don't know, but my guess is that they are at the very least doing a lot more of FFT than shortest paths. $\endgroup$ Sep 4, 2010 at 10:24
3
-
14$\begingroup$ By the way, is it really the case that quicksort is the sorting algorithm that is used most commonly in the real world? I had a quick look at the implementation of a general-purpose "sort" function in some commonly used programming languages. Perl: seems to have switched from quicksort to mergesort recently. Python: uses Timsort (mergesort/insertion sort hybrid). Java: used to be mergesort, nowadays Timsort. Databases tend to use external sorting. Is quicksort already an endangered species? $\endgroup$ Sep 3, 2010 at 23:05
-
$\begingroup$ I think that is a very good point. It would be great if someone can edit the answer. $\endgroup$ Jan 16, 2012 at 10:51
-
$\begingroup$ @Juan, although the point Jukka mentioned is correct I don't see any reason to edit the answer. $\endgroup$– KavehJan 16, 2012 at 20:09
$\begingroup$
$\endgroup$
1
I think the most used algorithm is Parity Check (or maybe CRC or some kind of error-correcting code), because they appear in every RAM access.
-
$\begingroup$ Also used at least once for every packet being sent across any IP-based network $\endgroup$ Feb 23, 2011 at 10:02
$\begingroup$
$\endgroup$
Simplex Algorithm - isn't this still competitive with the best interior point methods? If so it has to be used a lot.
$\begingroup$
$\endgroup$
1
More generally, you should look at the Kanellakis prize winners for ideas that have theoretical and practical heft.
-
$\begingroup$ thank you for the link, it looks very interesting. Partial motivation for the question was finding a nice catchy algorithmic name for the site. :) $\endgroup$– KavehSep 3, 2010 at 22:37
$\begingroup$
$\endgroup$
Regular expression matching by conversion to finite automata - I believe grep functions along these lines.
$\begingroup$
$\endgroup$
2
It's hard to think of more widely used algorithms than those in modern implementations of TCP: ie congestion avoidance, fast retransmit. Though that depends on how one determines what meets the criteria for an algorithm...
-
$\begingroup$ But can you really use TCP algorithms more often than FFT (which is already on this list)? If my computer sends a single IP packet (TCP or not), doesn't it typically trigger a whole bunch of FFT calculations? Usually the packets are transmitted at some point by using technologies such as WLAN, ADSL, and GSM, and I think most of them use modulations that rely heavily on FFT. $\endgroup$ Sep 4, 2010 at 9:34
-
$\begingroup$
$\endgroup$
Gaussian Elimination This is still used in practice right? If not replace with whatever is most frequently used to solve linear systems...
$\begingroup$
$\endgroup$
SHA-1 (and hash functions in general). Probably beat most other algorithms in terms of the number of executions.
$\begingroup$
$\endgroup$
B+ tree related algorithms is used in for the database stuffs
$\begingroup$
$\endgroup$
Scheduling algorithms. They are used by every user device and server worldwide. A number of variations is being used, I found a lot of references for "multilevel feedback queue"
$\begingroup$
$\endgroup$
This response interprets "most often" in terms of actual CPU cycles.
When I was learning computing in the '70s I recall reading that the vast majority of computer (read: mainframe) cycles were devoted to sorting. Business applications demand extensive sorting for analysis and reporting. I don't imagine that has changed very much, but of course the rise of other apps--e-mail, word processing, etc.--must have altered the mix. Those sorts are usually stable sorts (not Quicksort) due to the need to sort on successions of fields to create subsorts.
Strictly speaking, though, the algorithm used the most often is, without any doubt, whatever is executed by the Windows system wait process when nothing else otherwise is going on ;-).
$\begingroup$
$\endgroup$
Sprase Matrix Vector Multiply
... is the computational workhorse behind the solution of almost all linear systems. As a result it is being run whenever
- Scientists/engineers solve differential equations
- Statisticians find new correlations (PCA)
- Google runs pagerank
- Your phone predicts your location from GPS, accelerometers, cell tower locations
- Your car adjusts your suspension in motion
- etc....
Most of the FLOPs on any supercomputer or cluster are spent inside of a sparse mat-vec.
$\begingroup$
$\endgroup$
Newton's method. It's used for computing square roots, for computing division. It can be used to do linear programming. More generally it's the workhorse of (convex) optimization. It can be used to solve differential equations in Physics by minimizing the action/energy.
$\begingroup$
$\endgroup$
Hashing and red-black trees.
They're already implemented in STL (hash_map, map), and every programmer knows that such a container is incredibly convenient whenever you want to store some information indexed by an arbitrary data type.
$\begingroup$
$\endgroup$
Error correction algorithms, such as Reed-Solomon.
http://en.wikipedia.org/wiki/Error-correcting_code#List_of_error-correcting_codes http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction
$\begingroup$
$\endgroup$
1
I think DP is used "more often" than other algorithms cited in the survey so far. I infer "more often" in the sense of how often a non-trivial algorithm concept was implemented by programmer in real-life, rather than how many time a particular implementation of an algorithm in invoked.
DP is versatile, and has many faces. Sometimes I used it somewhat subconsciously and then realized later I was doing DP.
Of course, there are things that are even more common than Dynamic Program, but they are mostly data structure (array, linked list, hash).
-
7$\begingroup$ This is a bit different from the other suggestions as it is an algorithm design paradigm (similar to greedy or primal-dual) and not just a single algorithm. $\endgroup$ Sep 4, 2010 at 10:31
$\begingroup$
$\endgroup$
String Matching, used all the time in application software and on database level.
In the exact case, there are several quite involved algorithms (KMP, Boyer-Moore) with some that achieve sublinear expected runtime. They are also interesting to study from a CS point of view.
Approximate string matching, that is alignments, is probably even more interesting. You know "autocorrecting" features? Also, searches in noisy string data (e.g. DNA) is done using alignments.