5 ms·

In the big-Oh algorithmic complexity sense; in a loose sense, for any pair of implementations (radix sort, kr sort) there exists a word size w and a list size n

In the big-Oh algorithmic complexity sense; in a loose sense, for any pair of implementations (radix sort, kr sort) there exists a word size w and a list size n such that If either w or n increases, the time for radix sort would increase more quickly than for Kr sort - and this, eventually kr would be faster and keep getting faster. (Assuming that the hash can indeed yield average O(1) access, which is probabilistically but not deterministically true) That said, word size w is, in almost all integer dieting problems, bounded by 128 (by 64 or even 32 with high probability) which makes it acceptable to regard as “constant” in which case both sorts are essentially O(n) and it all depends on specific implementations (with radix sort likely significantly faster in practice)

adrianN 6y ago
Big-O as commonly used in the CS literature sometimes doesn't translate to Big-O on actual computers. For example virtual memory translation can add a log term where you wouldn't expect it: https://pdfs.semanticscholar.org/1e90/c55362cf7793dc0b2521f61752f2d0135e12.pdf https://pdfs.semanticscholar.org/1e90/c55362cf7793dc0b2521f6...
- jnxx 6y ago
  Yeah. I am wondering since a while whether well-known algorithms like the binary heap are still efficient on modern architectures, because their random memory access patterns.
  - lorenzhs 6y ago
    For priority queues, which implementation is optimal depends a lot on your workload (do you need addressability, i.e., a decreaseKey operation? What is the typical ratio of insertions to deletions? Are your keys integers?). I found some slide decks that are mostly in English with some German in between that might go some way to answering your question: [1] https://algo2.iti.kit.edu/sanders/courses/algen20/vorlesung.pdf https://algo2.iti.kit.edu/sanders/courses/algen20/vorlesung.... slide 180-207, there are some up-to-date measurements on slide 204 [2] https://nms.kcl.ac.uk/stefan.edelkamp/lectures/ae/slide/AE-AllgemeineVorrangwarteschlangen.pdf https://nms.kcl.ac.uk/stefan.edelkamp/lectures/ae/slide/AE-A... There are also parallel priority queues which might be useful depending on your problem, especially if it can be reformulated to operate on batches ("give me the 20 smallest items", "insert these 50 items").
  - contravariant 6y ago
    Look up cache-oblivious algorithms. Turns out that random memory access can often be improved upon with smart data structures.
- the8472 6y ago
  The paper mentions huge tables but considers their use uncommon, that has changed since then, at least on linux.
- lorenzhs 6y ago
  That's a common misunderstanding of what "Big-O" is, but rephrased as "the models used for algorithm analysis assume very simple machines that don't represent actual computers all that well" your point is very valid. There's a whole lot of things that our computers do that aren't accounted for in the RAM model (which is most commonly used when analysing sequential algorithms). Memory hierarchies are a big one (the external memory model accounts for a two-level hierarchy, and can be used to reason about cache usage or external memory ("out-of-core")), but other things such as branch (mis-)predictions or virtual memory translation (TLB) are rarely accounted for. That's what the field of Algorithm Engineering is about: designing algorithms that have good worst case guarantees ("Big-O") but that are also really fast when implemented on real-world hardware. (Given the publication list on your website, you probably know all this, but I wanted to expand on it for others)
  - Certhas 6y ago
    There is the idea that you should treat memory access as an O(N^.5) operation: https://github.com/emilk/ram_bench https://github.com/emilk/ram_bench I am not sure if any serious academic work has been built on this model, but it's a nice short hand.
    - lorenzhs 6y ago
      Well the problem with that is "this is a curve that roughly fits the data" is a bad way to go about constructing a model. It's a useful and neat observation, but that doesn't make it a good model. It might model random accesses to memory reasonably well (such as traversing a linked list, the example used there), but it doesn't model a scan over an array well. That doesn't make for a useful model. In contrast, the external memory model assumes a fast internal memory of size M (e.g., cache), which can be accessed in constant time, and a slow external memory of infinite size (e.g., RAM) which can only be accessed in blocks of size B (e.g., a cache line). Then you count how many blocks the algorithm needs to read or write. Now, scanning an array of size N takes O(N/B) I/Os, whereas scanning a linked list of the same size takes O(N) I/Os. The complexity of sorting is O(N/B log(N/B)/log(M/B)) I/Os. This models the same behaviour in a much cleaner way, applies equally to all levels of the memory hierarchy (you can also view RAM as the internal memory and a hard disk/SSD as the external memory), and is widely used in what you called "serious academic work" :) See also https://en.wikipedia.org/wiki/External_memory_algorithm https://en.wikipedia.org/wiki/External_memory_algorithm Furthermore, the introduction in the article you linked misunderstands Big-O notation so incredibly fundamentally that I don't think the author has done their background reading on machine models and Big-O notation.
- kurlberg 6y ago
  An amusing, surprising and in hindsight obvious lower bound for average random access speed in an array containing N "words" is N^(1/3) (cube root of N.) I.e., for any realizable computer without new physics.

adrianN 6y ago

Big-O as commonly used in the CS literature sometimes doesn't translate to Big-O on actual computers. For example virtual memory translation can add a log term where you wouldn't expect it: https://pdfs.semanticscholar.org/1e90/c55362cf7793dc0b2521f61752f2d0135e12.pdf https://pdfs.semanticscholar.org/1e90/c55362cf7793dc0b2521f6...

jnxx 6y ago
Yeah. I am wondering since a while whether well-known algorithms like the binary heap are still efficient on modern architectures, because their random memory access patterns.
- lorenzhs 6y ago
  For priority queues, which implementation is optimal depends a lot on your workload (do you need addressability, i.e., a decreaseKey operation? What is the typical ratio of insertions to deletions? Are your keys integers?). I found some slide decks that are mostly in English with some German in between that might go some way to answering your question: [1] https://algo2.iti.kit.edu/sanders/courses/algen20/vorlesung.pdf https://algo2.iti.kit.edu/sanders/courses/algen20/vorlesung.... slide 180-207, there are some up-to-date measurements on slide 204 [2] https://nms.kcl.ac.uk/stefan.edelkamp/lectures/ae/slide/AE-AllgemeineVorrangwarteschlangen.pdf https://nms.kcl.ac.uk/stefan.edelkamp/lectures/ae/slide/AE-A... There are also parallel priority queues which might be useful depending on your problem, especially if it can be reformulated to operate on batches ("give me the 20 smallest items", "insert these 50 items").
- contravariant 6y ago
  Look up cache-oblivious algorithms. Turns out that random memory access can often be improved upon with smart data structures.
the8472 6y ago
The paper mentions huge tables but considers their use uncommon, that has changed since then, at least on linux.
lorenzhs 6y ago
That's a common misunderstanding of what "Big-O" is, but rephrased as "the models used for algorithm analysis assume very simple machines that don't represent actual computers all that well" your point is very valid. There's a whole lot of things that our computers do that aren't accounted for in the RAM model (which is most commonly used when analysing sequential algorithms). Memory hierarchies are a big one (the external memory model accounts for a two-level hierarchy, and can be used to reason about cache usage or external memory ("out-of-core")), but other things such as branch (mis-)predictions or virtual memory translation (TLB) are rarely accounted for. That's what the field of Algorithm Engineering is about: designing algorithms that have good worst case guarantees ("Big-O") but that are also really fast when implemented on real-world hardware. (Given the publication list on your website, you probably know all this, but I wanted to expand on it for others)
- Certhas 6y ago
  There is the idea that you should treat memory access as an O(N^.5) operation: https://github.com/emilk/ram_bench https://github.com/emilk/ram_bench I am not sure if any serious academic work has been built on this model, but it's a nice short hand.
  - lorenzhs 6y ago
    Well the problem with that is "this is a curve that roughly fits the data" is a bad way to go about constructing a model. It's a useful and neat observation, but that doesn't make it a good model. It might model random accesses to memory reasonably well (such as traversing a linked list, the example used there), but it doesn't model a scan over an array well. That doesn't make for a useful model. In contrast, the external memory model assumes a fast internal memory of size M (e.g., cache), which can be accessed in constant time, and a slow external memory of infinite size (e.g., RAM) which can only be accessed in blocks of size B (e.g., a cache line). Then you count how many blocks the algorithm needs to read or write. Now, scanning an array of size N takes O(N/B) I/Os, whereas scanning a linked list of the same size takes O(N) I/Os. The complexity of sorting is O(N/B log(N/B)/log(M/B)) I/Os. This models the same behaviour in a much cleaner way, applies equally to all levels of the memory hierarchy (you can also view RAM as the internal memory and a hard disk/SSD as the external memory), and is widely used in what you called "serious academic work" :) See also https://en.wikipedia.org/wiki/External_memory_algorithm https://en.wikipedia.org/wiki/External_memory_algorithm Furthermore, the introduction in the article you linked misunderstands Big-O notation so incredibly fundamentally that I don't think the author has done their background reading on machine models and Big-O notation.
kurlberg 6y ago
An amusing, surprising and in hindsight obvious lower bound for average random access speed in an array containing N "words" is N^(1/3) (cube root of N.) I.e., for any realizable computer without new physics.