4 ms·
> Radix sort is theoretically O(N), Nothing theoretical about it: Sorting a list of all IP addresses can absolutely and trivially be done in O(N) > in reality
by geocar 4y ago
> Radix sort is theoretically O(N),
Nothing theoretical about it: Sorting a list of all IP addresses can absolutely and trivially be done in O(N)
> in reality you can't do better than O(log N)
You can't traverse the list once in <N so the complexity of any sort must be ≥N.
> but memory access is logarithmic
No it's not, but it's also irrelevant: A radix sort doesn't need any reads if the values are unique and dense (such as the case IP addresses, permutation arrays, and so on).
> Edit: I misremembered, memory access is actually O(sqrt(N)): https://github.com/emilk/ram_bench https://github.com/emilk/ram_bench
It's not that either.
The author ran out of memory; They ran a program that needs 10GB of ram on a machine with only 8GB of ram in it. If you give that program enough memory (I have around 105gb free) it produces a silly graph that looks nothing like O(√N): https://imgur.com/QjegDVI https://imgur.com/QjegDVI
The latency of accessing memory is not a function of N.
- FeepingCreature 4y agoThe latency of accessing physical memory is asymptotically a function of N for sufficiently large N - ie. big enough that signal propagation delay to the storage element becomes a noticeable factor. This is not generally relevant for PCs because the distance between cells in the DIMM does not affect timing; ie. the memory is timed based on worst-case delay.
- naasking 4y ago> The author ran out of memory; They ran a program that needs 10GB of ram on a machine with only 8GB of ram in it. No, you can clearly see the O(sqrt(N)) trend at every level of the memory hierarchy.
- geocar 4y ago> No, you can clearly see the O(sqrt(N)) trend at every level of the memory hierarchy. Lines goes up, then goes down. Very much unlike sqrt.
- naasking 4y agoIf you can't see the clear sqrt(N) behaviour in those plots, then I recommend using an online graphic calculator to see what such a graph actually looks like. The sqrt trend is plain as day.
- patrec 4y ago> The latency of accessing memory is not a function of N. How could it not be, given that any physical medium has finite information density, and information cannot propagate faster than the speed of light? And on a practical computer the size of N will determine if you can do all your lookups from registers, L1-L3, or main RAM (plus SSD, unless you disable paging).
- geocar 4y ago> How could it not be, given that any physical medium has finite information density, and information cannot propagate faster than the speed of light? You could have a tape of infinite length, and if you only ever request "the next one" then clearly the latency is constant. > And on a practical computer the size of N ... Don't be silly. N is the size of the input set, not the size of the universe.
- patrec 4y agoI feel we must be talking past each other. I thought the examples so far were about random access of N units of memory. The standard convention of pretending this can be done at O(1) always struck me as bizarre, because it's neither true for practical, finite, values of N (memory hierarchies are a thing) nor asymptotically for any physically plausible idealization of reality.
- aidenn0 4y agoRandom access times are irrelevant for radix sort since no random access to the input data is needed.
- naasking 4y agoYou still need to write each element to the target, which costs O(sqrt(N)), so the "strict" running time of radix sort would be O(N^1.5) in layered memory hierarchies. In flat memory hierarchies (no caching) as found in microcontrollers, it reduces back to O(N).