読者です 読者をやめる 読者になる 読者になる

callstack

プログラミングでいろいろやる

ヤング盤

最近,優先度付きキュー(Priority Queue)に興味があったので色々調べていたら,
ヤング盤(young tableau)というものを見つけました.
有名なあの書物で,ヒープソートの章の練習問題で出てくるらしいですね.
詳細は他の文献に譲るとして,定義は以下の通り.

ヤング盤は、ヤング図形を一つ取り、同図形の n 個の箱に 1, 2, …, n の数を、以下の制約に基づいて埋めることによって得られる。

  • 各行で、数は左から右に増加する。
  • 各列で、数は上から下に増加する。

(出典:Wikipedia)

例えば3x3の表で配列A=[5, 3, 2, 1, 4]が与えられたとして,

1 3 5
2 4 -
- - -

みたいな感じですかね.上の定義でいくと,与えられた配列を昇順ソートして,

1 2 3
4 5 -
- - -

のように入れてもヤング盤といえます.
並べ方は色々ありますが,共通しているのは左上の要素が最小値になることですね. なんか面白そうなので勉強がてら実装しました.言語はRuby(2.3.0).

https://gist.github.com/rk0der/411a73309e3c10b91250ce9592237581

値の追加(insert)と最小値の取り出し(extract)を実装しました.
これらの操作後は再構築が実行されるので,常にヤング盤が維持されます.

上のプログラムは

m n a1 a2 ...

という入力をとり, m × n の表を作り,そこにa1, a2, ... から成る配列を元にヤング盤を構築します.

ruby young_tableau.rb
3 3 5 3 2 1 4
1
2
3
4
5

やっぱり優先度付きキューじゃないか.訴訟.

Moshの接続簡易化スクリプトを書いた

Mosh

最近,リモートマシンで作業するのにSSHではなくMoshを使っています.
スリープ復帰時の自動接続はとても便利です. ただ少し接続が面倒だったので簡易化するスクリプトをメモ.

他のブログ等でよく書かれているやり方では,

  1. リモートマシンでmosh-serverを実行
  2. 出力のMOSH_CONNECTの行からポートとキーをコピー
  3. クライアント側でexport MOSH_KEY=<コピーしたキー>を実行する
  4. クライアント側でmosh-client 接続先IP <コピーしたポート>

という手順を踏んで接続します.
mosh-serverは60秒間接続が無いと死ぬので,60秒以内に上の作業をやる必要があります.
途中で手間取るとmosh-serverが落ちて最初からやり直し...

書いた

できればsshみたいに使いたいのでこんなものを書いた.

  • moshup.sh
#!/bin/sh

if [ $1 = '-h' -o $1 = '--help' ]; then
  echo 'Usage: ./moshup.sh username@ip_addr'
  exit
fi

MOSH_SV_EX='mosh-server'
MOSH_CL_EX='mosh-client'

remote_host=$1
ip_addr=`echo $remote_host | cut -d'@' -f2`

moshout=`ssh $remote_host $MOSH_SV_EX`
data=`echo $moshout | grep 'MOSH CONNECT' | cut -d' ' -f3,4`
set -- $data
port=$1

export MOSH_KEY=$2
$MOSH_CL_EX $ip_addr $port

実行は

./moshup.sh hogehoge@xxx.xxx.xxx.xxx

おわり

卓越したタイピングスキルと操作精度があれば普通の方法でもよいかも.
あと他の楽な接続方法が多分あると思うので教えていただけたらうれしいです.