Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Faster Than Dijkstra?

systemsapproach.org

Post reply on HN
Print view View original

71–80 of 90 posts

Re: Faster Than Dijkstra?

#71

Post by layer8 »

GuB-42 wrote: post #65
shoo wrote: post #54

The underlying argument this article seems to be making is that an appropriate algorithm for any given application isn't always the one with the most efficient asymptotic performance for sufficiently large n -- for a given application (in this case routing), we have data on typical values of n that appear in reality and we can choose an algorithm that offers good enough (or optimal) performance for n in that constrai…

I came to realize that logs don't matter. O(log(n)) and O(1) are effectively the same thing. The reason is that real computers have memory, accessing memory takes time, and bigger n needs more memory, simply to store the bits that represent the number. Already, we have a factor of O(log(n)) here. But also each bit of memory takes physical space, we live in a 3D world, so, best case, on average, the distance to a memo…

> Already, we have a factor of O(log(n)) here.

Doesn’t that mean that O(log(n)) is really O(log²(n))?

Re: Faster Than Dijkstra?

#72

Post by fsckboy »

GuB-42 wrote: post #65
shoo wrote: post #54

The underlying argument this article seems to be making is that an appropriate algorithm for any given application isn't always the one with the most efficient asymptotic performance for sufficiently large n -- for a given application (in this case routing), we have data on typical values of n that appear in reality and we can choose an algorithm that offers good enough (or optimal) performance for n in that constrai…

I came to realize that logs don't matter. O(log(n)) and O(1) are effectively the same thing. The reason is that real computers have memory, accessing memory takes time, and bigger n needs more memory, simply to store the bits that represent the number. Already, we have a factor of O(log(n)) here. But also each bit of memory takes physical space, we live in a 3D world, so, best case, on average, the distance to a memo…

>logs don't matter. O(log(n)) and O(1) are effectively the same thing.

ever heard of a hashtable? that's because O(c) is better than O(log(N)). if they were the same, you would only have heard of binary search.

Re: Faster Than Dijkstra?

#73

Post by onecommentman »

vprcic wrote: post #17

Each time a discussion about sorting starts, I'm reminded of a "lively debate" I had with my boss/friend about the most optimal sorting approach. He claimed it's O(n) pointing to counting sort as an example. This didn't sit well with me. A sorting algorithm, I insisted, should be defined something like "a function taking an unsorted array of elements and returning a sorted one". But it seems there is no agreed upon d…

Obligatory mention of the linear time analog sorting algorithm known as the “spaghetti algorithm”.

https://en.wikipedia.org/wiki/Spaghetti_sort

https://every-algorithm.github.io/2023/11/25/spaghetti_sort....

The equivalent for positive link weight shortest paths is the “string algorithm” — build the network out of string and pull taut between the two knots/nodes, the resulting set of taut links is the shortest path.

Re: Faster Than Dijkstra?

#74

Post by chowells »

fsckboy wrote: post #72
GuB-42 wrote: post #65

Earlier quoted context omitted.

I came to realize that logs don't matter. O(log(n)) and O(1) are effectively the same thing. The reason is that real computers have memory, accessing memory takes time, and bigger n needs more memory, simply to store the bits that represent the number. Already, we have a factor of O(log(n)) here. But also each bit of memory takes physical space, we live in a 3D world, so, best case, on average, the distance to a memo…

> logs don't matter. O(log(n)) and O(1) are effectively the same thing. ever heard of a hashtable? that's because O(c) is better than O(log(N)). if they were the same, you would only have heard of binary search.

Please explain to me how you can hash n distinct strings into O(n) buckets in O(1) time. Please note that this process needs to work as n goes to infinity.

Hash tables are O(log n) structures when you don't hand-wave away the "compute a hash" part. The thing is, search trees are far worse than that in practice and you aren't hand-waving away the "compare two elements" part. That's where the real speed savings come from.

Re: Faster Than Dijkstra?

#75

Post by thfuran »

layer8 wrote: post #71
GuB-42 wrote: post #65

Earlier quoted context omitted.

I came to realize that logs don't matter. O(log(n)) and O(1) are effectively the same thing. The reason is that real computers have memory, accessing memory takes time, and bigger n needs more memory, simply to store the bits that represent the number. Already, we have a factor of O(log(n)) here. But also each bit of memory takes physical space, we live in a 3D world, so, best case, on average, the distance to a memo…

> Already, we have a factor of O(log(n)) here. Doesn’t that mean that O(log(n)) is really O(log²(n))?

You have to define what n is.

Re: Faster Than Dijkstra?

#76

Post by thbb123 »

Even Knuth, in TAOP, acknowledges that using O(n) asymptotic behavior as a measure of performance is just a heuristic and not an absolute.

Cache-awareness and structure discovery are 2 important tools of the engineer to optimize practical problems.

If we wanted a reliable measure of the difficulty of a problem instance, it should rely on a function of O(K(n)) where K is the kolmogorov complexity of the input.

Re: Faster Than Dijkstra?

#77

Post by geocar »

hinkley wrote: post #33
vprcic wrote: post #17

Each time a discussion about sorting starts, I'm reminded of a "lively debate" I had with my boss/friend about the most optimal sorting approach. He claimed it's O(n) pointing to counting sort as an example. This didn't sit well with me. A sorting algorithm, I insisted, should be defined something like "a function taking an unsorted array of elements and returning a sorted one". But it seems there is no agreed upon d…

I can’t think of a single time I’ve needed a sorted list of only numbers. It’s always numbers and something else, like names or dates. Maybe for median calculations, but I don’t even use those that much either. Especially in telemetry, where mean is easy and median is not.

> I can’t think of a single time I’ve needed a sorted list of only numbers.

Gosh. Let me try to convince you.

I use permutation arrays all the time: lists of indexes that can be used across multiple vectors.

This is much faster than the pattern of scanning rows, constructing tuples of (thingToSort . thingIWantInThatOrder) and making a custom sort function, and destructuring those tuples...

And really, not having to write custom sort functions is really really nice.

> Especially in telemetry, where mean is easy and median is not.

Funny. Yes median is obvious with a permutation array, and maybe mean is less so.

When your data is really big and not very variable, mean of x is roughly the same as the mean of any sufficient sample of x, and that sample can be meaningfully represented as a permutation array!

You can get such an array with reservoir sampling and some maths, and (depending on what you know of your data and variance) sometimes even simpler tricks.

That's kindof actually how the "faster than dijkstra" trick referred-to in the article works: Data sets with small variance has this same property that the min of x is roughly the same as the min of a sufficient sample of x (where the size of sufficient has to do with the variance). And so on.

Another big use-case in my code is trees: Apter trees have a flat memory layout which is convenient for permutation arrays which can simultaneously represent index, rotation, tombstones, and all sorts of other things you might need to do with a tree.

Give it a dig. There's good stuff in there.

Re: Faster Than Dijkstra?

#78

Post by LegionMammal978 »

tialaramex wrote: post #62
mjcohen wrote: post #60

Earlier quoted context omitted.

Not if the ratio between the largest and smallest floats is very large (2^(2^n)) where n is the number of bits in the exponent.

I think you either haven't thought about this or you did your math wrong. You need (2^e)+m+1 bits. That is more bits than would fit in the cheap machine integer type you just have lying around, but it's not that many in real terms. Let's do a tiny one to see though first, the "half-precision" or f16 type, 5 bits of exponent, 10 bits of fraction, 1 sign bit. We need 43 bits. This will actually fit in the 64-bit signed…

You also need some extra bits at the top so that it doesn't overflow (e.g., on an adversarial input filled with copies of the max finite value, followed by just as many copies of its negation, so that it sums to 0). The exact number will depend on the maximum input length, but for arrays stored in addressible memory it will add up to no more than 64 or so.

Re: Faster Than Dijkstra?

#79

Post by tialaramex »

LegionMammal978 wrote: post #78
tialaramex wrote: post #62

Earlier quoted context omitted.

I think you either haven't thought about this or you did your math wrong. You need (2^e)+m+1 bits. That is more bits than would fit in the cheap machine integer type you just have lying around, but it's not that many in real terms. Let's do a tiny one to see though first, the "half-precision" or f16 type, 5 bits of exponent, 10 bits of fraction, 1 sign bit. We need 43 bits. This will actually fit in the 64-bit signed…

You also need some extra bits at the top so that it doesn't overflow (e.g., on an adversarial input filled with copies of the max finite value, followed by just as many copies of its negation, so that it sums to 0). The exact number will depend on the maximum input length, but for arrays stored in addressible memory it will add up to no more than 64 or so.

Thanks, you're right there for accumulating excess, I don't think you can actually get to 64 extra bits but sure, lets say 64 extra bits if you want a general purpose in memory algorithm, it's not cheap but we shouldn't be surprised it can be done.

Re: Faster Than Dijkstra?

#80

Post by [deleted] »

chowells wrote: post #74
fsckboy wrote: post #72

Earlier quoted context omitted.

> logs don't matter. O(log(n)) and O(1) are effectively the same thing. ever heard of a hashtable? that's because O(c) is better than O(log(N)). if they were the same, you would only have heard of binary search.

Please explain to me how you can hash n distinct strings into O(n) buckets in O(1) time. Please note that this process needs to work as n goes to infinity . Hash tables are O(log n) structures when you don't hand-wave away the "compute a hash" part. The thing is, search trees are far worse than that in practice and you aren't hand-waving away the "compare two elements" part. That's where the real speed savings come f…

[deleted]
Post reply on HN