カタラン数を計算してみる、その２

Ruby Snippet

前回はfactorialとcombinationでカタラン数を導出しようと、fact 20くらいであっけなくオーバーフローしたけど、チーター本のP.216ではカタラン数をDPで計算してる。けど、問題の解説見てて{C_0=1}があったほうが分かり易いなと何となく思った*1。


{C_0=1}を定義した場合



{C_0 = 1}
{C_1= C_0*C_0 =1}
{C_2= C_1*C_0+C_0*C_1 =2}
{C_3= C_2*C_0+C_1*C_1+C_0*C_2 =5}
{C_4= C_3*C_0+C_2*C_1 + C_1*C_2+C_0*C_3 = 14}
{C_5 = ... = 42}
{C_n = C_{n-1}*C_0 + C_{n-2}*C_1 + ... + C_1*C_{n-2} + C_0*C_{n-1} }

しなかった場合(書籍の解説より引用)



C0=1
{C_1=1}
{C_2= C_1+C_1 =2}
{C_3= C_2+C_1*C_1+C_2 =5}
{C_4= C_3+C_2*C_1 + C_1*C_2+C_3 = 14}
{C_5 = ... = 42}
{C_n = C_{n-1} + C_{n-2}*C_1 + ... + C_1*C_{n-2} + C_{n-1} }

で、{C_n}の一般項は、本の通りになると腑に落ちた。それだけ*2ｗ−



ってわけのいかないので、それでコード書いてみた。けど、本のサンプルのDPは*3よく分からないので
Ruby*4の再帰で書き下すｗ−。

$memo = Array.new(10, 0)
$memo[0] = 1

def catalan n
  return $memo[n] unless $memo[n].zero?

  $memo[n] = (1..n).to_a.reduce(0){|s,i|
    #p [s,i]
    p [$memo]

    s + catalan(n-i) * catalan(i-1)
  }
  $memo[n]
end

それっぽい答え出てるけど、早いのかどうかわからないｗ−

P.S.
前回のfactorial使ったのと、今回のrubyコードの時間計測しても大して変わらないな

$ time ruby catalan.rb
[1, 1]
[2, 2]
[3, 5]
[4, 14]
[5, 42]
[6, 132]
[7, 429]
[8, 1430]
[9, 4862]
[10, 16796]
[11, 58786]
[12, 208012]
[13, 742900]
[14, 2674440]
[15, 9694845]

real    0m0.334s
user    0m0.310s
sys     0m0.020s

$ time ruby catalan_memo.rb
[1, 1]
[2, 2]
[3, 5]
[4, 14]
[5, 42]
[6, 132]
[7, 429]
[8, 1430]
[9, 4862]
[10, 16796]
[11, 58786]
[12, 208012]
[13, 742900]
[14, 2674440]
[15, 9694845]

real    0m0.321s
user    0m0.300s
sys     0m0.010s

最強最速アルゴリズマー養成講座　プログラミングコンテストTopCoder攻略ガイド
最強最速アルゴリズマー養成講座　プログラミングコンテストTopCoder攻略ガイド
posted with amazlet at 17.03.21
SBクリエイティブ (2013-08-14)
売り上げランキング: 49,919
Amazon.co.jpで詳細を見る

*1:って思ったけど、wikipediaがそのような導出なのでそれ見ただけかもｗ−

*2:全部書くの面倒くさいので、詳細は本を参照してください＾＾

*3:ってよりループにかな。本質的に再帰と等価だからforで記述できそうなのは分かるけどｗ−

*4:慣れているのでｗｗｗ

カタラン数を計算してみる

Ruby F# Snippet

　F#で書いてみたカタラン数は何処かバグっているようで、試しにRubyで書いたらまあ普通に期待値帰ってきたｗ−

世界に整数数値型*1のみならF#でも動くはず*2なのだが？

カタラン数とは

気に入ったのは、凸角形の三角形分割の組み合わせ数と一致するとの事。

Rubyでカタラン数

$ ruby catalan.rb
1
2
6
1
3
3
[1, 1]
[2, 2]
[3, 5]
[4, 14]
[5, 42]
[6, 132]
[7, 429]
[8, 1430]
[9, 4862]
[10, 16796]
[11, 58786]
[12, 208012]
[13, 742900]
[14, 2674440]
[15, 9694845]

def fact n
<<EOS
  if n == 0
    1
  else
    n * fact(n-1)
  end
EOS
  (1..n).inject(:*) || 1
end

def comb(n, r)
  fact(n) / (fact(r) * fact(n-r))
end

def catalan n
  case n
  when 0 then 1
  else
    comb(2*n, n) - comb(2*n, n-1)
  end
end

puts fact 0
puts fact 2
puts fact 3

puts comb 3, 0
puts comb 3, 1
puts comb 3, 2

(1..15).each{|i|
  p [i,catalan(i)]
}

F#の場合

  • rev1: int32で駄目
  • rev2: int64にしたけどfactorial 21でオーバーフローしているのでbitintにしないとイケないか
    • todo
  • rev3: bigint版
    • todo

*1:int64ではどこかで精度が足りてないのだろうか？

*2:なんかまたポカミスしてる気がするのだｗ−

visual studio 2015でのエディタ分割、メモ

Windows Memo

忘れては調べてるのでメモ

水平分割

  1. ウィンドウ -> 分割

垂直分割

  1. ウィンドウ -> 新規ウィンドウ
  2. 「タブ部分を右クリック」 -> 垂直タブ グループの新規作成
ファイル画面移動
  • Ctrl-Tabで、タブファイルを循環移動
参考

Visual Studioで2つのコードファイルを並べて表示する方法 - Yamakiの日記

rubyでdfsでメモ化再帰

Ruby AtCoder

　いや、早くなるのは分かってたけどめちゃくちゃ早かった*1のでｗ−

P.S.
チーター本の７章「動的計画法、メモ化」のサンプルのrubyでのベンチ結果です。

dfs

$ ruby -v
ruby 2.1.5p273 (2014-11-13) [arm-linux-gnueabihf]

$ time ruby hello_dfs.rb
119759850

real    13m50.176s
user    13m50.080s
sys     0m0.050s
hello_dfs.rb
$h = 13
$w = 17

def dfs(nowh, noww)
  return 0 if nowh >  $h || noww > $w
  return 1 if nowh == $h && noww == $w

  dfs(nowh+1, noww) + dfs(nowh, noww+1)
end

puts dfs(0, 0)

dfs with memo

$ time ruby hello_dfs2memo.rb
119759850

real    0m0.325s
user    0m0.320s
sys     0m0.010s
hello_dfs2memo.rb
$h = 13
$w = 17

$memo = Array.new($h+1){Array.new($w+1, 0)}

def dfs(nowh, noww)
  return 0 if nowh >  $h || noww > $w
  return 1 if nowh == $h && noww == $w
  return $memo[nowh][noww] unless $memo[nowh][noww].zero?

  $memo[nowh][noww] = dfs(nowh+1, noww) + dfs(nowh, noww+1)
  $memo[nowh][noww]
end

puts dfs(0, 0)

with c++

　参考に、c++での再帰とメモ化再帰の実行時間。さすがに早いですね。

$ gcc --version
gcc (Raspbian 4.9.2-10) 4.9.2
...

$ time ./dfscpp
119759850

real    0m9.905s
user    0m9.870s
sys     0m0.020s

$ time ./dfscpp2memo
119759850

real    0m0.010s
user    0m0.000s
sys     0m0.000s

P.S. 2017/3/10

ちなみに、計測はrasbian on rpi2で*2図ってますｗ−

with mruby

　なんか、知らないけど興味持たれたようなので、mrubyの場合も*3
わーい、YARVよりメモ化再帰が、はやーい。すごーい。

$ ~/git/mruby/bin/mruby -v
mruby 1.2.0 (2015-11-17)

$ time ~/git/mruby/bin/mruby hello_dfs.rb
119759850

real    48m11.377s
user    48m11.260s
sys     0m0.010s

$time ~/git/mruby/bin/mruby hello_dfs2memo.rb
119759850

real    0m0.064s
user    0m0.050s
sys     0m0.010s

*1:アルゴリズムって大切ですね＾＾

*2:まあお仕事がARM Linuxなのでそれでの速度感覚の練習がてらです＾＾；

*3:今日のHeadの取れたてぴちぴちです＞＜

sshからOP-TEEのQEMU環境実行方法

OPTEE

　デフォルトだと、GUIのxtermが立ち上がる設定なので、sshのCUIでは失敗します。
ので、すこしMakefileいじってやっることによってCUIから起動させました。

Makefileの修正

xtermが勝手に立ち上がるのを無効にします。

diff --git a/qemu_v8.mk b/qemu_v8.mk
index 0dded16..7351c7e 100644
--- a/qemu_v8.mk
+++ b/qemu_v8.mk
@@ -221,8 +221,6 @@ run: all
 .PHONY: run-only
 run-only:
        $(call run-help)
-       $(call launch-terminal,54320,"Normal World")
-       $(call launch-terminal,54321,"Secure World")
        $(call wait-for-ports,54320,54321)
        cd $(ARM_TF_PATH)/build/qemu/release && \
        $(QEMU_PATH)/aarch64-softmmu/qemu-system-aarch64 \

soc_termの手動起動

で、上記で勝手に起動されていたSecure/NonSecureの、soc_termを手動で起動します。
コンソールを別に２個用意して、下記でQEMUからの接続待ちさせてください

Secure
$ ~/devel/optee/soc_term$ ./soc_term 54321
NonSecure
$ ~/devel/optee/soc_term$ ./soc_term 54320

qemuの起動

　で、あとはmake run-onlyでQEMU立ち上げれば、はい成功。おわり＾＾

簡単なlinuxカーネル開発環境の構築メモ

Linux GDB 
$ cat /etc/debian_version 
8.7
$ uname -a
Linux debian 3.16.0-4-amd64 #1 SMP Debian 3.16.39-1 (2016-12-30) x86_64 GNU/Linux

opteeのrepo syncビルド環境を流用

  • opteeのビルド手順の通りに環境作って、optee/linuxを置き換えればOK。
    • pros
      • qemuのみで仮想化構築はシンプル
      • ARMv7, ARMv8*1の実行環境が簡単に手に入る
      • gdbで簡単デバック
      • 序にopteeも試せる
    • cons
      • userlandがbusyboxで貧弱。strace*2とかない＞＜
        • このあたりをいじるとLFSになりそう*3
      • シングルコアのみ。optee側ばqemuの2cpu初期化に対応していないので2cpu以上で現状動かせない

elkdatを利用

  • elkdatのインストール手順は通りに環境作ればOK。とイカなかったので下記に差分のメモ書き
    • proc
      • userlandがubuntu16.04(手順流用すれば、debianとかも簡単にできそう
      • カーネルテストが搭載済み（スバラ＞＜。。。
      • 試せてないけどgdbでカーネルデバッグできるでしょ
      • 多分マルチコア出来る
    • cons
      • 簡単構築とはいえ、vagrant/qemu/kvm/libvirtと仮想化にいろいろ入れる
        • そのぶん早そうだけど
      • x64の環境。お仕事柄で、ARMv7,v8のクロス環境が欲しかったりする
      • 4cpu8smpで、./test bootが4分くらいかかる(16cpuでぶん回すのがデフォルトなってる＾＾；
        • なんか差分なくてもclean && makeしてる気がする。ccacheなどで早くできないだろうか

構築メモ

/etc/libvirt/libvirtd.confの編集

以下コメントアウト*5を解除。

#unix_sock_group = "libvirtd"
#unix_sock_ro_perms = "0777"
#auth_unix_ro = "none"
#auth_unix_rw = "none"

以下コマンドで/etc/groupに自身のユーザを追加

# groupadd -g 900 libvirtd

$ id
uid=1000(murase) ### この自分のユーザ名を以下で追加

# usermod -G libvirtd -a murase
# systemctl restart libvirtd

vagrant-libvirtをインストール

最新の0.0.37だと失敗したので古いのでｗ−

$ vagrant plugin install --plugin-version 0.0.35  vagrant-libvirt

elkdatでboxをインストール

で、あとはgit cloneしたelkdatで、./initするだけど環境が構築される(スバラです＞＜*6

murase@debian:~/github$ cd elkdat/
murase@debian:~/github/elkdat$ ls
LICENSE  README.md  elkdat  example  fini  init  ktest  test
murase@debian:~/github/elkdat$ ln -s ../linux-stable linux
murase@debian:~/github/elkdat$ ./init
+ vagrant box add elastic/ubuntu-16.04-x86_64 --provider libvirt
Ignoring ruby-libvirt-0.7.0 because its extensions are not built.  Try: gem pristine ruby-libvirt --version 0.7.0
==> box: Loading metadata for box 'elastic/ubuntu-16.04-x86_64'
    box: URL: https://atlas.hashicorp.com/elastic/ubuntu-16.04-x86_64
==> box: Adding box 'eIgnoring ruby-libvirt-0.7.0 because its extensions are not built.  Try: gem pristine ruby-libvirt --version 0.7.0
Bringing machine 'ktest' up with 'libvirt' provider...
==> ktest: Uploading base box image as volume into libvirt storage...
==> ktest: Creating image (snapshot of base box volume).
lastic/ubuntu-16.04-x86_64' (v20161120.0.0) for provider: libvirt
    box: Downloading: https://atlas.hashicorp.com/elastic/boxes/ubuntu-16.04-x86_64/versions/20161120.0.0/providers/libvirt.box
==> box: Successfully added box 'elastic/ubuntu-16.04-x86_64' (v20161120.0.0) for 'libvirt'!
+ pushd elkdat
~/github/elkdat/elkdat ~/github/elkdat
+ vagrant up
Ignoring ruby-libvirt-0.7.0 because its extensions are not built.  Try: gem pristine ruby-libvirt --version 0.7.0
Bringing machine 'ktest' up with 'libvirt' provider...
==> ktest: Uploading base box image as volume into libvirt storage...
==> ktest: Creating image (snapshot of base box volume).
...

残りはqiitaの手順にしたがっていろいろやってみるぞい

P.S.　600個目の記事っぽいｗ−ｂ

*1:うちの環境だとARMv8のrepo syncのmake allが失敗してる

*2:ARMv8には入ってたけど、こっちgdbの接続方法わからない

*3:それはそれで楽しそうだが、まあ時間がないｗ−

*4:ubuntu16.04だと編集内容がすでに反映されていたので不要

*5:stable/jessieだとunix_sock_gropuがlibvirt(dがない)になってた

*6:DL時間節約のために、linux.gitは事前にclone済のをシンボリックリンクしておく

組み込みのちっちゃい系OSメモ

OPTEE v6 McKernel mbed Zephyr Mini-OS

　お仕事がそっち系で、まあ勉強しないと行けないのでｗ−
手始めにxv6コード読みと弄りしたいと思うが、序にいろいろ調べたのをペタペタしておく。