ruby-dev

At Thu, 16 Aug 2001 00:15:05 +0900,
Satoru Takabayashi wrote:
> 作者です。
> 
> APIは、こんな感じでいいでしょうか。
> <http://namazu.org/~satoru/ruby-bsearch/>
> まずいようであれば修正します。

　rough/ 以下のモジュールは標準採用への登竜門ということで、よい
API ときれいな実装のためには互換性など気にせずにバンバンいじって
しまいましょう。


　今一つだけ気付いたのは、 1...5 形式の Range に対応していないと
いう些細な不具合です。あと、 API についていうと、こんな風にする
のはどうかなーと思いました。

	bsearch(v) で従来の bsearch {|x| x <=> v} と等価になる。
	ただし、要素が降順に並んでいる場合は従来の
	bsearch {|x| v <=> x} と等価。

	bsearch(v) {|x| f(x) } で従来の bsearch {|x| f(x) <=> v }
	と等価になる。ただし、要素が降順の場合は従来の
	bsearch {|x| v <=> f(x) } と等価。

	降順かどうかは最初と最後の要素を比較して判断する。
	ブロックを与えた場合はブロックの評価値を比較して判断する。

まあ、言葉で書くだけではあれなので実装してみました。

  def bsearch_first(value, range = 0...length())
    low = range.first() - 1

    if range.exclude_end?
      high = range.last()
    else 
      high = range.last() + 1
    end

    if block_given?
      desc = yield(first()) > yield(last())
    else
      desc = first() > last()
    end

    while low + 1 != high
      mid = (low + high) / 2

      if block_given?
        cmp = yield(self[mid]) <=> value
      else
        cmp = self[mid] <=> value
      end

      if !desc && cmp < 0 || desc && cmp > 0
        low = mid
      else 
        high = mid
      end
    end

    if high >= self.length
      return nil
    end

    if block_given?
      cmp = yield(self[high]) != value
    else
      cmp = self[high] != value
    end

    if cmp
      return nil
    else 
      return high
    end
  end


　単純な走査の場合はブロックの呼び出しがなくなるものの、条件判断が
いろいろ増えてしまっている気も。。

　まあ、使い方が若干直感的になるという方が主眼です。

> CVSアカウントをもらえれば継続的に保守できます。

　pserver 経由のアクセスになるので、希望のアカウント名と crypt
されたパスワードとを私宛に送ってください。すぐに発行します。


(入力した文字列を crypt する one-liner)

ruby -e "a=(0..127).map{|i|'%c'%i}.grep /[\da-z]/i;puts gets.chomp.crypt(a[rand a.size]+a[rand a.size])"

-- 
                     /
                    /__  __            Akinori.org / MUSHA.org
                   / )  )  ) )  /     FreeBSD.org / Ruby-lang.org
Akinori MUSHA aka / (_ /  ( (__(  @ iDaemons.org / and.or.jp

"Freeze this moment a little bit longer, make each impression
  a little bit stronger..  Experience slips away -- Time stand still"

Thread

Prev Next

In This Thread

Prev Next

[#14185] ruby on Linux/m68k — akira yamada / やまだあきら <akira@...>

[#14195] exception at IO.popen failure — nobu.nakada@...

[#14196] fork() on MacOS — nobu.nakada@...

[#14206] undef_method :method_missing — Kenichi Komiya <kom@...1.accsnet.ne.jp>

[#14229] [BUG] segv on [str].pack("p") — Koji Arai <JCA02266@...>

[#14300] 名前空間を調べる効果的な方法はありますか？ — 西 啓一朗 <receiver@...>

[#14327] Re: [ruby-cvs] ruby/ext/socket: * string.c (rb_str_lstrip_bang): new method. — "U.Nakamura" <usa@...>

[#14338] setup.rb (Re: Common GUI framework) — Minero Aoki <aamine@...>

[#14382] [BUG] segv on regex matching with long string — TAKAHASHI Masayoshi <maki@...>

[#14390] [Patch] pp.rb and debug.rb — "NAKAMURA, Hiroshi" <nakahiro@...>

[#14406] typo in ruby 1.7 — Koji Arai <JCA02266@...>

[#14413] 1.7.1 2001-08-06: if true && /match/ — WATANABE Tetsuya <tetsu@...>

[#14430] Re: [ruby-cvs] ruby: * object.c (rb_obj_inspect): merge from 1.7: remove useless space. — Kazuhiro NISHIYAMA <zn@...>

[#14436] 1.7.1 2001-08-06: [BUG] unknown node type 0 — akira yamada / やまだあきら <akira@...>

[#14441] "foo".lstrip! should return `nil'. — Koji Arai <JCA02266@...>

[#14445] string.c rb_str_cmp() — TOYOFUKU Chikanobu <toyofuku@...>

[#14464] Ruby/Bsearch — akira yamada / やまだあきら <akira@...>

[#14465] Ruby/Bsearch — akira yamada / やまだあきら <akira@...>

[#14480] avoid compile warning of tcltklib with VC5 — "U.Nakamura" <usa@...>

[#14505] BUG: ruby 1.6.4 cannot use threads on Sparc (segv) — akira yamada / やまだあきら <akira@...>

[#14516] ext/digest/sha2/extconf.rb and try_run — WATANABE Hirofumi <eban@...>

[#14530] restore terminal mode even if readline interrupted. — Koji Arai <JCA02266@...>

[#14547] setuid/setgid — nobu.nakada@...

[#14552] read in IO#eof? — nobu.nakada@...

[#14560] — nobu.nakada@...

[#14565] (mswin32) dln_strerror() returns empty message — Tietew <tietew@...>

[#14572] noisy warnings of resolv.rb — Koji Arai <JCA02266@...>

[#14573] [PATCH] ruby-mode.el — Kenichi Komiya <kom@...1.accsnet.ne.jp>

[#14575] infinite loop on Dir.glob("*/**/*") — nobu.nakada@...

[#14576] glob_helper: merge from 1.7 — nobu.nakada@...

[#14577] option nodynamic — Daisuke Aoki <dai@...>

[#14584] Array#merge, Array#squeeze — "Akinori MUSHA" <knu@...>

[#14590] rb_load — OJ <oj@...7.com>

[#14595] SEGV at `$0 = "long long string"' — nobu.nakada@...

[#14601] $stdout への代入 ( 再考) — Koji Arai <JCA02266@...>

[#14603] patch for GNU/Hurd — akira yamada / やまだあきら <akira@...>

[ruby-dev:14478] Re: Ruby/Bsearch

Thread

In This Thread

[#14300] 名前空間を調べる効果的な方法はありますか？ — 西啓一朗 <receiver@...>

[#14445] string.c rb_str_cmp() — TOYOFUKU　Chikanobu <toyofuku@...>