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
> 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.
TLDR: You're being unhelpfully pedantic.
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
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.
But sorting by arbitrary strings like names can’t avoid comparison sort.
Gosh. Let me try to convince you.
I use permutation arrays all the time: lists of indexes that can be used across multiple vectors.
This is much faster than the pattern of scanning rows, constructing tuples of (thingToSort . thingIWantInThatOrder) and making a custom sort function, and destructuring those tuples...
And really, not having to write custom sort functions is really really nice.
> Especially in telemetry, where mean is easy and median is not.
Funny. Yes median is obvious with a permutation array, and maybe mean is less so.
When your data is really big and not very variable, mean of x is roughly the same as the mean of any sufficient sample of x, and that sample can be meaningfully represented as a permutation array!
You can get such an array with reservoir sampling and some maths, and (depending on what you know of your data and variance) sometimes even simpler tricks.
That's kindof actually how the "faster than dijkstra" trick referred-to in the article works: Data sets with small variance has this same property that the min of x is roughly the same as the min of a sufficient sample of x (where the size of sufficient has to do with the variance). And so on.
Another big use-case in my code is trees: Apter trees have a flat memory layout which is convenient for permutation arrays which can simultaneously represent index, rotation, tombstones, and all sorts of other things you might need to do with a tree.
Give it a dig. There's good stuff in there.
"sorting" means assigning things into bins (which are usually ordered).
You might substitute "sorted by height" but its certainly not a correction. While "ordered into lines" would be an error.
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"
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.
https://en.wikipedia.org/wiki/Spaghetti_sort
https://every-algorithm.github.io/2023/11/25/spaghetti_sort....
The equivalent for positive link weight shortest paths is the “string algorithm” — build the network out of string and pull taut between the two knots/nodes, the resulting set of taut links is the shortest path.