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

有向グラフの簡潔表現GLOUDS

ネタ元

Johannes Fischer, Daniel Peters: GLOUDS: Representing tree-like graphs. J. Discrete Algorithms 36: 39-49 (2016)

概要

  • 木の簡潔データ構造LOUDSを拡張した有向グラフの簡潔データ構造GLOUDSを提案する
  • in-edgeが2以上のノードをコピーして、グラフを木に変換しLOUDSに似たデータ構造で表現する
  • in-edgeの数が少ない、つまり木に近い有向グラフの場合効果を発揮する

LOUDS

木のビット表現。LOUDSの話は今までにも聞いたことがあるが、この論文の説明が一番わかり易い。

  • 各ノードを1*子の数+0で表現する(0が親、1が子ノードを表すと考えると分かりやすい)
  • level-order(深さ毎)にノードの01表現を連結する
  • level iでk番目に出現する1で表された子ノードは、level i+1でk番目に出現する0で表された親ノードに対応する
  • この性質から、親から子、子から親へ01表現のrank, selectで辿ることが出来る

GLOUDS

次のような方法で有向グラフから木を作る。

  • あるノードから有向辺で全てのノードに辿れるようなノードをrootと呼ぶ
  • 複数あり得るが、簡単のためrootが一つだけあると仮定する
  • rootノードからlevel orderで各ノードuを辿る
  • uの各子供vについて、vがまだ辿られていないノードだったら枝を貼る
  • vが既に辿られているノードだったらvをコピーしたshadowノードを作り、そのノードに枝を貼る

次にこの木を簡潔データ構造で表すにはどうすればよいかを考える。

  • vがまだ辿られていないノードであればvを1で表す
  • vがすでに辿られているノードであればvを2で表す
  • 親ノードuを0で表す

これで木を表すことが出来たが、これだけでは元の有向グラフで出来た操作が行えない。 以下の情報を付け加え、操作可能にする。

  • 有向グラフ上のノードは、変換した木上でshadowノードとそうでないノード(1ノードと呼ぶことにする)で表される
  • 1ノードは有向グラフ上のノードが表す子の情報全てと親の情報を1つ持っている。
  • shadowノードは親の情報を1つ持っている。
  • つまり、子を辿るためには、全てのshadowノードから対応する1ノードに、
  • 親をたどるためには全てのノードからそれ以外のノードへと遷移することが出来ればよい
  • 対応関係を整数文字列で表し、整数文字列上のrank, selectで実現する
  • level-orderで木を辿りshadowノードを、対応する1ノードのrank(何番目に出現したか)で表すことで木のshadowノードの出現を整数文字列Hとして持つ
  • H[i]=xはlevel-orderでi番目のshadowノードに対応する1ノードがlevel-orderでx番目に出現することを表す
  • 対応するノード間はこの文字列Hを経由し、木のrank, select、Hのrank, selectで対応するノード間を辿ることが出来る

その他

以下は今後覚えておくと良さそうなのでメモ

  • ビット配列上のrank, selectはn+o(1)bitsでO(1)時間で実行可能
  • rank, selectは文字列上にも拡張できる。
  • よく知られている方法だとn log σ(1 + o(1)) bitsでrankがO(log log σ)時間、selectがO(1)時間で実行可能、ここでσは文字種類数
  • 当たり前だが文字列を陽に持っていればn log σ bitsで各位置の文字にO(1)時間でアクセスできる
  • σ=wO(1)の時上記の3つの操作はより高速に実行可能、ここでwはワード長
  • この場合O(n log σ) bitsで上記3つの処理がO(1)時間で実行可能

apple wireless keyboardのcapsとcontrolを入れ替えた

Apple Wireless Keyboard (US)を買った。 HHKBも良いけど、このキーボードもなかなか良い。

HHKBや内蔵キーボードはControlがaの左に来るけど、このキーボードの場合はcapsになっているので前回の記事のように変更した。 kg86.hatenablog.com

最初はKarabinerを使って設定しようとしたが、control→capsは上手くいくが、caps→controlは上手くいかない。 どうやらcapsを違うキーに割り当てるにはSeilというソフトが追加で必要なようだ。 ドキュメントを読むとseilでcapsを一旦違うキーコードに割当て、karabinerで新しいキーコードを違うキーコードに割り当てるようになっている。 問題はkarabinerはキーボードデバイスごとの設定ができるのに、seilは全体設定しか無いこと。 これでは弄る必要のない、HHKBや内蔵キーボードまで影響が出てくる。

悩んでいたら、もっとシンプルな方法に気がついた。 デフォルトのキーボード設定でcapsとcontrolの入れ替えができる、しかもキーボードデバイスごとに。

[システム環境設定]→[キーボード]→[修飾キー]の順に選択すれば設定画面が表示される。

macでHHKBのキーを変更した

Happy Hacking Keyboard(HHKB)はキーが少なくて素敵だけど、macだとキーが少なすぎて直感とは違うキー配置になってしまう。 ディップスイッチを使うことで、キー配置を少しいじれるけど柔軟とは言い難く限界がある。

Karabainerを使ってキーの配置をいじってみた。 HHKBのみをキーを変更したいので、HHKBのデバイスをKarabiner の private.xml 設定方法 - Qiitaを参考にして登録する。 僕の環境では以下のようになった。

  <devicevendordef>
    <vendorname>PFU</vendorname>
    <vendorid>0x0853</vendorid>
  </devicevendordef>

  <deviceproductdef>
    <productname>HHKB</productname>
    <productid>0x0100</productid>
  </deviceproductdef>

僕の環境では(ディップスイッチの設定にもよると思う)2つのMetaキーがOptionキーになっていて、左AltがFnに、右AltがCommandキーになっている。 以下ではMetaキーをCommandに、右AltをOptionキーに割り当てている。

僕の使用方法ではOptionはEmacsでAltキーとしてしか使わないので、これぐらい使用頻度が少ない位置にして、Commandキーを使いやすくしたほうが良い。

<?xml version="1.0"?>
<root>
  <devicevendordef>
    <vendorname>PFU</vendorname>
    <vendorid>0x0853</vendorid>
  </devicevendordef>

  <deviceproductdef>
    <productname>HHKB</productname>
    <productid>0x0100</productid>
  </deviceproductdef>

  <item>
    <name>Swap Command and Option in HHKB</name>
    <identifier>private.hhkb</identifier>
    <device_only>DeviceVendor::PFU, DeviceProduct::HHKB</device_only>
    <autogen>__KeyToKey__ KeyCode::OPTION_L, KeyCode::COMMAND_L</autogen>
    <autogen>__KeyToKey__ KeyCode::OPTION_R, KeyCode::COMMAND_R</autogen>
    <autogen>__KeyToKey__ KeyCode::COMMAND_R, KeyCode::OPTION_R</autogen>
  </item>
</root>

HHKBだけ、キー変更が有効なことを確認した。概ね満足。 但し、元々Karabinerの設定でCommandキーを組み合わせで押さない場合は英数、かなキーとして振る舞う設定をしていたのだけど、今回新しく割り当てたコマンドキーではそのように振る舞ってくれなかった。 内部の設定の適用順序があるのだろうか?

f:id:kg86:20161121152744p:plain

もしかすると以下の記述が関係ある?

Karabinerでは設定を再帰的に反映することは出来ません。 一つの設定が反映された後は他の設定は無視されます。 マニュアル - Karabiner - OS X用のソフトウェア

映画「舟を編む」を観た

企画から出版に行き着くまでに10数年は掛かると言われる辞書作成作業に取り組んだ人たちの話。

途方もない作業に地道に取り組んでいる人とそれを支える人たちの姿がとても魅力的だ。

舟を編む 通常版 [DVD]

舟を編む 通常版 [DVD]

「はじめよう! 要件定義 ~ビギナーからベテランまで」を読んだ

非常に平坦に書かれていて読みやすい。

はじめよう!  要件定義 ~ビギナーからベテランまで

はじめよう! 要件定義 ~ビギナーからベテランまで

こういった専門分野の人にとっては当たり前の知識を、そのエッセンスだけつまみ食いすることで知識や考えの幅が広がると思って実践中。 この本は優しい言葉で重要な事が書かれている。 素晴らしいのは重要なことが繰り返し繰り返し、ダメ押しのように書かれていること。 最重要する事柄を見失わずに、他のことはそれを補強するようなアクションを起こしていく。 最初から最後まで一筋の道が見えているのでとても分かりやすい。

特定のサイトへのアクセスを制限する

maclinuxに適用可能ですが、おそらくwindowsでも同様の方法で設定可能です。

はじめに

趣味でプログラミングや英語の勉強だったりしてると、集中したいと思っている思いとは反対についついtwitteryoutubeに手を出してしまうといった事が多いと思います。 最近だとtwitterが長い動画に対応したり、youtubeはどんどん高画質で面白くなっていったりで、時間はどんどん奪われていく一方ですね。

今回は本当にやりたい事に集中するために、特定のサイトのアクセスを制限する方法を試したいと思います。

/etc/hostsでアクセス制限する

方法は簡単。 /etc/hostsの末尾に以下を書き加えます。 0.0.0.0に空白を入れてアクセス制限をしたいURLを記入すれば完了です。

0.0.0.0 youtube.com
::      youtube.com
0.0.0.0 www.youtube.com
::      www.youtube.com
0.0.0.0 www.facebook.com
::      www.facebook.com
0.0.0.0 twitter.com
::      twitter.com
0.0.0.0 facebook.com
::      facebook.com
0.0.0.0 api.twitter.com
::      api.twitter.com
0.0.0.0 www.twitter.com
::      www.twitter.com
0.0.0.0 facebook.com
::      facebook.com
0.0.0.0 www.facebook.com
::      www.facebook.com

仕組みは単純で、記入したURLに向こうなipアドレスを指定するため結果としてアクセスできなくなります。

指定したら、DNSキャッシュを消すために以下のコマンドを打つ(macのみ、Linuxは未確認)。

sudo dscacheutil -flushcache;sudo killall -HUP mDNSResponder;

chromeの場合は独自でキャッシュしてるため、chrome://net-internals/#dnsにアクセスして、「Clear host cache」をクリック。

試すと、若干のタイムラグはあったが、アクセス制限できるようになりました。

戻す場合は、該当の行をコメントアウトして、同じようにDNSのキャッシュをクリアすればOK。

CUIが苦手でmacの人は、GUIで設定できるアプリもあります、SelfControl。 正確に理解していませんが、同様に/etc/hostsをいじっているようです。

Windowsでもホストを設定するファイルがあるようなので、同様に設定すれば出来るんじゃないかと思います。 Windowsの場合はフリーソフトが沢山ありそうですが。

補足

macで設定する場合、理由は分かりませんが、設定内容がうまく反映されないことがあります。 回避方法としては、ipv6で設定するとうまく行くと報告があったりしますが、それでもうまくいかないという報告もあったりします。 僕も原因がわからないので注意して下さい。 バグに近いのであまり、深追いをせず出来ない場合は諦めるのも手だと思います。

エルゴノミクスマウスのボタンをカスタマイズして負荷軽減する(mac)

仕事柄PCを一日中使っているせいで、腱鞘炎、肩こりを発症して毎日辛い思いをしてます。

セルフマッサージやストレッチを試してみたものの悪化の一途を辿り、現在はマウスをクリックするだけで、クリックした指、手首、手首したの腕、肩が同時に痛んでしまう重傷の状態です。

いろいろ調べた結果、人間工学(エルゴノミクス)的に良いマウスが売られているようなので購入してみました。

最初に触った感触は凄く良く、マウスを持った状態に緊張感はまったくなく極論すれば手をおいて休めている感覚に近いです。 さすがエルゴノミクス、この値段でこの体験が出来るのはお値段以上です。

ただ、クリックに関しては他のマウスと変わらないという感想です。 僕の症状が重傷のためですが、やはり痛い。

マウスの形状自体はすごく良いのに、ボタンが少し残念だと思っていたら、あることに気づきました。 このマウス5ボタンなんですが、ちょうど4,5ボタンが親指にあるんですね。 試しに触ってみると、人差し指でクリックするよりかは楽にクリックできました。

ということは、4,5ボタンに1,2ボタンを割り当てればより負荷軽減できるのではと思ったので実際にやってみました。

Karabiner というツールを使えば、任意のキーをカスタマイズできます。

カスタマイズ方法は以下が参考になります。 【Mac】5ボタンマウスの進む戻る(サイド)ボタンを有効化する方法 - 光のカナダ留学blog

実際に4,5ボタンを1,2ボタン、もしくは2,1ボタンに割り当てる設定を追加しました。

<?xml version="1.0"?>
<root>
  <item>
    <name>Mouse 4 and 5 Button to Right and Left Button</name>
    <identifier>private.mouse45torl</identifier>
    <autogen>--PointingButtonToKey-- PointingButton::BUTTON5, PointingButton::LEFT</autogen>
    <autogen>--PointingButtonToKey-- PointingButton::BUTTON4, PointingButton::RIGHT</autogen>
  </item>
  <item>
    <name>Mouse 4 and 5 Button to Left and Right Button</name>
    <identifier>private.mouse45tolr</identifier>
    <autogen>--PointingButtonToKey-- PointingButton::BUTTON4, PointingButton::LEFT</autogen>
    <autogen>--PointingButtonToKey-- PointingButton::BUTTON5, PointingButton::RIGHT</autogen>
  </item>
</root>

使用した感じでは、ボタンを入れ替える前に比べ、痛みが激減し負荷軽減できていることが実感できました。

今回はmacの設定方法の紹介しましたが、単純にキーコードを入れ替えているだけなのでLinuxWindowsでも簡単にできると思います。