シャッフル 1.9のString PDFプリンタ (2011/03/05)

shuffle

Class Array
  def shuffle
    self.each_with_index{|v, i|
      self[i]=self[(ri=rand(i+1))]
      self[ri]=v}
  end
end

通称 Knuth のシャッフルと言われるアルゴリズムです。発明したのは Knuth 先生ではないのですが、彼の著作で有名になったアルゴリズムです。一見、これでちゃんとシャッフルされるかどうかは自明ではないと私には思われたので、ちょっと考えてみました。

長さ2のリストについて、このアルゴリズムが正確に動作するかどうかは rand が願いどおりに動くかどうかにかかっています。それがokだとすれば、ちゃんと動きます。

長さ $n$ のリストについてちゃんと動くと仮定します。このとき、長さ $n+1$ のリストの末尾の要素はこのアルゴリズムを適用した結果、リスト全体に等確率$\frac{1}{n+1}$で出現します。

先頭から長さ$n$ の部分列は、仮定から各要素が部分列内部に均等に確率 $\frac{1}{n}$ で出現するので、これが末尾と確率 $\frac{1}{n(n+1)}$ で交換された結果、やはりその場所に出現する確率は $\frac{1}{n} - \frac{1}{n(n+1)} = \frac{1}{n+1}$

つまり、長さ$n+1$ のリストでも、全ての要素が全ての場所に均等に確率 $\frac{1}{n+1}$ で出現します。

ところで、手でやる場合にカードをどう切ればちゃんとシャッフルされるのか、というのはなかなか難しい問題みたいです。

祝 Squeeze released

ということで Debian unstable も間接的にだいぶ入れ換えがありました。

open office が libreoffice にころもがえしたため、 upgrade するときに消えたものが幾つかあったので、それを手で入れ直しました。

関係あるのか無いのか判りませんが、プリンタも動かなくなりました。これは、関係ありそうな削除されたパッケージを入れ直して、プリンタの登録をやりなおしたら治りました。いまのところ、他に大きなトラブルもなく普通にいろんなものが動いています。 openoffice は請求書を書いたりするのの欠かせないので、動かなくなった時は若干焦りました。

出力先をPDFに

PDFオーサリングツールにはいろんなものがありますが、「できあがって印刷にまわしてもいいデータ」をPDFの状態でとっておきたい、という要望は昔からあるわけです。 unix の世界ではあらゆるものがファイルですから、これは OS の使用感としても自然な発想です。

最近は cups というものがあって、 Debian でもちゃんと動いて非常に便利なわけですが、これのプリンタ選択オプションで、そういう機能が実現されたら便利で好ましいわけです。

一方、 OpenOffice の impress では、プレゼンテーション資料を PDF として export するときに一枚一ページで export されてしまいます。配布資料としては一枚に複数ページが掲載されている形式が一般的ですが、これが選べません。ハンドアウトの出力先はプリンタになってしまいます。これを PDF として誰かに渡したいという場合は万事休す。

そこでプリンタとして PDF ファイルを選べば全ては解決するわけです。

yuji@dedepo:~%aptitude search pdf | grep printer
i   cups-pdf                        - PDF printer for CUPS                      
p   ppdfilt                         - filter that inserts printer specific comma

cups-pdf をインストールします。すると cupsd が再起動されて、システム管理メニューのプリンタ設定で、 PDF プリンタを追加できるようになります。

impress のハンドアウトの出力先に pdf を選びます。さて、ここで問題が発生しました。そのPDFファイルは広大なファイルシステムのいったいどこに存在してるんだ？

/etc/cups/cups-pdf.conf に次のエントリがあります

### Default: /var/spool/cups-pdf/${USER}

Out ${HOME}/PDF

つまり ~/PDF にできているぽいですね。見てみましょう。お。ありました。

これの便利なところは、そのままだと全部印刷されてしまうアプリケーションでも、PDF でならページ数を指定して印刷できるところですよ。

Ruby1.9 もじれつ

先日らい、徐々に 1.9 を使い始めている。こっちのが微妙に速いので。 1.9 は文字列関係が大幅に強化されているわけだが、 1.8 の文字列扱いでも大して困ってなかった俺にはヒジョーにオーバーヘッドなのでめんどくさくて無視していた。しかしやはりここはちゃんとキャッチアップしないといけない機運が高まって来たので、調べてみたところ、おもったより簡単でした。

内部で保持するデータ、入力、出力それぞれにエンコーディングがある。

EUC-JP のデータを読むにはこうする

str=File.open("hoge", "r:EUC-JP").read

こうやって読み込んだ文字列は EUC-JP エンコーディングになっている。

str.encoding
=> #<Encoding:EUC-JP>

このように、文字列のインスタンスがエンコード情報を保持しています。違うエンコードでの出力は出力するために開いたIOで、たとえば "w:UTF-8" と属性をセットするといい。

どんなエンコーディングが使えるのかな？

irb(main):061:0> Encoding.list
=> [#<Encoding:ASCII-8BIT>, #<Encoding:UTF-8>, #<Encoding:US-ASCII>, #<Encoding:Big5>(以下略

1.9.2 では 95個使えるようです。エンコードを指定するための名前は Encoding.name_list で取得できます。名前はエンコード本体よりも少し冗長で160個以上あります。エンコーディングの変更はずばり encode で引数はエンコーディング名です。

irb(main):078:0> str[-2].encode("UTF-8")
=> "せ"

破壊的にエンコードを変更する encode! もあるのは御想像のとおり。

基本的に読み書きするエンコードが決まってる場合は、昔懐かしい $KCODE の代わりにファイルの頭のほうに

# encoding: UTF-8

という具合にマジックコメントを書くのが良いようです。

この記事が解りやすくて参考になると思います。

1.9.2 から Random クラスというのができていて、rand なインスタンスをたくさん出したり、 Marshal しておけるようになっています。これがいまいち何が便利なのかしっくり来ないのですが、ややこしい事が一つあって、俺製 random variables 生成ルーチンを Random モジュールとしてまとめてたんですが、これが名前がカチあって引っ越さざるをえなくなりました。まぁ中身は Phython の実装をそのままパクってきたりしてるんですけどね。

私としては、 1.9 で一番ありがたいのは、変数のスコープがレキシカルになった事です。残念なのは Thread でマルチコアが使えないところ。

記事リストへ