Is there a chart of all rows of data and the listed algorithms?

Question

Is there a chart or table in any place where many (at least popular) data structures and algorithms with their runtime and efficiency are displayed?

What I'm looking for is what I can take a look at and decide which structure / algorithm is best for a particular case. This would be useful when working on a new project or just as a tutorial.

Answer 1

I do not think that such a list exists. The sheer number of well-known algorithms and data structures is staggering, and new ones are being developed all the time. Moreover, many of these algorithms and data structures are specialized, which means that even if you had a list in front of you, it would be difficult to know which ones were applicable to the specific problems you were trying to solve.

Another problem with such a list is how to quantify effectiveness. If you were to evaluate algorithms in terms of asymptotic complexity (big-O), then you could put certain algorithms and data structures that are asymptotically optimal, but impractical at small inputs in front of algorithms, which are known to be fast for practical cases, but theoretically cannot be theoretically. As an example, consider the search for the median median algorithm for linear temporal order statistics, which has such a huge constant coefficient that other algorithms are much better in practice. Or consider quicksort, which in the worst case is O (n ² ), but in practice has an average complexity of O (n log n) and is much faster than other sorting algorithms.

On the other hand, it was necessary to try to list the algorithms for performance, the list would be misleading. Performance is based on a number of factors that depend on the machine and input (for example, locality, input size, input form, machine speed, processor architecture, etc.). This can be useful, usually a trick, but in many cases you can mislead numbers to choose one algorithm when the other is much superior.

There is also implementation complexity. Many algorithms exist only in documents or have reference implementations that are not optimized or written in a language that is not what you are looking for. If you find the Holy Grail algorithm that does exactly what you want but don’t implement it, it can be difficult to compile and debug your own version. For example, if there was no predominance of red / black tree implementations, do you think you can encode it yourself? How about a Fibonacci heap? Or (from personal experience) van Emde Boas? It can often be a good idea to choose a simpler algorithm that is "good enough" but easy to implement with a much more complex algorithm.

In short, I would like for such a table to exist, which really had all this information, but practically speaking, I doubt that it can be constructed in such a way that it is useful. The Wikipedia links from @hammar's comments are actually pretty good, but the best way to find out which algorithms and data structures to use in practice is to practice testing them.

Answer 2

A chart or table will not be a particularly useful link.

If you intend to use a specific algorithm or data structure to solve a problem, you better know and understand it inside and out. And that includes knowing (and knowing how to get) their respective effectiveness. This is not particularly difficult. Most standard algorithms have simple, intuitive N*logN such as N^2 , N*logN , etc.

Speaking of which, Big-O isn’t all about time. For example, sort. A variety heap has a better Big-O than a fast, but fast variety is much better in practice. Constant factors in Big-O can also make a huge difference.

When you talk about data structures, there are more of them than it seems at first glance. For example, a hash map seems like just a tree map with much better performance, but you get an additional sorting structure with a tree map.

Knowing which best algorithm / data structure to use is a matter of knowledge, not a lookup table.

Returning to your question, I do not know any such link. It would be a good exercise to do it yourself. Wikipedia has some pretty decent articles on common algorithms / data structures along with some decent analysis.

Answer 3

Collecting all the algorithms and / or data structures is practically impossible - even when I write this, no doubt, someone invents a new algorithm or data structure somewhere. In a larger scheme of things, this probably does not matter much, but it is still possibly new and (at least slightly) different from everything that has been done before (although, of course, it is always possible that it turns out to be large, an important thing).

However, US NIST has a dictionary of Algorithms and Data Structures Dictionary , which lists more than most people who have ever known or cared for. It covers most of the obvious “big ones” that everyone knows, and terribly many lesser known ones. The University of Canterbury is different , which (or, at least, it seems to me) is a little more modest, but still covers most of the fact that a typical programmer probably cares about them and is a little better organized to find an algorithm to solve a specific problem, and is not based primarily on already knowing the name of the algorithm you want.

There are also various collections / lists that are more specialized. For example, The Stony Brook Algorithm Repository focuses mainly (exclusively?) On combinatorial algorithms. It is based on the Algorithm Design Guide , so it can be especially useful if you use / use this book (and if you are interested, this book is usually very much appreciated).

Answer 4

The first priority for a computer program is correctness, and the second, most of the time, is the programmer’s time — something directly related to mobility and extensibility.

Because of this, there is a programming school that protects simply the use of simple things, such as record arrays, unless this is a part of performance-sensitive, in which case you need to not only consider data structures and algorithms, but also "architechture "which led you to this problem in the first place.