NaturalNode/natural — pull request #40 by moos (2012-05-15 20:56:14+00:00)
Title: fix extra binary search steps when word not found

While doing some benchmarking, I noticed the binary search in index files performs extra iterations when a word is not found. For example, searching for 'acre-' in index.noun, findAt() recursion:

1 2393327 'acre-' 'judgement_day' 2393327
2 1196663 'acre-' 'direct_sum' 1196664
3 598331 'acre-' 'buyout_bid' 598332
4 299165 'acre-' 'attraction' 299166
5 149582 'acre-' 'amorphophallus_campanulatus' 149583
6 74790 'acre-' 'agapanthus' 74792
7 37394 'acre-' 'acorn_barnacle' 37396
8 56092 'acre-' 'administrative_division' 18698
9 46743 'acre-' 'acular' 9349
10 42068 'acre-' 'acrylonitrile-butadiene-styrene' 4675
11 39730 'acre-' 'acridity' 2338
12 38561 'acre-' 'acousticophobia' 1169
13 39146 'acre-' 'acquisition' 585
14 39439 'acre-' 'acrasiomycetes' 293
15 39586 'acre-' 'acreage' 147
16 39512 'acre-' 'acre-foot' 74
17 39475 'acre-' 'acre' 37
18 39494 'acre-' 'acre' 19
19 39504 'acre-' 'acre-foot' 10
20 39499 'acre-' 'acre' 5
21 39502 'acre-' 'acre-foot' 3
22 39500 'acre-' 'acre' 2
23 39501 'acre-' 'acre' 1

It finally stops when adjustment (last param) == 1. Steps after iteration 18 are unnecessary since it landed on the same line as before. This patch fixes that by adding a lastKey parameter to findAt().

I've also exposed IndexFile.prototype._findAt() for some optimization work I'm doing.