[ruby-list:49319] Re: Array#bsearchで求められる前提について
From:
Kouhei Yanagita <yanagi@...>
Date:
2013-04-15 03:51:10 UTC
List:
ruby-list #49319
こんにちは。柳田です。
「monotone (or sorted)」と言ってもどのようにソートするかの違いがあるだろうと思っていたのですが、
改めて読んでみると、その後ろに書いてあるブロックの返す値の仕様も合わせて考えれば、
どのように並べられているべきかは明らかですね。
どうもありがとうございました。
2013年4月10日 20:20 Yusuke Endoh <mame@tsg.ne.jp>:
> 遠藤といいます。
>
> 2013年4月10日 17:23 Kouhei Yanagita <yanagi@shakenbu.org>:
>> 2.0.0p0で
>>
>> (1..10).to_a.bsearch { |e| e < 3 }
>>
>> がnilになるのですが、これは「配列がソートされていない」ということでいいのでしょうか。
>
> はい、そうなります。rdoc では "monotone (or sorted)" と表現しています。
>
>
>> 言い換えると、Array#bsearchで前提とされているソートとは、
>> 「ブロックを満たす任意の要素は、ブロックを満たさない任意の要素より後ろにある」という意味であって、
>> 「ブロックを満たす任意の要素は、ブロックを満たさない任意の要素より前にある」状態は含まない
>> ということでいいのでしょうか。
>
> その通りです。
>
> 厳密に言うと、あるインデックス i (0 <= i <= ary.size) に対して、
>
> - i より小さいインデックスの要素に対してブロックは false を返し、かつ
> - i と等しいか大きいインデックスの要素に対してブロックは true を返す
>
> という条件を満たさないとダメです (この時 ary[i] を返す) 。
>
> 詳しくは rdoc を見てください。
>
> http://ruby-doc.org/core-2.0/Array.html#method-i-bsearch
>
>
> 2013年4月10日 17:23 Kouhei Yanagita <yanagi@shakenbu.org>:
>> こんにちは。柳田と申します。
>>
>> 2.0.0p0で
>>
>> (1..10).to_a.bsearch { |e| e < 3 }
>>
>> がnilになるのですが、これは「配列がソートされていない」ということでいいのでしょうか。
>>
>> 言い換えると、Array#bsearchで前提とされているソートとは、
>> 「ブロックを満たす任意の要素は、ブロックを満たさない任意の要素より後ろにある」という意味であって、
>> 「ブロックを満たす任意の要素は、ブロックを満たさない任意の要素より前にある」状態は含まない
>> ということでいいのでしょうか。
>>
>> ソースコードを読むとその前提で実装されているように見えるのですが、
>> 仕様として意図されたものなのかどうかわからなかったので質問します。
>>
>>
>> --
>> 柳田 浩平 / やなぎた こうへい
>> Kouhei Yanagita <yanagi at shakenbu.org>
>>
>
>
>
> --
> Yusuke Endoh <mame@tsg.ne.jp>
>
--
柳田 浩平 / やなぎた こうへい
Kouhei Yanagita <yanagi at shakenbu.org>