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

41–50 of 90 posts

Re: Faster Than Dijkstra?

#41

Post by _bernd »

_bernd wrote: post #16
alias_neo wrote: post #7

Deja Vu. I read this article a few days ago I'm sure, word-for-word, but it wasn't on this site in OP? It stood out because when it mentioned textbooks and said "including ours" I looked at the site and thought to myself "they do textbooks?".

> and thought to myself "they do textbooks?". Indeed: https://systemsapproach.org/books-html/ If you are cheap on money, but you do have time, and like to get into networking, I can only highly recommend https://book.systemsapproach.org/

The link to https://book.systemsapproach.org/internetworking/routing.htm... is in the first paragraph.

Re: Faster Than Dijkstra?

#42

Post by vlovich123 »

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.

If the primary key is the number, it still works (and dates are just numbers by the way) because you can sort a heterogenous dataset by a single numeric key pretty trivially.

But sorting by arbitrary strings like names can’t avoid comparison sort.

Re: Faster Than Dijkstra?

#44

Post by jalacira »

Epa095 wrote: post #37
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…

Usually when one talk about sorting, without specifying closer, one means comparison sort [1], which indeed has an average-case lower bound of O(n*log(n)). In more special cases all kinds of other runtimes are possible. 1: https://en.wikipedia.org/wiki/Comparison_sort

[dead]

Re: Faster Than Dijkstra?

#45

Post by Jtsummers »

fn-mote wrote: post #43

Should have a more conspicuous link to the Quanta article that it references if not the original. (It’s there, just not on the top.) https://www.quantamagazine.org/new-method-is-the-fastest-way... https://arxiv.org/abs/2504.17033

He links to those in the first two sentences. How is that not "on the top"?

Re: Faster Than Dijkstra?

#46

Post by moffkalast »

Jtsummers wrote: post #34
moffkalast wrote: post #32

Earlier quoted context omitted.

What I'm missing is certainly what the hell the algorithm even is and what is its complexity. This guy just rambles about old switches.

> What I'm missing is certainly what the hell the algorithm even is and what is its complexity. https://arxiv.org/pdf/2504.17033 - Linked from the second sentence of the submission, not hard to track down. And the complexity (by which I presume you mean algorithmic complexity) is stated in the submission and in the PDF linked by the submission and that I just shared with you.

I did eventually find that yes, after sifting through the rest of the useless links, the quantamagazine article that says jack shit, the link to the ACM symposium call for submissions (lmao). Like come on, why label that "underlying research"?

And all of that was wasted time since it seems that this just isn't at all applicable to A* heuristics the way Dijkstra's is. It's only an improvement in a very specific case.

Re: Faster Than Dijkstra?

#47

Post by CaptainNegative »

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…

> You can generally reduce the problem to a finite alphabet by taking the finite subset that actually appears in the input.

You can generally sort any array in constant time by taking that constant to be the time it takes to sort the array using bubble sort.

Re: Faster Than Dijkstra?

#48

Post by shiandow »

qsort wrote: post #13
shiandow wrote: post #12

Interestingly sorting is O(N) for a surprisingly large class of datatypes. Anything that behaves well with lexicographic sorting really. Supposing one uses a 'trie' as a priority queue, the inserts and pops are effectively constant.

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.)

Both are true in practice, so not unreasonable. For graph weights that is, not sorting.

That said the finite alphabet and bounded length requirements can be softened a bit. Even for general sorting algorithms.

I mean, for the kind of lexicographic sotable data we're talking about you can basically pick a convenient alphabet size without cost.

And unbounded length is not that big an obstruction. Sure you are going to need O(n log(n)) comparisons. But you can't compare data of unbounded length in constant time anyway. In the end you end up taking an amount of time that is at least proportional to the amount of data, which is optimal up to a constant factor. And if you fiddle with radix sort enough you can get it within something similar.

Basic ASCII strings and tuples aren't that big an obstruction. Fractions are more complicated.

Really the O(n log(n)) for comparison based sorts and O(N) for radix sort mean something different. One is the number of comparisons to the number of elements, and the other closer to the number of operations per amount of data. Though that assumes O(1) swaps, which is technically incorrect for data that doesn't fit a 64 bit computer.

Re: Faster Than Dijkstra?

#49

Post by marcosdumay »

NooneAtAll3 wrote: post #26
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

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.

Re: Faster Than Dijkstra?

#50

Post by lscharen »

pvillano wrote: post #40
hinkley wrote: post #33

Earlier quoted context omitted.

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.

To be pedantic, median is cheaper than sorting. O(n) with a quicksort-like algorithm. Also, if you're taking an average of floating point numbers, you might want to sort it first and add from smallest to largest, to better preserve precision

An aside, but I recently learned -- if one is willing to use a very modest amount of memory -- summing floating-point numbers with no loss of precision is effectively a solved problem with the XSUM algorithm.

https://glizen.com/radfordneal/ftp/xsum.pdf

Post reply on HN