4 ms·
This is the exact point of view they are rejecting. You want spectacular average-case performance at the cost of a slow but not catastrophic worst-case.
by Donald 9y ago
This is the exact point of view they are rejecting. You want spectacular average-case performance at the cost of a slow but not catastrophic worst-case.
- anonacct37 9y agoSo basically suitable for batch mode only? There's really no other situation in software where average is a useful measure.
- willchang 9y agoHow about searching the web? I'd rather most queries take 1 second, and 10% taking 10 seconds, than every query taking 5 seconds. I don't understand how you can be so confident about attaching a utility function to latency.
- KirinDave 9y agoThis is not only wrong for most user-facing cases, but it misses the key notion of training 1-N sub-models, which is a gateway to actually measuring the degree of success or failure in the index building step and modifying it as needed.
- PeterisP 9y agoWell, no, for many user-facing use cases your performance essentially averages out if you have enough users - i.e. for a single user even the worst case performance is faster than they care about, but you're limited by how many concurrent users your hardware can serve. In that case, you want the average to be as low as possible because then you need less hardware for the same throughput, or you can get faster response time for any users once the waiting/delay caused by other users is taken into account. A blocking read operation that predictably takes 10 ms will limit you to 100 requests per second, and with an uneven/bursty distribution many of those requests will be queued for 100ms; A blocking read operation that sometimes takes 50 ms but has 5 ms on average will have almost no queuing in 100 requests per second, so the 50ms will really be the worst case.
- DonbunEf7 9y agoAnd they will be forced to learn, the hard way, that this is a bad way to approach algorithms design. The same argument applies to quicksort, and we know how that turned out: http://www.cs.dartmouth.edu/~doug/mdmspe.pdf http://www.cs.dartmouth.edu/~doug/mdmspe.pdf
- czardoz 9y agoThat argument cannot be generalized to every use-case. In fact it's very specific to quick sort. Yes, this approach may not work for a lot of situations, but there are some (as pointed out elsewhere in the comments), where it's perfectly reasonable, even desirable to improve the average runtime at the cost of the worst case.
- goialoq 9y agoThat adversarial quicksort only applies under specific constraints (2. Pivot-choosing takes O(1) comparisons; all other comparisons are for partitioning. ) that are easily worked around.
- bunderbunder 9y agoDepends on application. They're looking at analytical workloads, which presumably means they're focused on batch jobs. For OLTP-type workloads, I care very much about worst-case performance.