News for hackers. Stuff that matters.
Re:Magic: The Gathering Is Turing Complete (2012) by gowld on Thursday November 16, 2017 @02:20PM (#15715636)
Are you sure the constant is enormous? https://arxiv.org/abs/1606.00484
Re:Magic: The Gathering Is Turing Complete (2012) by mabbo on Thursday November 16, 2017 @02:34PM (#15715764)
The paper you've posted: "The Median of Medians (also known as BFPRT) algorithm, although a landmark theoretical achievement, is seldom used in practice because it and its variants are slower than simple approaches based on sampling."

Me: "It's O(n), but the constant in the front is enormous, so it's usually totally impractical"

?

Re:Magic: The Gathering Is Turing Complete (2012) by btilly on Thursday November 16, 2017 @04:04PM (#15716602)
But it is not impractical!

Quickselect is trivial to write and has a much better constant on average, but can be O(n^2).

If you do rounds of quickselect then occasionally a round of median of medians, you get guaranteed O(n) performance that on average is as close as you want to what quickselect does.

Re:Magic: The Gathering Is Turing Complete (2012) by mabbo on Thursday November 16, 2017 @06:03PM (#15717514)
I'm not saying QuickSelect has a large constant. I am saying the median of median O(n) algorithm, which again is not QuickSelect, has a large constant.
Re:Magic: The Gathering Is Turing Complete (2012) by btilly on Thursday November 16, 2017 @07:37PM (#15718057)
And I am saying that when you combine the two you get an algorithm with a small constant in practice and guaranteed O(n) behavior in the worst case.

For example do quickselect on 9/10 rounds but on every 10th round do a median of medians. The overhead of guaranteed performance will only be a few percent off of the average.

Re:Magic: The Gathering Is Turing Complete (2012) by mabbo on Friday November 17, 2017 @07:21AM (#15721389)
That's very cool. However, the anecdote I was sharing for comparison purposes specially referred to the median of median algorithms. This was also many years ago, long before the paper above was written.

I'm not saying that it's impossible to do it and always will be. Re-read what I've said if you like, and you'll see I am simply sharing an anecdote for the purposes of an analogy about this particular situation.

Re:Magic: The Gathering Is Turing Complete (2012) by lmartel on Thursday November 16, 2017 @09:19PM (#15718447)
This didn't make intuitive sense to me so tried to Google it. Is "Introselect" what you're referring to? https://en.wikipedia.org/wiki/Introselect

It's a hybrid of quickselect and median of medians, but the switching strategy's a bit more complicated.

Re:Magic: The Gathering Is Turing Complete (2012) by btilly on Thursday November 16, 2017 @10:22PM (#15718646)
Introselect is a more complex version of the same idea.

But basically both quickselect and median of medians are divide and conquer. Median of medians is an expensive way to guarantee a good division. Quickselect hopes for one.

If quickselect goes well, then median of medians will be relatively cheap when run because it is run on a much shorter list. If quickselect does not go well, the median of medians passes guarantee progress. So average behavior is only slightly worse, and worst case behavior is still nicely bounded (albeit with a much worse constant).

Re:Magic: The Gathering Is Turing Complete (2012) by megaman22 on Thursday November 16, 2017 @02:47PM (#15715900)
I remember my algorithms class wasting like a week and a half going over that. I'm still a little bitter. There's only a few courses that I would have wanted a refund on my tuition for, and that's one of them.
Re:Magic: The Gathering Is Turing Complete (2012) by lmkg on Thursday November 16, 2017 @02:56PM (#15715998)
I'm not a domain expert, but I would assume that "approaches based on sampling" could be O(1). If so, the slowness would be based on the scaling, not on the constant.
Re:Magic: The Gathering Is Turing Complete (2012) by pdpi on Thursday November 16, 2017 @06:42PM (#15717732)
If you keep the number of samples constant (so that you can have O(1) time) then the quality of the estimate goes down with the number of items in the collection. To keep the quality constant, you need number of samples to scale with the size of the collection.
Re:Magic: The Gathering Is Turing Complete (2012) by Retric on Thursday November 16, 2017 @10:09PM (#15718608)
Depends on how you are measuring accuracy.

Suppose I have a set of all integers less than k and > 0, and you after N random selections want to estimate k. Presumably as k increases your accuracy drops in absolute terms. But, if you do the same thing using the reals so there is infinite number of numbers from zero to k you can still make a bounds for k.

Granted there are now infinite number of reals in your estate, but you can still pick an N such that an arbitrary % of the time k is +/- an arbitrary % of your guesses.

Re:Magic: The Gathering Is Turing Complete (2012) by contravariant on Thursday November 16, 2017 @07:03PM (#15717855)
Not necessarily, using k samples you can estimate the mean of i.i.d. samples with a variance of 1/k the sample variance. Note that this is independent of the sample distribution, in particular it's also true if you're drawing from some fixed collection, regardless of its size.

I find it harder to say something about the median, but I imagine some similar theorems hold.

Unless you have some definition of quality for which you can show that you do need more samples with a bigger collection?