Live data from Hacker News

Faster Than Dijkstra?

systemsapproach.org

31–40 of 90 posts

Re: Faster Than Dijkstra?

#31
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…

"ordering" means arranging things in order by some metric.

"sorting" means assigning things into bins (which are usually ordered).

Re: Faster Than Dijkstra?

#32

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"

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.

Re: Faster Than Dijkstra?

#33
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.

Re: Faster Than Dijkstra?

#34

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"

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.

Re: Faster Than Dijkstra?

#35
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

W is the span or range.

Re: Faster Than Dijkstra?

#36
post #31
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…

"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?

Re: Faster Than Dijkstra?

#37
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

Re: Faster Than Dijkstra?

#38
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…

[deleted]

Re: Faster Than Dijkstra?

#39
post #3

Earlier quoted context omitted.

The Quanta article on the paper was considerably more breathless in describing a fine piece of work in mathematics. The author here points out that one of the things that makes Dijkstra's result iconic is that it could be used practically in a straightforward way. As an engineer, beautiful mathematics is useless if I can't convert it to running code.

Actually there's a whole bunch of mathematics which I find useful as an engineer because it tells me that the perfection I have vaguely imagined I could reach for is literally not possible and so I shouldn't expend any effort on that. e.g Two body gravity I can just do the math and get exact answers out. But for N> 2 bodies that doesn't work and it's not that I need to think a bit harder, maybe crack out some graduat…

> Actually there's a whole bunch of mathematics which I find useful as an engineer because it tells me that the perfection I have vaguely imagined I could reach for is literally not possible and so I shouldn't expend any effort on that

That's actually given as a reason to study NP-completeness in the classic 1979 book "Computers and Intractability: A Guide to the Theory of NP-Completeness" by Garey & Johnson, which is one of the most cited references in computer science literature.

Chapter one starts with a fictional example. Say you have been trying to develop an algorithm at work that validates designs for new products. After much work you haven't found anything better than exhaustive search, which is too slow.

You don't want to tell your boss "I can't find an efficient algorithm. I guess I'm just too dumb".

What you'd like to do is prove that the problem is inherently intractable, so you could confidently tell your boss "I can't find an efficient algorithm, because no such algorithm is possible!".

Unfortunately, the authors note, proving intractability is also often very hard. Even the best theoreticians have been stymied trying to prove commonly encountered hard problems are intractable. That's where the book comes in:

> However, having read this book, you have discovered something almost as good. The theory of NP-completeness provides many straightforward techniques for proving that a given problem is “just as hard” as a large number of other problems that are widely recognized as being difficult and that have been confounding the experts for years.

Using the techniques from the book you prove the problem is NP-complete. Then you can go to your boss and announce "I can't find an efficient algorithm, but neither can all these famous people". The authors note that at the very least this informs your boss that it won't do any good to fire you and hire another algorithms expert. They go on:

> Of course, our own bosses would frown upon our writing this book if its sole purpose was to protect the jobs of algorithm designers. Indeed, discovering that a problem is NP-complete is usually just the beginning of work on that problem.

...

> However, the knowledge that it is NP-complete does provide valuable information about what lines of approach have the potential of being most productive. Certainly the search for an efficient, exact algorithm should be accorded low priority. It is now more appropriate to concentrate on other, less ambitious, approaches. For example, you might look for efficient algorithms that solve various special cases of the general problem. You might look for algorithms that, though not guaranteed to run quickly, seem likely to do so most of the time. Or you might even relax the problem somewhat, looking for a fast algorithm that merely finds designs that meet most of the component specifications. In short, the primary application of the theory of NP-completeness is to assist algorithm designers in directing their problem-solving efforts toward those approaches that have the greatest likelihood of leading to useful algorithms.

Re: Faster Than Dijkstra?

#40
post #33
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.

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

Post reply on HN