5 ms·

Basically algorithmic complexity analysis often ignores the cost of accessing data because the underlying storage is sometimes unknown - be it in memory, on a s

Basically algorithmic complexity analysis often ignores the cost of accessing data because the underlying storage is sometimes unknown - be it in memory, on a spinning disc or on magnetic tape. Unfortunately that gives suboptimal algorithms because that basic practically is ignored. You then end up with a bunch of algorithms that look worse “on paper” but still outperforms the theoretically optimal ones. Often the number of items is also ignored. If you want to implement a set-like feature but you’ll be using less than X elements, you can often get better performance just using a linear search through an array than use a full fledged hashed set.

jsmith45 5y ago
Agreed. There are plenty of cases where an asymptotically "worse" algorithm performs better than a "better" one for all practical sizes. Like it is very very much possible that the asymptotically "better" algorithms have coeffcients so high that the break even point takes like week or more of computation. There are not many programs where users will tolerate using it with so much data that operations take that long.
munificent 5y ago
This reads like a criticism of complexity analysis, but really you're just describing it. By definition and by design, algorithmic complexity analysis only shows you how an algorithm behaves asymptotically. That means it's often not the right tool for selecting an algorithm with optimal real-world performance, but I think that's less a fault of the tool than it is a fault of the tool selector. Saying, "complexity analysis ignores constant factors and small-data size performance" is sort of like saying "hammers ignore the threading on screws".
- Retric 5y ago
  Saying something is a poor fit in the real world is a perfectly valid criticism. Arguably complexity analysis is such a poor fit programmers should never actually use it, but vastly simplifying problems can make for a good first approximation.
  - alex_smart 5y ago
    Saying "why do we teach programmers complexity analysis in a word RAM model, there are no idealized RAM machines that behave like that in the real world" is no better than saying "why do we teach people Euclidean geometry, there are no such idealized geometrical systems in the real world". The point is that: 1. The analysis is useful and instructive. 2. It teaches you how to analyse computing models, starting from a simple one, so that when you need to, you can build and analyse more complex models specific to your domain.
    - Retric 5y ago
      In the real world spacetime is very close to Euclidean geometry near earth. Complexity analysis on the other hand can be wrong by literal orders of magnitude. If carpenters needed to worry about the internal angles of a triangle a ding up to between 9,672 and 1.72 degrees then I think people would consider Euclidean geometry a waste of time, but 180 +/- 0.0000001 is fine.
      - alex_smart 5y ago
        You are responding to an argument I never made. You don't teach children Euclidean because they would actually ever need to calculate the area of a triangle. You teach them geometry because it is a good exercise in working with logic, proofs and mathematical models. >Complexity analysis on the other hand can be wrong by literal orders of magnitude. Seeing how complexity analysis only applies to the asymptotic behavior of an algorithm, I don't even know how to make any semantic sense of that statement. It is not even wrong.
        Retric 5y ago
        > only applies to asymptotic behavior. This is false, complex analysis is vastly more than just Big O, other resources like memory usage are also considered as are exact results.
        5y ago
MatteoFrigo 5y ago
What you are saying may be a valid criticism of basic undergraduate algorithms courses, but it is a bit unfair as an absolute criticism of the field. There exists a huge literature that studies algorithms under various models of the memory hierarchy, and under various models of I/O. Even Knuth's venerable The Art of Computer Programming from 50 years ago studied the problem of optimal sorting assuming that the data is on tape and one has six tape drives available (for some value of six that I forgot).
- svat 5y ago
  Not many people realize that the literature you mention is the field of "analysis of algorithms", which is a sub-field of (or, in practice, somewhat different from) computational complexity theory / theory of algorithms. Robert Sedgewick (CS professor at Princeton, and an early PhD student of Knuth) has a great book with Flajolet on Analysis of Algorithms [1], and in one of the lectures from his course [2] makes a distinction between the complexity analysis usually taught in basic undergraduate algorithms courses (he calls O-notation not the scientific method, in a certain context in the lecture) and AofA (which involves saying "Running time is ~aN^c" instead of saying "Running time is O(N^c)", and also actually measuring against real programs) — watch the video or read the slides; it's an interesting distinction. And the Purdue website [3] is even better at giving a sense of the field. [1]: https://aofa.cs.princeton.edu https://aofa.cs.princeton.edu [2]: https://aofa.cs.princeton.edu/online/slides/AA01-AofA.pdf https://aofa.cs.princeton.edu/online/slides/AA01-AofA.pdf / https://www.coursera.org/learn/analysis-of-algorithms/lecture/LAXjA/a-scientific-approach https://www.coursera.org/learn/analysis-of-algorithms/lectur... [3]: https://aofa.cs.purdue.edu https://aofa.cs.purdue.edu
jjgreen 5y ago
I recently had occasion to re-implement the R-tree structure [1] which I based on the original code by Guttman. There, each set of child nodes were stored in a (hard-coded 1k) page of memory, but there was a macro which allowed n sets of child-nodes in a page, but that value was set to 1. I assumed that this was an experiment which turned out to not work, hence the hard-coded 1 to disable it. As the code was nearing completion I experimented with values other than 1, and found a 3-fold increase in speed for a value of n=8 (IIRC) against a 4k memory page. It's always worth testing your assumptions :-) [1] http://soliton.vm.bytemark.co.uk/pub/jjg/en/code/librtree/ http://soliton.vm.bytemark.co.uk/pub/jjg/en/code/librtree/

jsmith45 5y ago

Agreed. There are plenty of cases where an asymptotically "worse" algorithm performs better than a "better" one for all practical sizes. Like it is very very much possible that the asymptotically "better" algorithms have coeffcients so high that the break even point takes like week or more of computation. There are not many programs where users will tolerate using it with so much data that operations take that long.

munificent 5y ago

This reads like a criticism of complexity analysis, but really you're just describing it. By definition and by design, algorithmic complexity analysis only shows you how an algorithm behaves asymptotically. That means it's often not the right tool for selecting an algorithm with optimal real-world performance, but I think that's less a fault of the tool than it is a fault of the tool selector. Saying, "complexity analysis ignores constant factors and small-data size performance" is sort of like saying "hammers ignore the threading on screws".

Retric 5y ago
Saying something is a poor fit in the real world is a perfectly valid criticism. Arguably complexity analysis is such a poor fit programmers should never actually use it, but vastly simplifying problems can make for a good first approximation.
- alex_smart 5y ago
  Saying "why do we teach programmers complexity analysis in a word RAM model, there are no idealized RAM machines that behave like that in the real world" is no better than saying "why do we teach people Euclidean geometry, there are no such idealized geometrical systems in the real world". The point is that: 1. The analysis is useful and instructive. 2. It teaches you how to analyse computing models, starting from a simple one, so that when you need to, you can build and analyse more complex models specific to your domain.
  - Retric 5y ago
    In the real world spacetime is very close to Euclidean geometry near earth. Complexity analysis on the other hand can be wrong by literal orders of magnitude. If carpenters needed to worry about the internal angles of a triangle a ding up to between 9,672 and 1.72 degrees then I think people would consider Euclidean geometry a waste of time, but 180 +/- 0.0000001 is fine.
    - alex_smart 5y ago
      You are responding to an argument I never made. You don't teach children Euclidean because they would actually ever need to calculate the area of a triangle. You teach them geometry because it is a good exercise in working with logic, proofs and mathematical models. >Complexity analysis on the other hand can be wrong by literal orders of magnitude. Seeing how complexity analysis only applies to the asymptotic behavior of an algorithm, I don't even know how to make any semantic sense of that statement. It is not even wrong.
      - Retric 5y ago
        > only applies to asymptotic behavior. This is false, complex analysis is vastly more than just Big O, other resources like memory usage are also considered as are exact results.
        5y ago

MatteoFrigo 5y ago

What you are saying may be a valid criticism of basic undergraduate algorithms courses, but it is a bit unfair as an absolute criticism of the field. There exists a huge literature that studies algorithms under various models of the memory hierarchy, and under various models of I/O. Even Knuth's venerable The Art of Computer Programming from 50 years ago studied the problem of optimal sorting assuming that the data is on tape and one has six tape drives available (for some value of six that I forgot).

svat 5y ago
Not many people realize that the literature you mention is the field of "analysis of algorithms", which is a sub-field of (or, in practice, somewhat different from) computational complexity theory / theory of algorithms. Robert Sedgewick (CS professor at Princeton, and an early PhD student of Knuth) has a great book with Flajolet on Analysis of Algorithms [1], and in one of the lectures from his course [2] makes a distinction between the complexity analysis usually taught in basic undergraduate algorithms courses (he calls O-notation not the scientific method, in a certain context in the lecture) and AofA (which involves saying "Running time is ~aN^c" instead of saying "Running time is O(N^c)", and also actually measuring against real programs) — watch the video or read the slides; it's an interesting distinction. And the Purdue website [3] is even better at giving a sense of the field. [1]: https://aofa.cs.princeton.edu https://aofa.cs.princeton.edu [2]: https://aofa.cs.princeton.edu/online/slides/AA01-AofA.pdf https://aofa.cs.princeton.edu/online/slides/AA01-AofA.pdf / https://www.coursera.org/learn/analysis-of-algorithms/lecture/LAXjA/a-scientific-approach https://www.coursera.org/learn/analysis-of-algorithms/lectur... [3]: https://aofa.cs.purdue.edu https://aofa.cs.purdue.edu

jjgreen 5y ago

I recently had occasion to re-implement the R-tree structure [1] which I based on the original code by Guttman. There, each set of child nodes were stored in a (hard-coded 1k) page of memory, but there was a macro which allowed n sets of child-nodes in a page, but that value was set to 1. I assumed that this was an experiment which turned out to not work, hence the hard-coded 1 to disable it. As the code was nearing completion I experimented with values other than 1, and found a 3-fold increase in speed for a value of n=8 (IIRC) against a 4k memory page. It's always worth testing your assumptions :-) [1] http://soliton.vm.bytemark.co.uk/pub/jjg/en/code/librtree/ http://soliton.vm.bytemark.co.uk/pub/jjg/en/code/librtree/