7 ms·

It's easy to forget that the original C standards were largely codifying existing practice during an era when using gets() [1] was existing practice. The world

It's easy to forget that the original C standards were largely codifying existing practice during an era when using gets() [1] was existing practice. The world wasn't quite ready for Ada, I guess. Best-laid plans of mice and men etc. etc.. Also, keep an eye out for "amortized" complexity. This does have a legitimately rigorous definition, but for latency-bound paths it can practically amount to "O(whatever), except for the particular invocations that are far, far worse under unspecified conditions". [1] https://www.man7.org/linux/man-pages/man3/gets.3.html#BUGS https://www.man7.org/linux/man-pages/man3/gets.3.html#BUGS

lostcolony 6y ago
...I fully plan to use "O(whatever)". Not sure for what. But, yes. (naive) Quicksort's amortized complexity being O(nlogn), but its O(n^2) on already sorted data, is all I ever needed to learn to take away that lesson. When sorting already sorted data is worse than sorting randomized data, it's a quick realization that "amortized cost" = "read the fine print".
- nyanpasu64 6y ago
  Quicksort as O(n log n) is not amortized complexity, but average runtime for random data.
  - lostcolony 6y ago
    Fair point; I'm confusing my terminology. Analogy and realization still holds.
    - virgilp 6y ago
      Also, already sorted data.. in reverse order. If it's already sorted in the right order, quicksort takes linear time. This is an important difference - data you use might indeed often be appropriately sorted, but in practice will seldom be sorted in reverse order.
      - SuchAnonMuchWow 6y ago
        If it's already sorted in the right order, quicksort runs in O(n log n). quicksort is O(n log n) bestcase, O(n*n) worstcase.
        virgilp 6y ago
        Actually, yeah, my original reply was dumb, I forgot quicksort :) It can be n*n for properly-sorted arrays too, depending on pivot selection (for randomized pivot selection, it's n log n).
        deleted 6y ago
        [deleted]
        lostcolony 6y ago
        Yes; random pivot selection is nlogn (unless you are very, very, statistically impossibly, unlucky. Or using very short arrays where it doesn't matter anyway). But I'm pretty sure data sorted in either direction (i.e., 'reversed' or not, ascending or descending), and taking a pivot from either end, is n^2. It doesn't have to be reversed; you always end up with everything unsorted ending up on one side or the other of the pivot, with each recursive step being just one less comparison than the step prior, meaning it has N-1 + N-2 + ... + 1 comparisons regardless of which way the array is sorted, or N(N-1)/2 comparisons total (Gauss' formula but starting at one less than the total number of items N, since that's the number of comparisons each step), which is O(N^2). There is no cause where it's linear time, unless you are first iterating across the array to select the first pivot that is out of place (which may be a reasonable optimization, but can also be made to apply regardless of what direction the array is sorted).
      - jameshart 6y ago
        On the contrary: very common UI pattern to have a data grid that sorts by a particular column when you click the header, then reverses that sort order when you click the header again. So for a user to sort by date, descending, they click the header, causing an ascending sort, then click it again, causing a descending one. Often such a grid will be quite well abstracted from its data source - it might be executing a remote query to return data in the new order every time - but I bet there are some examples out there that are backed by a local dataset and carry out an actual sort operation when you hit the header... and fall into a quicksort worst case if the user clicks the same header twice in a row.
  - ncmncm 6y ago
    Interestingly, it is quite easy to double the speed of Quicksort, even at this late date, with just a couple-line change. <http://cantrip.org/sortfast.html http://cantrip.org/sortfast.html> Anyway I thought it was interesting.
  - mcguire 6y ago
    Something that is amortized complexity: vector.push(x) Most of the time, it's O(1). Sometimes it's O(n). If you double the size of the backing array when it runs out of space, it's amortized O(1).
    - randomswede 6y ago
      Or triple, or quadruple. Or even (IIRC) "increase by 50%" (but, I would need to sit down and do the actual math on that). But, doubling a number is cheap and more conservative than quadrupling (the next "cheap" multiplier).
- lloeki 6y ago
  I (sadly) have to resort to use "O(scary)" too often for my taste. From: https://stackoverflow.com/a/185576/368409 https://stackoverflow.com/a/185576/368409 /* This is O(scary), but seems quick enough in practice. */
inimino 6y ago
It's also easy to forget that C was competing mainly with assembly, while C++ competed with managed languages. The early C programmer ethos, especially among library authors, was much more along the lines of "look at the generated object code if you want to know what it's doing" while modern practice leans more towards "read the documentation for complexity guarantees". I'm not saying that worse documentation leads to better programmers, but I'm not not saying that either. Practices change, standards change.
- DarkWiiPlayer 6y ago
  Good documentation and inspecting the compiled bytecode are both good ways of finding out about performance characteristics of certain features. The problem starts when people rely on assumptions ("sscanf should be fast because it's widely used") or performance folklore ("localizing every function you'll ever use makes your Lua code faster"), because those tend to either be completely wrong or lack very important context.
  - IggleSniggle 6y ago
    I live in js land, and the barrier between “folklore” and “documentation” is extremely thin. Especially since V8 may introduce changes at any time that affect performance characteristics of js. I’d respond with “well if performance matters it shouldn’t be in js” except for all the shite being written in js these days, with js being the hammer that makes everything else look like a nail.
    - Chyzwar 6y ago
      V8 documents these changes very well[1]. You can write very fast JS code. When carefully written it can have Java like performance[2]. It is just very hard in practice where most ecosystem is optimized for developer productivity. When performance matter, write your own code and carefully benchmark everything. You can see this working for Typescript and VSCode[3] [1] https://v8.dev/blog https://v8.dev/blog [2] https://benchmarksgame-team.pages.debian.net/benchmarksgame/fastest/javascript.html https://benchmarksgame-team.pages.debian.net/benchmarksgame/... [3] https://github.com/microsoft/TypeScript/pull/43035#issuecomment-788535463 https://github.com/microsoft/TypeScript/pull/43035#issuecomm...
alexchamberlain 6y ago
It makes me chuckle when hash maps are stated to be O(1) insertions. Which is true, in respect to the number of items in the map, assuming the map doesn't need resizing and there isn't a hash collision... but it's generally not true in respect to the key length. (I think most implementations are O(ln), where l is the length of the key and n is the number of inserted items, assuming the hash function is O(l) - the _amortised_ runtime would be O(l))
- thaumasiotes 6y ago
  > assuming the map doesn't need resizing This isn't a big difficulty; it's still amortized O(1). > and there isn't a hash collision This is a real difficulty, unless you allow map resizing. Luckily, we do. > but it's generally not true in respect to the key length. OK, but in most cases the key length is constant, making anything that depends on the key length O(1) by definition.
  - TeMPOraL 6y ago
    I'm guessing GP means the complexity guarantee sidesteps the complexity of the hashing function. It probably doesn't matter all that much in typical case - I'm guessing 80-90% of hash map use is with very short strings.
    - thaumasiotes 6y ago
      Short strings, long strings; they're going to use the same key length. Calculating the key may take longer for the long string, if you're basing the hash on the contents of the string[1], but the key won't end up being a different size. The md5 of a 3-byte string is 16 bytes and the md5 of a 40GB string is also 16 bytes. [1] Not typical. e.g. Java takes the hash key of an object to be its address in memory, which doesn't require looking at the contents.
      - iainmerrick 6y ago
        Calculating the key may take longer for the long string Right, that’s exactly what they are warning about. Not typical. e.g. Java takes the hash key of an object to be its address in memory No, that’s just the base implementation in Object (and arguably it was a bad idea). All useful “value type” classes will override it with a real hash of the content, including String. There are some cases in Java where you do want to use IDs instead of values as your map keys, but they’re rare.

lostcolony 6y ago

...I fully plan to use "O(whatever)". Not sure for what. But, yes. (naive) Quicksort's amortized complexity being O(nlogn), but its O(n^2) on already sorted data, is all I ever needed to learn to take away that lesson. When sorting already sorted data is worse than sorting randomized data, it's a quick realization that "amortized cost" = "read the fine print".

nyanpasu64 6y ago
Quicksort as O(n log n) is not amortized complexity, but average runtime for random data.
- lostcolony 6y ago
  Fair point; I'm confusing my terminology. Analogy and realization still holds.
  - virgilp 6y ago
    Also, already sorted data.. in reverse order. If it's already sorted in the right order, quicksort takes linear time. This is an important difference - data you use might indeed often be appropriately sorted, but in practice will seldom be sorted in reverse order.
    - SuchAnonMuchWow 6y ago
      If it's already sorted in the right order, quicksort runs in O(n log n). quicksort is O(n log n) bestcase, O(n*n) worstcase.
      - virgilp 6y ago
        Actually, yeah, my original reply was dumb, I forgot quicksort :) It can be n*n for properly-sorted arrays too, depending on pivot selection (for randomized pivot selection, it's n log n).
        deleted 6y ago
        [deleted]
        lostcolony 6y ago
        Yes; random pivot selection is nlogn (unless you are very, very, statistically impossibly, unlucky. Or using very short arrays where it doesn't matter anyway). But I'm pretty sure data sorted in either direction (i.e., 'reversed' or not, ascending or descending), and taking a pivot from either end, is n^2. It doesn't have to be reversed; you always end up with everything unsorted ending up on one side or the other of the pivot, with each recursive step being just one less comparison than the step prior, meaning it has N-1 + N-2 + ... + 1 comparisons regardless of which way the array is sorted, or N(N-1)/2 comparisons total (Gauss' formula but starting at one less than the total number of items N, since that's the number of comparisons each step), which is O(N^2). There is no cause where it's linear time, unless you are first iterating across the array to select the first pivot that is out of place (which may be a reasonable optimization, but can also be made to apply regardless of what direction the array is sorted).
    - jameshart 6y ago
      On the contrary: very common UI pattern to have a data grid that sorts by a particular column when you click the header, then reverses that sort order when you click the header again. So for a user to sort by date, descending, they click the header, causing an ascending sort, then click it again, causing a descending one. Often such a grid will be quite well abstracted from its data source - it might be executing a remote query to return data in the new order every time - but I bet there are some examples out there that are backed by a local dataset and carry out an actual sort operation when you hit the header... and fall into a quicksort worst case if the user clicks the same header twice in a row.
- ncmncm 6y ago
  Interestingly, it is quite easy to double the speed of Quicksort, even at this late date, with just a couple-line change. <http://cantrip.org/sortfast.html http://cantrip.org/sortfast.html> Anyway I thought it was interesting.
- mcguire 6y ago
  Something that is amortized complexity: vector.push(x) Most of the time, it's O(1). Sometimes it's O(n). If you double the size of the backing array when it runs out of space, it's amortized O(1).
  - randomswede 6y ago
    Or triple, or quadruple. Or even (IIRC) "increase by 50%" (but, I would need to sit down and do the actual math on that). But, doubling a number is cheap and more conservative than quadrupling (the next "cheap" multiplier).
lloeki 6y ago
I (sadly) have to resort to use "O(scary)" too often for my taste. From: https://stackoverflow.com/a/185576/368409 https://stackoverflow.com/a/185576/368409 /* This is O(scary), but seems quick enough in practice. */

inimino 6y ago

It's also easy to forget that C was competing mainly with assembly, while C++ competed with managed languages. The early C programmer ethos, especially among library authors, was much more along the lines of "look at the generated object code if you want to know what it's doing" while modern practice leans more towards "read the documentation for complexity guarantees". I'm not saying that worse documentation leads to better programmers, but I'm not not saying that either. Practices change, standards change.

DarkWiiPlayer 6y ago
Good documentation and inspecting the compiled bytecode are both good ways of finding out about performance characteristics of certain features. The problem starts when people rely on assumptions ("sscanf should be fast because it's widely used") or performance folklore ("localizing every function you'll ever use makes your Lua code faster"), because those tend to either be completely wrong or lack very important context.
- IggleSniggle 6y ago
  I live in js land, and the barrier between “folklore” and “documentation” is extremely thin. Especially since V8 may introduce changes at any time that affect performance characteristics of js. I’d respond with “well if performance matters it shouldn’t be in js” except for all the shite being written in js these days, with js being the hammer that makes everything else look like a nail.
  - Chyzwar 6y ago
    V8 documents these changes very well[1]. You can write very fast JS code. When carefully written it can have Java like performance[2]. It is just very hard in practice where most ecosystem is optimized for developer productivity. When performance matter, write your own code and carefully benchmark everything. You can see this working for Typescript and VSCode[3] [1] https://v8.dev/blog https://v8.dev/blog [2] https://benchmarksgame-team.pages.debian.net/benchmarksgame/fastest/javascript.html https://benchmarksgame-team.pages.debian.net/benchmarksgame/... [3] https://github.com/microsoft/TypeScript/pull/43035#issuecomment-788535463 https://github.com/microsoft/TypeScript/pull/43035#issuecomm...

alexchamberlain 6y ago

It makes me chuckle when hash maps are stated to be O(1) insertions. Which is true, in respect to the number of items in the map, assuming the map doesn't need resizing and there isn't a hash collision... but it's generally not true in respect to the key length. (I think most implementations are O(ln), where l is the length of the key and n is the number of inserted items, assuming the hash function is O(l) - the _amortised_ runtime would be O(l))

thaumasiotes 6y ago
> assuming the map doesn't need resizing This isn't a big difficulty; it's still amortized O(1). > and there isn't a hash collision This is a real difficulty, unless you allow map resizing. Luckily, we do. > but it's generally not true in respect to the key length. OK, but in most cases the key length is constant, making anything that depends on the key length O(1) by definition.
- TeMPOraL 6y ago
  I'm guessing GP means the complexity guarantee sidesteps the complexity of the hashing function. It probably doesn't matter all that much in typical case - I'm guessing 80-90% of hash map use is with very short strings.
  - thaumasiotes 6y ago
    Short strings, long strings; they're going to use the same key length. Calculating the key may take longer for the long string, if you're basing the hash on the contents of the string[1], but the key won't end up being a different size. The md5 of a 3-byte string is 16 bytes and the md5 of a 40GB string is also 16 bytes. [1] Not typical. e.g. Java takes the hash key of an object to be its address in memory, which doesn't require looking at the contents.
    - iainmerrick 6y ago
      Calculating the key may take longer for the long string Right, that’s exactly what they are warning about. Not typical. e.g. Java takes the hash key of an object to be its address in memory No, that’s just the base implementation in Object (and arguably it was a bad idea). All useful “value type” classes will override it with a real hash of the content, including String. There are some cases in Java where you do want to use IDs instead of values as your map keys, but they’re rare.