Add a binary search function to Calc to do faster search than "in"

[rlwhitcomb]

Noticed about a 10% improvement in "p45.calc" with this change ("index" -> "search").

[rlwhitcomb]

In a significant speed test: array with 1,000,000 values, and 10,000 random inquiries, here are the timings: Elapsed time of "index test" was 346.723513 secs. Elapsed time of "search test" was 680.501862 secs.

SO .... binary search was NOT faster, in fact 2x slower.... Reopening this issue.

[rlwhitcomb]

I'm pretty sure the slowdown is two-fold:

• doing "buildValueList" with UNCHANGED in the "search" case which is NOT done with "index"
• also doing "toArray" in the "search" case, which is yet another copy operation, also not done with "index"

The first problem is easily changed by simply omitting it, and doing the search directly, as "index" does. The second is not so easy, since the built-in binary search method requires an array. But we could possibly build our own based on ArrayList, which should have similar performance (?) as the system one.

[rlwhitcomb]

Okay, this is better. without doing the "buildValueList" or the "toArray" conversion, and using our home-grown binary search of a "List" here are the results for 100,000 values:

Elapsed time of "search test" was 0.219597 secs.
Elapsed time of "index test" was 16.744470 secs.

So, delivering the desired speed-up over "index".

On a busy system, plugged in for maximum performance, got this result for 1,000,000 values:

Elapsed time of "search test" was 1.457051 secs.
Elapsed time of "index test" was 2896.911337 secs.

So, yeah, guessing that "search" really does go faster now.

[rlwhitcomb]

Another new result, for 100,000 objects:

Elapsed time of "search test" was 0.202419 secs.
Elapsed time of "index test" was 17.168861 secs.

Or > 75x faster with "search".