undefined | Better HN

0 pointsdouglaswlance5y ago0 comments

You can do a binary search to efficiently locate the positive sample.

0 comments

Note that optimal branch factor would probably depend on the expected negative rate. If 98% of your samples are coming back negative, it may be more optimal to divide by into 4 or 8 groups instead of 2 groups.

ced5y ago

But what if there are two (or more?) positive samples? It's an interesting problem.

bequanna5y ago

If the initial test size is 64 and contains a positive, split into two groups of 32 and test each. Continue splitting and testing when a positive is encountered.

ced5y ago

Yeah, but this version is not necessarily optimal. If you have 4 positive samples, then you will test 2+2+1+1+1+1 = 8, instead of 4 in the naive case.

It feels like a problem for information theory.

1 more reply

gnulinux5y ago

You keep binary searching each part. I.e. if both 32/32 subsamples turn positive, you perform binary search on those 32 samples.

j / k navigate · click thread line to collapse

0 comments

timerol5y ago

ced5y ago

But what if there are two (or more?) positive samples? It's an interesting problem.

bequanna5y ago

If the initial test size is 64 and contains a positive, split into two groups of 32 and test each. Continue splitting and testing when a positive is encountered.

ced5y ago

Yeah, but this version is not necessarily optimal. If you have 4 positive samples, then you will test 2+2+1+1+1+1 = 8, instead of 4 in the naive case.

It feels like a problem for information theory.

1 more reply

gnulinux5y ago

You keep binary searching each part. I.e. if both 32/32 subsamples turn positive, you perform binary search on those 32 samples.

j / k navigate · click thread line to collapse