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?
What do you do when you sort your washing?
Faster Than Dijkstra?
51–60 of 90 posts
Re: Faster Than Dijkstra?
#52Earlier 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?
"The children were sorted in to two lines by gender then ordered by height"
You might substitute "sorted by height" but its certainly not a correction. While "ordered into lines" would be an error.
Re: Faster Than Dijkstra?
#53Earlier 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.
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.
Suppose you have n elements to sort and you don't have duplicates. Each element is a string of L fixed size symbols (bits, bytes, whatever). And suppose that there are at least n/10 unique elements. You may replace 10 with any other constant. This means that, as you add more elements, you are not just adding more duplicates of the same values.
In order to have n/10 unique elements, you need to be able to construct n/10 different strings, which means that L needs to be at least log_(base = how many distinct symbols you have)(n/10), which is O(log n). So you have L * n = O(n log n) symbols to write down, and even reading the input takes time O(n log n).
As a programmer, it's very very easy to think "64-bit integers can encode numbers up to 2^64, and 2^64 is HUUUUGE, so I'll imagine that my variables can store any integer". But asymptotic complexity is all about what happens when inputs get arbitrarily large, and your favorite computer's registers and memory cells cannot store arbitrarily large values, and you end up with extra factors of log n that you need to deal with.
P.S. For fun, you can try to extend the above analysis to the case where the number of unique elements is sublinear in the number of elements. The argument almost carries straight through if there are at least n^c unique elements for 0 < c < 1 (as the c turns into a constant factor when you take the log), but there's room to quibble: if the number of unique elements is sublinear in n, one might argue that one could write down a complete representation of the input and especially the sorted output in space that is sublinear in L * n. So then the problem would need to be defined a bit more carefully, for example by specifying the the input format is literally just a delimited list of the element values in input order.
Re: Faster Than Dijkstra?
#54The 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 constrained range, as well as potentially having other benefits such being simpler to implement correctly in a short amount of engineering time.
This argument is very much in line with Mike Acton's data-driven design philosophy [1] -- 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.
It's common that new algorithms or data-structures with superior asymptotic efficiency are less performant for smaller problem sizes vs simpler alternatives. As always, it depends on the specifics of any given application.
[1] see Mike's CppCon 2014 talk "Data-Oriented Design and C++" https://www.youtube.com/watch?v=rX0ItVEVjHc
Re: Faster Than Dijkstra?
#55Earlier quoted context omitted.
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
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.
Re: Faster Than Dijkstra?
#56Re: Faster Than Dijkstra?
#57Each 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
Don't know about if Sleep Sort even is a valid sorting algorithm? Is this even real?
Re: Faster Than Dijkstra?
#58Graph 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 true, but we can't reproduce it outside of the test subject(s). So it's a constant siren song to try to figure out how the fuck we do that and write a program that does it faster or more reliably.
Traveling Salesman was the last hard problem I picked up solely to stretch my brain and I probably understand the relationship between TSP and linear programming about as well as a Seahawks fan understands what it is to be a quarterback. I can see the bits and enjoy the results but fuck that looks intimidating.
Re: Faster Than Dijkstra?
#59Graph 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…
>while a computer would take weeks or until the heat death of the universe to do it better.
I don't buy this, approximation algorithms are an entire field of CS, if you're OK with an approximate solution I'm sure computers could do that quickly as well.
Re: Faster Than Dijkstra?
#60Earlier quoted context omitted.
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
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.