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

61–70 of 90 posts

Re: Faster Than Dijkstra?

#61

Post by shoo »

hinkley wrote: post #58

Graph Theory and AI have been forever linked because it turns out the human brain is ridiculously good at finding a path through a graph that is somewhere in the neighborhood of 97% optimal, and we can do it in minutes while a computer would take weeks or until the heat death of the universe to do it better. It's vexatious how good we are at it, and it's exactly the sort of problem that Science likes. We know it's tr…

standard algorithms for single-source/single-dest pathfinding scale log-linearly in the size of the graph, so compared to other combinatorial optimisation problems, optimal pathfinding is incredibly easy for computers to do & scales pretty well to industrial-sized problems. computers can also do optimal pathfinding for problems that humans would not be able to solve easily (because the graphs don't easily embed in 2d or 3d, say, so we can't bring our vision systems to bear)

other combinatorial optimisation problems - like the traveling salesman you mention - are much harder than pathfinding to solve optimally or even approximately

Re: Faster Than Dijkstra?

#62

Post by tialaramex »

mjcohen wrote: post #60
tialaramex wrote: post #55

Earlier quoted context omitted.

That paper explains some useful optimisation details, but obviously since the floats are all (either infinity or) some multiple of a known tiny fraction (their smallest non-zero number), we can definitely sum them accurately.

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 integer type on a modern CPU.

Now lets try f64, the big daddy, 11 exponent, 52 fraction, 1 sign bit so total 2048 + 52 + 1 = 2101 bits. As I said it doesn't fit in our machine integer types but it's much smaller than a kilobyte of RAM.

Edited: I can't count, though it doesn't make a huge difference.

Re: Faster Than Dijkstra?

#63

Post by michaelt »

emil-lp wrote: post #36
myhf wrote: post #31

Earlier quoted context omitted.

"ordering" means arranging things in order by some metric. "sorting" means assigning things into bins (which are usually ordered).

This is news to me. Source?

That's because it's not true.

https://www.merriam-webster.com/dictionary/ordering

Order - transitive verb - 1. to put in order : arrange - "The books are ordered alphabetically by author."

noun - 4. b(1) the arrangement, organization, or sequence of objects or of events - "alphabetical/chronological/historical order" "listed the items in order of importance"

https://www.merriam-webster.com/dictionary/sorting

Sort - transitive verb - 1. to put in a certain place or rank according to characteristics - "sort the mail" "sorted the winners from the losers" "sorting the data alphabetically"

noun - 5. an instance of sorting - "a numeric sort of a data file"

Re: Faster Than Dijkstra?

#64

Post by vlovich123 »

marcosdumay wrote: post #49
NooneAtAll3 wrote: post #26

Earlier quoted context omitted.

counting sort is O(nW), where W is largest value if you don't care about W or it is essentially constant - then it can be dropped but it is an input parameter that will change execution time

It's O(n+W), not O(n*W). > if you don't care about W or it is essentially constant - then it can be dropped Also, every algorithm that ends in a real computer is bound to a constant time. That's still not a practical thing to do.

The simplification is correct but not correctly stated (even though colloquially it's common to state it that way). Technically it's when some component of the algorithm is dwarfed by another, then you can exclude it (i.e. O(n+W) =~ O(n) when W TLDR: You're being unhelpfully pedantic.

Re: Faster Than Dijkstra?

#65

Post by GuB-42 »

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 memory cell is proportional to the cube root of the amount of memory cells we will have to access. And since the speed of light is finite, it is also a cube root in time.

So "constant time" is actually cube root on a real computer. And I am generous by saying "real". Real real computers have plenty of stuff going on inside of them, so in practice, complexity analysis at the O(log(n)) level is meaningless without considering the hardware details.

Going from log(n) to log2/3(n) is just an exercise in mathematics, it may lead to practical applications, but by itself, it doesn't mean much for your software.

Re: Faster Than Dijkstra?

#66

Post by MoltenMan »

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…

Most of this is very true, except for the one caveat I'll point out that a space complexity O(P(n)) for some function P implies at least a O(cubedroot(P(n))) time complexity, but many algorithms don't have high space complexity. If you have a constant space complexity this doesn't factor in to time complexity at all. Some examples would be exponentiation by squaring, miller-rabin primality testing, pollard-rho factorization, etc.

Of course if you include the log(n) bits required just to store n, then sure you can factor in the log of the cubed root of n in the time complexity, but that's just log(n) / 3, so the cubed root doesn't matter here either.

Re: Faster Than Dijkstra?

#67

Post by mabbo »

Many years ago, as an undergrad, I had a conversation with a grad student friend about the Selection algorithm (which will find the kth largest item in an unsorted list in O(n) time). I loved it, but when I tested it in practice it was slower than just sorting and selecting well into the billions of elements.

My friend said "that may be true, but consider the philosophical implication: because that algorithm exists, we know it's possible to answer the question in O(n) time. We once didn't know that, and there was no guarantee that it was possible. We might still be able to find a better O(n) algorithm."

I feel the same way about this. Sure, this might not be faster than Dijkstra's in practice, but now we know it's possible to do that at all.

Re: Faster Than Dijkstra?

#68

Post by aGHz »

emil-lp wrote: post #36
myhf wrote: post #31

Earlier quoted context omitted.

"ordering" means arranging things in order by some metric. "sorting" means assigning things into bins (which are usually ordered).

This is news to me. Source?

https://dictionary.cambridge.org/dictionary/english/sort

to put a number of things in an order or to separate them into groups: Paper, plastic, and cans are sorted for recycling.

sort something into something I'm going to sort these old books into those to be kept and those to be thrown away.

sort something by something You can use the computer to sort the newspaper articles alphabetically, by date, or by subject.

sort (through) She found the ring while sorting (through) some clothes.

Re: Faster Than Dijkstra?

#69

Post by rkomorn »

michaelt wrote: post #63
emil-lp wrote: post #36

Earlier quoted context omitted.

This is news to me. Source?

That's because it's not true. https://www.merriam-webster.com/dictionary/ordering Order - transitive verb - 1. to put in order : arrange - "The books are ordered alphabetically by author." noun - 4. b(1) the arrangement, organization, or sequence of objects or of events - "alphabetical/chronological/historical order" "listed the items in order of importance" https://www.merriam-webster.com/dictionary/sorting Sort - t…

I don't get how this disagrees with what GGP wrote.

Re: Faster Than Dijkstra?

#70

Post by rramadass »

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…

> understand the actual specific problem you need to solve, not the abstract general problem. Understand the statistical distribution of actual problem instances, they'll have parameters in some range. Understand the hardware you're building writing software for, understand its finite capacity & capability.

Very much in line with what James Coplien and colleagues described with "Commonality and Variability Analysis" and "Family-oriented Abstraction, Specification, and Translation" (FAST) for Software Engineering in the 90's. Coplien's PhD thesis titled Multi-Paradigm Design and book titled Multi-Paradigm Design for C++ is based on this approach.

Commonality and Variability in Software Engineering (pdf) - https://www.dre.vanderbilt.edu/~schmidt/PDF/Commonality_Vari...

Multi-Paradigm Design (pdf of PhD thesis) - https://tobeagile.com/wp-content/uploads/2011/12/CoplienThes...

Post reply on HN