code review 3025042: sort: simplify semantics of Search.

sort: simplify semantics of Search.
As discussed earlier.

[rog, 2010-11-11 19:06:36]

Hello gri (cc: golang-dev@googlegroups.com),

I'd like you to review this change.

[gri, 2010-11-11 23:05:07]

Can you please upload the latest version sync'ed against the repository? It
appears that it does the same number of calls of f which is great.
- gri

On Thu, Nov 11, 2010 at 11:06 AM, <rogpeppe@gmail.com> wrote:

> Reviewers: gri,
>
> Message:
> Hello gri (cc: golang-dev@googlegroups.com),
>
> I'd like you to review this change.
>
>
> Description:
> sort: simplify semantics of Search.
> As discussed earlier.
>
> Please review this at http://codereview.appspot.com/3025042/
>
> Affected files:
>  M src/pkg/sort/search.go
>  M src/pkg/sort/search_test.go
>
>
>

[rog, 2010-11-11 23:21:21]

PTAL (i *hope* i got the merging right)

On 11 November 2010 23:04, Robert Griesemer <gri@golang.org> wrote:
> Can you please upload the latest version sync'ed against the repository? It
> appears that it does the same number of calls of f which is great.
> - gri
>
> On Thu, Nov 11, 2010 at 11:06 AM, <rogpeppe@gmail.com> wrote:
>>
>> Reviewers: gri,
>>
>> Message:
>> Hello gri (cc: golang-dev@googlegroups.com),
>>
>> I'd like you to review this change.
>>
>>
>> Description:
>> sort: simplify semantics of Search.
>> As discussed earlier.
>>
>> Please review this at http://codereview.appspot.com/3025042/
>>
>> Affected files:
>>  M src/pkg/sort/search.go
>>  M src/pkg/sort/search_test.go
>>
>>
>
>

[gri, 2010-11-11 23:44:05]

http://codereview.appspot.com/3025042/diff/17001/src/pkg/sort/search.go
File src/pkg/sort/search.go (right):

http://codereview.appspot.com/3025042/diff/17001/src/pkg/sort/search.go#newco...
src/pkg/sort/search.go:31: // caller to verify the actual presence by testing if
data[i] == x.
we should probably be complete here and say:

... by testing if i < n && data[i] == x.

http://codereview.appspot.com/3025042/diff/17001/src/pkg/sort/search.go#newco...
src/pkg/sort/search.go:32: // Thus 0 <= i <= n and i is the first index of x if
x is present in the data.
I think this sentence needs to go where it was before; the 'Thus' refers to that
description and not the fact that one needs to test outside for the presence of
x.

http://codereview.appspot.com/3025042/diff/17001/src/pkg/sort/search.go#newco...
src/pkg/sort/search.go:48: // i <= h <= j
What was here before was correct: When you enter the loop body, i+1 < j, i.e.,
the difference j-i >= 2, and thus (j-i)/2 >= 1. So i < h < j.

[rog, 2010-11-12 06:05:25]

http://codereview.appspot.com/3025042/diff/17001/src/pkg/sort/search.go
File src/pkg/sort/search.go (right):

http://codereview.appspot.com/3025042/diff/17001/src/pkg/sort/search.go#newco...
src/pkg/sort/search.go:31: // caller to verify the actual presence by testing if
data[i] == x.
On 2010/11/11 23:44:05, gri wrote:
> we should probably be complete here and say:
> 
> ... by testing if i < n && data[i] == x.

Done.

http://codereview.appspot.com/3025042/diff/17001/src/pkg/sort/search.go#newco...
src/pkg/sort/search.go:32: // Thus 0 <= i <= n and i is the first index of x if
x is present in the data.
On 2010/11/11 23:44:05, gri wrote:
> I think this sentence needs to go where it was before; the 'Thus' refers to
that
> description and not the fact that one needs to test outside for the presence
of
> x.

Done.

http://codereview.appspot.com/3025042/diff/17001/src/pkg/sort/search.go#newco...
src/pkg/sort/search.go:48: // i <= h <= j
On 2010/11/11 23:44:05, gri wrote:
> What was here before was correct: When you enter the loop body, i+1 < j, i.e.,
> the difference j-i >= 2, and thus (j-i)/2 >= 1. So i < h < j.

i could have sworn i changed this!
done.

[rog, 2010-11-12 06:44:52]

On 11 November 2010 23:04, Robert Griesemer <gri@golang.org> wrote:
>It appears that it does the same number of calls of f which is great.

that's interesting - i guess the +1 means that the final case,
when i+1==j, comes one iteration sooner.

the new one *is* marginally less efficient than the old...
.075% more calls per search averaged over all the cases
in TestSearchEfficiency. could be worse :-)

[gri, 2010-11-12 23:56:14]

On Thu, Nov 11, 2010 at 10:44 PM, roger peppe <rogpeppe@gmail.com> wrote:

> On 11 November 2010 23:04, Robert Griesemer <gri@golang.org> wrote:
> >It appears that it does the same number of calls of f which is great.
>
> that's interesting - i guess the +1 means that the final case,
> when i+1==j, comes one iteration sooner.
>

> the new one *is* marginally less efficient than the old...
> .075% more calls per search averaged over all the cases
> in TestSearchEfficiency. could be worse :-)
>

Yes, I noticed that in the old implementation, occasionally there is 1 less
than log2(n) iterations. Now it appears to be always log2(n).
- gri

[gri, 2010-11-12 23:56:34]

LGTM
thanks!
- gri

[gri, 2010-11-12 23:57:38]

*** Submitted as http://code.google.com/p/go/source/detail?r=c4f0f4abb627 ***

sort: simplify semantics of Search.
As discussed earlier.

R=gri
CC=golang-dev
http://codereview.appspot.com/3025042

Committer: Robert Griesemer <gri@golang.org>

[rog, 2010-12-02 19:23:50]

*** Abandoned ***