Home > Erlang Archive

Erlang Archive

[Python]2分探索

ビューティフルコードの7章で、この章を読み進む前に2分探索を実装しろと書いてあった。
ということでPythonで実装してみる。

最初に書いたコードはこれ。

PLAIN TEXT
PYTHON:
  1. def mybinarysearch(a, t, f):
  2.     n = len(a)
  3.     if n <= 0:
  4.         return -1
  5.     if n == 1:
  6.         if a[0] == t:
  7.             return 0
  8.         else:
  9.             return -1
  10.     m = int(n / 2)
  11.     r = f(t, a[m - 1])
  12.     if r <= 0:
  13.         x = mybinarysearch(a[:m], t, f)
  14.         if x>= 0:
  15.             return x
  16.         else:
  17.             return -1
  18.     else:
  19.         x = mybinarysearch(a[m:], t, f)
  20.         if x>= 0:
  21.             return m + x
  22.         else:
  23.             return -1

配列、検索対象、比較関数を渡す。
さすがにこれだと、いちいちlenを計算していたり効率悪すぎだし、コードも汚いのでもう少しましにする。

PLAIN TEXT
PYTHON:
  1. def mybinarysearch(a, t, f):
  2.     def func(array, i, n):
  3.         if n <= 0:
  4.             return -1
  5.         elif n == 1:
  6.             if f(array[0], t) == 0:
  7.                 return i
  8.             else:
  9.                 return -1
  10.         else:
  11.             m = int(n / 2)
  12.             if f(t, array[m - 1]) <= 0:
  13.                 return func(array[:m], i, m)
  14.             else:
  15.                 return func(array[m:], i + m, n - m)
  16.     return func(a, 0, len(a))

これで、配列中で対象に合致する最小のIndexが返るはず？

最小にこだわらなければこうなるかな

PLAIN TEXT
PYTHON:
  1. def mybinarysearch(a, t, f):
  2.     def func(array, i, n):
  3.         if n <= 0:
  4.             return -1
  5.         m = int(n / 2)
  6.         r = f(t, array[m])
  7.         if r == 0:
  8.             return i + m
  9.         elif r <0:
  10.             return func(array[:m], i, m)
  11.         else:
  12.             return func(array[m + 1:], i + m + 1, n - m - 1)
  13.     return func(a, 0, len(a))

この章の主題であるテストはまだちゃんとやってない。

これから考えてやってみよう。
再帰で書いてしまったので遅そうだけど、2分探索だったらあふれることはないだろう。

Erlang yumでOKだよ

何も考えずにソースをmakeしてインストールしちゃったけど、普通にパッケージになってるじゃん。
yum install erlang
ほんの少しバージョンは古いかもしれないけど、これでOKですね。すいません。
あとあと面倒くさいことにならないようにyumで入れ直しとこ。

自分用のメモだけど一応make installで入ったファイルはこれ。
cd /usr/local/lib/erlang && ./Install -minimal /usr/local/lib/erlang
　
for file in erl erlc epmd run_erl to_erl dialyzer typer escript; do \
rm -f /usr/local/bin/$file; \
ln -s /usr/local/lib/erlang/bin/$file /usr/local/bin/$file; \
done

Erlangをインストールした

家のLinuxが入っているマシン（Fedora Core6）にErlangをインストールした。
解説するまでも無いけど手順は以下のとおり。
wget http://www.erlang.org/download/otp_src_R11B-4.tar.gz
tar xvzf otp_src_R11B-4.tar.gz
cd otp_src_R11B-4
./configure
make
make install
で一応動いた。

# erl
Erlang (BEAM) emulator version 5.5.4 [source] [async-threads:0] [hipe] [kernel-poll:false]
　
Eshell V5.5.4 (abort with ^G)
1> 1 + 2.
3
2> io:put_chars("Hello World\n").
Hello World
ok
3>

ソースをダウンロードして10MB以上あったので覚悟してたけど、makeに思った以上時間がかかった。
Creating initial PLT (will take several minutes; please be patient)
とか言われたあとかなり待たされたのは、英語が読めなくて忍耐が無いだったら固まったと思って処理をとめちゃったかもしれない。（←たぶんこんな人はいないと思うけど）

これから少しずつ触っていってみるつもり。

Home > Erlang Archive

Recent Entries
Categories
Archives
Tag Cloud
Search
Feeds
Meta

Return to page top