4 ms·

A related question: why do we even talk about algorithms that assume infinite storage when all our devices are finite? How are they relevant? I think in part i

A related question: why do we even talk about algorithms that assume infinite storage when all our devices are finite? How are they relevant? I think in part it’s because storage limits are platform-specific and context-dependent. Sure, your laptop has a hard drive with limited storage capacity, but how much free space do you have? Running out of disk space isn’t an algorithmic limit, it’s a limit of the environment, which is constantly changing. So this is a way of splitting concerns. When we’re analyzing algorithms, storage capacity is someone else’s problem. It’s not part of the function’s API. (Though, handling running out of storage gracefully might be part of the API, depending on the language.)

kstrauser 2y ago
Because it’s useful to think about whether a thing can be computed if there are no hardware limits involved. If it can, is there an upper bound to those requirements? And if it can’t, then we know it certainly can’t be computed on a physical machine with finite resources.
tialaramex 2y ago
One of the big ideas in the Standard Template Library for C++ was that it should specify big-O complexity values. The idea is that if I know algorithm A is O(N) and algorithm B is O(N) whereas algorithm C is O(log N) then I will know that it's stupid to use both algorithm's A and B together to avoid C, because the complexity of C was actually lower. In practice there's a big problem - big-O isn't good enough for real world engineering decisions. So we need to measure, and if we're measuring why bother defining this in the STL ? There's also a small problem, this forbids, at least notionally, implementations from choosing better options which strictly don't meet the documented criteria. But that problem counts as small because in practice we'll just pretend not to notice and leave the resulting bug reports from pedants in the fix-never pile.
- citizen_friend 2y ago
  I would disagree. The purpose of big O in the STL is not to allow you to compare different algorithms, but allow you to reason about how that will scale with input size. If I test perf with a size of 1000 and then it’s declared to be linear, I have a pretty good idea if that’s the right tool for the job. Do you have any examples of “better” algorithms that the STL is not able to use? Another idea in STL is to provide many algorithms, which is why there are 3 sorts.
  - jcranmer 2y ago
    The most infamous case is that std::unordered_map is essentially required to be a bucket-based hashtable, whereas it's usually better to have a probe-based hashtable instead.
    - tialaramex 2y ago
      The thing that's fascinating for std::unordered_map is that it wasn't standardised in C++ 98. These hash tables are a C++ 11 feature. They feel like a 1980s feature, if there was a hash table in C's stdlib, this is the hash table you'd expect. But it's not in C and it wasn't from the 1980s, it's from the same year Osama Bin Laden was killed by US special forces. Rust existed at the same time this data structure was standardised. Not Rust 1.0, but that's insane, it's like when you realise millions of older Spanish people were alive before their country was a democracy. Many are old enough to remember the prior regime.
      - jcranmer 2y ago
        Well, if you want to be pedantic, std::unordered_map first appears in the C++ working draft in 2006 (N2009), which is before Rust was first publicly announced.
        tialaramex 2y ago
        I do want to be pedantic, but not in a fair way :) The C++ 11 standard was not required to standardize broken garbage from many years ago. WG21 pulled C++ 0x Concepts (a much more powerful feature than the "Concepts Lite" which landed in C++ 20) because they argued it might take too long to implement, ridiculous as that claim is, so there's no reason to keep something terrible just because it's in a draft paper.
    - citizen_friend 2y ago
      Hash maps are extremely difficult to make general which is probably why they were never included in C++98. unordered_map is a disaster.
AdamH12113 2y ago
Computer Science is a sub-field of mathematics. Mathematical concepts usually become more useful, not less, as they become more general. Even elementary ideas like counting and arithmetic don't include practical limits. My favorite example is the concept of periodicity, which is usually defined something like this: A signal x(t) is periodic if, for some nonzero value T (called the period), x(t + T) = x(t) for all t. This implies that all periodic signals are eternal, which is never the case in the real world! But we talk about "periodic" signals all the time because the concept is still useful.

kstrauser 2y ago

Because it’s useful to think about whether a thing can be computed if there are no hardware limits involved. If it can, is there an upper bound to those requirements? And if it can’t, then we know it certainly can’t be computed on a physical machine with finite resources.

tialaramex 2y ago

One of the big ideas in the Standard Template Library for C++ was that it should specify big-O complexity values. The idea is that if I know algorithm A is O(N) and algorithm B is O(N) whereas algorithm C is O(log N) then I will know that it's stupid to use both algorithm's A and B together to avoid C, because the complexity of C was actually lower. In practice there's a big problem - big-O isn't good enough for real world engineering decisions. So we need to measure, and if we're measuring why bother defining this in the STL ? There's also a small problem, this forbids, at least notionally, implementations from choosing better options which strictly don't meet the documented criteria. But that problem counts as small because in practice we'll just pretend not to notice and leave the resulting bug reports from pedants in the fix-never pile.

citizen_friend 2y ago
I would disagree. The purpose of big O in the STL is not to allow you to compare different algorithms, but allow you to reason about how that will scale with input size. If I test perf with a size of 1000 and then it’s declared to be linear, I have a pretty good idea if that’s the right tool for the job. Do you have any examples of “better” algorithms that the STL is not able to use? Another idea in STL is to provide many algorithms, which is why there are 3 sorts.
- jcranmer 2y ago
  The most infamous case is that std::unordered_map is essentially required to be a bucket-based hashtable, whereas it's usually better to have a probe-based hashtable instead.
  - tialaramex 2y ago
    The thing that's fascinating for std::unordered_map is that it wasn't standardised in C++ 98. These hash tables are a C++ 11 feature. They feel like a 1980s feature, if there was a hash table in C's stdlib, this is the hash table you'd expect. But it's not in C and it wasn't from the 1980s, it's from the same year Osama Bin Laden was killed by US special forces. Rust existed at the same time this data structure was standardised. Not Rust 1.0, but that's insane, it's like when you realise millions of older Spanish people were alive before their country was a democracy. Many are old enough to remember the prior regime.
    - jcranmer 2y ago
      Well, if you want to be pedantic, std::unordered_map first appears in the C++ working draft in 2006 (N2009), which is before Rust was first publicly announced.
      - tialaramex 2y ago
        I do want to be pedantic, but not in a fair way :) The C++ 11 standard was not required to standardize broken garbage from many years ago. WG21 pulled C++ 0x Concepts (a much more powerful feature than the "Concepts Lite" which landed in C++ 20) because they argued it might take too long to implement, ridiculous as that claim is, so there's no reason to keep something terrible just because it's in a draft paper.
  - citizen_friend 2y ago
    Hash maps are extremely difficult to make general which is probably why they were never included in C++98. unordered_map is a disaster.

AdamH12113 2y ago

Computer Science is a sub-field of mathematics. Mathematical concepts usually become more useful, not less, as they become more general. Even elementary ideas like counting and arithmetic don't include practical limits. My favorite example is the concept of periodicity, which is usually defined something like this: A signal x(t) is periodic if, for some nonzero value T (called the period), x(t + T) = x(t) for all t. This implies that all periodic signals are eternal, which is never the case in the real world! But we talk about "periodic" signals all the time because the concept is still useful.