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

21–30 of 90 posts

Re: Faster Than Dijkstra?

#21

Post by amluto »

SkiFire13 wrote: post #20
qsort wrote: post #13

Earlier quoted context omitted.

Only if you assume a finite alphabet and bounded length. Relax either and you're back to O(n log n) for a fully general solution. Examples of both: tuples and strings. (There's also the problem of how you define your computational model. You can do better than O(n log n) in transdichotomous models. I'm assuming the hand-wavy, naive model the average algorithms class goes along with.)

> Only if you assume a finite alphabet and bounded length You can generally reduce the problem to a finite alphabet by taking the finite subset that actually appears in the input. If you have an unbounded length then you can make sorting O(l n) where `l` is a bound on the lengths of your input. It's still linear in n, and also better than the O(l n logn) you would with traditional comparison based algorithms once you…

> O(l n)

If you don’t have large numbers of repeats of each element, then l needs to scale like O(log n), so O(l * n) is at least O(n log n).

Fundamentally, what’s going on here is that switching between computation models can easily add and remove log factors.

Re: Faster Than Dijkstra?

#22

Post by tpoacher »

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…

You reminded me of "Sleep Sort" [0]

[0] https://news.ycombinator.com/item?id=2657277

Re: Faster Than Dijkstra?

#23

Post by robotpepi »

amluto wrote: post #21
SkiFire13 wrote: post #20

Earlier quoted context omitted.

> Only if you assume a finite alphabet and bounded length You can generally reduce the problem to a finite alphabet by taking the finite subset that actually appears in the input. If you have an unbounded length then you can make sorting O(l n) where `l` is a bound on the lengths of your input. It's still linear in n, and also better than the O(l n logn) you would with traditional comparison based algorithms once you…

> O(l n) If you don’t have large numbers of repeats of each element, then l needs to scale like O(log n), so O(l * n) is at least O(n log n). Fundamentally, what’s going on here is that switching between computation models can easily add and remove log factors.

> so O(l * n) is at least O(n).

I guess you mean "at least O(n*log(n))".

Re: Faster Than Dijkstra?

#24

Post by amluto »

robotpepi wrote: post #23
amluto wrote: post #21

Earlier quoted context omitted.

> O(l n) If you don’t have large numbers of repeats of each element, then l needs to scale like O(log n), so O(l * n) is at least O(n log n). Fundamentally, what’s going on here is that switching between computation models can easily add and remove log factors.

> so O(l * n) is at least O(n). I guess you mean "at least O(n*log(n))".

Indeed, and thanks. I edited it :)

Re: Faster Than Dijkstra?

#26

Post by NooneAtAll3 »

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…

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

Re: Faster Than Dijkstra?

#27

Post by drfuchs »

K0IN wrote: post #18

I can only recommend (for all Germans here) this video from "dorfuchs": https://youtu.be/3ge-AywiFxs?si=TbcRsBNkzGhpOxQ4&t=842 (timestamped=) He shows a derivation that at best, a sorting algorithm can do is O(n log(n)) for n real positive numbers.

From who now?

Re: Faster Than Dijkstra?

#28

Post by WoodenChair »

NooneAtAll3 wrote: post #25

am I missing something? this was a lot of words that sum up to "I heard that new algorithm exists but spent zero effort actually evaluating it"

No, I don't think you're missing anything. He never answered the title of the post ("Faster Than Dijkstra?"). Instead he went on a huge tangent about his experience writing software for routers and is dismissive of the algorithm because the router problem space he was working in did not deal with a node count high enough to warrant the need for a more complex algorithm. Dijkstra's algorithm is used for problem spaces with far higher number of nodes than he mentions... basically an article that talks about some kind of interesting things but doesn't say much about its central question.

Re: Faster Than Dijkstra?

#29

Post by SkiFire13 »

amluto wrote: post #21
SkiFire13 wrote: post #20

Earlier quoted context omitted.

> Only if you assume a finite alphabet and bounded length You can generally reduce the problem to a finite alphabet by taking the finite subset that actually appears in the input. If you have an unbounded length then you can make sorting O(l n) where `l` is a bound on the lengths of your input. It's still linear in n, and also better than the O(l n logn) you would with traditional comparison based algorithms once you…

> O(l n) If you don’t have large numbers of repeats of each element, then l needs to scale like O(log n), so O(l * n) is at least O(n log n). Fundamentally, what’s going on here is that switching between computation models can easily add and remove log factors.

I think you're making some assumptions on n that I'm not making. I'm considering it to be the number of elements to sort, not the size of the input.

Re: Faster Than Dijkstra?

#30

Post by gowld »

usrusr wrote: post #10
gowld wrote: post #5

Earlier quoted context omitted.

More important is that the new algorithm has a multiplicative factor in m (edges), so it's only efficient for extremely sparse graphs. If m > n (log n)^{1/3} Then this algorithm is slower. for 1 Million nodes, if the average degree is >3.5, the new algorithm has worse complexity (ignoring unstated constant factors)

"Any sufficiently sparse graph is indistinguishable from a linked list" comes to mind ;)

A linked list is sparse by the metric of minimum maximum degree (2).

A maximally sparse connected graph by mean (degree edge/node ratio) is any tree (mean degree ~ 1), not necessarily a linked list.

Post reply on HN