read-eval-print loop

プログラミング関連のメモ

メンバー関数にもとづいてソートする

C C++ Tips

「オブジェクトの状態に依存したソートを行いたい」ということがあると思います。

#include <vector>

using namespace std;

class A {
public:
  A(int k);
  vector<int> sorted();
private:
  vector<int> vec;
  int param;
};

A::A(int k) {
  param = k;
}

vector<int> A::sorted() {
  // paramに依存したソートをして返す
}

そこでメンバー関数をsortの比較関数に使う方法として

  1. bind関数を使う方法
  2. 関数オブジェクトを定義する方法

の2つを紹介したいと思います。 （後続のコードのうち既出のコードと重複する部分を適宜省略します。）

1. bind関数を使う方法 （C++11以降）

#include <function> // bind

using namespace std::placeholders;

class A {
private:
  bool cmp(int a, int b);
}

vector<int> A::sorted() {
  vector<int> ret = vec;
  sort(ret.begin(),ret.end(),bind(&A::cmp,this,_1,_2));
  return ret;
}

bool A::cmp(int a, int b) {
  return a%param < b%param;
}

考えてみればparamもbindを使って渡せるのでcmpが2引数である必要もないですね。

2.関数オブジェクトを明示的に定義する方法

比較のためのクラスcmpを定義し、関数呼び出し演算子()をオーバーロードします。

class A {
private:
  class cmp {
  public:
    A &a;
    cmp(A &a) : a(a) {};
    bool operator() (int x, int y) {
      return x%a.param < y%a.param;
    };
  };
};

vector<int> A::sorted() {
  vector<int> ret = vec;
  sort(ret.begin(),ret.end(),cmp(*this));
  return ret;
}

とくに前者のような関数型のアプローチは適用範囲が広そうなので、覚えておいて損はないと思います。

forループで符号なし整数を使って0までカウントダウンする

C C++ Tips

for文で符号なし整数を0までカウントダウンする場合、当然ですが>= 0という条件は使えません。

// 条件が常に真になるため無限ループ
for (unsigned int i = n-1; i >= 0; i--)

可能ならば符号付き整数にキャストしてしまう、i == 0の場合をforの外に出す、といった方法が考えられますが、よりスマートに次のようにも書くことができます。

for (unsigned int i = n; i-- > 0; )

本文のiもちゃんと欲しい値になっています。

また、符号なし整数がラップアラウンドすることを利用して*1、次のように書くことができます。

for (unsigned int i = n-1; i != UINT_MAX; i--) 
// もしくは
for (unsigned int i = n-1; i != -1; i--)

-1は整数変換のルールによりUINT_MAXに変換されることに注意。

残念ながら、どちらの方法も初期値が最大値を取る場合は使えません。

参考：

c++ - Reverse iteration with an unsigned loop variable - Stack Overflow

INT02-C. 整数変換のルールを理解する

*1:正確には、符号なし整数で値が表現できない場合は、最大値より1大きい値で割った余りになることと-1 = -1* (UINT_MAX+1) + UINT_MAXから

リンクをスクリプトファイルに張ったときスクリプトファイルのパスを取得する

Python Tips

シンボリックリンクを介してスクリプトを実行すると、スクリプト内の__file__にはシンボリックリンクの情報が格納されます。

import os.path

print(__file__)
# -> リンクのパス
print(os.path.dirname(__file__))
# -> リンクの親ディレクトリ

os.path.realpath()を使えばリンクではなくスクリプト自身のパスを取得できます。

print(os.path.realpath(__file__))

二分木を配列で持つときのインデックスづけについて

アルゴリズム データ構造

二分木は一次元の配列として表現できます。例えば、インデックス0をルートとして、xの左の子は2*x+1,右の子は 2*x+2といった具合です。

ところで、このインデックスづけは1.「どの子のインデックスも他の子やルートと被らない」という必須の性質と、2.「配列に隙間がない（あっても定数サイズ）」というよい性質を持ちます。このことを簡単に確認してみましょう。(自明だという人も多いと思いますが、自分は式が天下り的に与えられて悩みました)

まず1.について 2 x + 1と 2 x + 2は単調増加で、かつ x \ge 0でとる整数値がそれぞれ( 0でない)奇数と偶数であるため成り立つことが分かります。また2.については 2 (x+1) + 1 = 2 x + 3と 2 (x + 1) + 2 = 2 x + 4より、インデックスが小さいほうから敷き詰められていくため、こちらも成り立つことが分かります。

これを頭に入れておくと、いざ使うときに「式何だっけ？」とならずに済みます。またルートを1、左の子をx << 1、右の子をx << 1 | 1とするようなインデックスづけも正当であることが分かります。

HackerRank: Kingdom Division

別解 HackerRank

HackerRankの問題Kingdom Divisionの自分の解法が解説のものとは異なっていたのでアイデアをメモ。

木についての再帰を使って場合の数を数え上げる。そのために部分木に注目した際の２つのカテゴリを考える。

  • open: 部分木の根の都市が味方の都市と接していない。
  • closed: 部分木の根の都市が味方の都市と接している。

ただし、根以外のノードについては味方の都市と接しているものとする。以下では根の都市を一方の陣営に固定した場合を考える。葉にあたる都市についてopenな場合の数は1、closedな場合の数は0となる。また親ノードの場合の数は、子ノードの場合の数から次のように再帰的に計算できる。

openな場合の数

\displaystyle Open(v) = \prod_{c \in child(v)}^{} Closed(c)

closedな場合の数

\displaystyle Closed(v) = \prod_{c \in child(v)}^{} (Open(c) + 2 \cdot Closed(c)) - \prod_{c \in child(v)}^{} Closed(c)

説明しておくと、openな子は味方となるのが親しかいないのでopenな(=味方のいない)親の子になることはない。そのため Open(v)は一番目の式で定まる。 Closed(v)の計算で Closed(c)を2倍しているのは敵味方どちらでもよいからである。またclosedな親には少なくとも一つ味方となるような子が必要なので、敵ばかりとなるような場合の数を引いている。

したがって、この問題はDFSを行うことで簡単に解くことができる。ただし再帰が深くなるので再帰関数で実装するとスタックオーバーフローを起こす（と思う）。

Linuxでデバイスがマウントされているか知る方法

Linux

例えば、外付けHDDが接続されていない（マウントされていない）状況で、そのディスクをターゲットとしたバックアップを実行すると、マウントポイント以下、つまり内蔵ディスクに対してバックアップファイルが生成されてしまいます。 これを防ぐためには、ディレクトリがマウントポイントかどうかをチェックするmountpointコマンドが使えます。

mountpoint -q <ディレクトリ> && rsync ...

mountpointコマンドがない場合は、/proc/mountsとgrepの組み合わせが使えます。

HaskellでPerl互換の正規表現ライブラリの使い方と比較

Haskell 正規表現 PCRE

HaskellのPerl互換の正規表現ライブラリregexpr, regex-pcre, pcre-light, pcre-heavy, text-icuの使い方と差異についてまとめてみました. ただし, あくまで現時点での情報に基づいていることにご留意ください. また, 使い方といっても網羅することは到底叶いません. それでも, 使い勝手, ライブラリの特徴, 注意点などは感じ取っていただけるかと思います.

Haskell初心者の方へ

HaskellにはParsecという正規表現より強力なパーサライブラリがあります. 正規表現では記述に無理があるような場合でも, Parsecを使えばすんなり書けてしまうかも知れません. ぜひ利用を検討してみてください. 使い方については, 例えばReal World Haskellの第16章が参考になります.

簡単なまとめ

ライブラリの機能を簡単に整理すると次のようになります.

日本語 置換 分割 Cラッパー compileM
regexpr ○ ○ ○ N ×
regex-pcre × × × Y ○
pcre-light △ × × Y ○
pcre-heavy ○ ○ ○ Y ○
text-icu ○ × × Y ○

"Cラッパー"はバックエンドとしてpcreを使っているかを表しています. このようなライブラリではpcre向けのオプションを用意していることが多いようです. "compileM"は不正な正規表現文字列に対してfailするコンパイル関数を持っているかを表しています. このような関数を持たない場合, 不正な正規表現を検知するためには例外を受ける必要があるでしょう.

注意点

pcre系のライブラリで日本語文字を扱う場合に上手く行かない原因として

  1. utf8オプションのつけ忘れ
  2. -XOverloadedStringsとByteStringとの併用

が挙げられます. 2.は一般にData.ByteString.UTF8.fromStringやConvertibleStringsのメソッドconvertStringを用いて適切にデータ変換することで解決できます. 以下のコード例では, この2つをその場その場で適当に使ってしまっていますが, 基本的には互いに置き換え可能です.

次から各ライブラリについて使い方を中心に詳しく見ていきます.

regexpr

  • 型がシンプルでわかりやすい
  • 対象はString型
  • Perl風の置換
  • 関数による置換

型はStringとタプルおよびリストから構成されていて, それだけ見れば何ができるか分かります. 関数の個数も10個程度におさまっているので, 容易に使いこなせるでしょう.

使い方

> matchRegexPR "(\\d+)-(\\d+)-(\\d+)" "\t111-2222-3333\t"
Just (("111-2222-3333",("\t","\t")),[(3,"3333"),(2,"2222"),(1,"111")])

マッチの全体, 前後, 番号付きのキャプチャが返ってきています.

マッチするものをすべて取り出すには, gmatchRegexPRかmultiMatchRegexPRを使います. gmatchRegexPRは前回のマッチの後続部分のみを探索しますが, multiMatchRegexPRは前回マッチした部分も探索します.

> gmatchRegexPR "ab*" "abbbbabb"
[(("abbbb",("","abb")),[]),(("abb",("","")),[])]
> multiMatchRegexPR "ab*" "abbbbabb"
[(("abbbb",("","abb")),[]),(("abbb",("","babb")),[]),(("abb",("","bbabb")),[]),(("ab",("","bbbabb")),[]),(("a",("","bbbbabb")),[]),(("abb",("abbbb","")),[]),(("ab",("abbbb","b")),[]),(("a",("abbbb","bb")),[])]

\数記法を使った置換. {}で数を囲うことで曖昧さを排除できます.

> gsubRegexPR "(?:,(\\d+))|(?:(\\d+),)" "\\1\\{2}0" "123,456,789"
"12304560789"

関数を使った置換も可能です.

> putStrLn $ gsubRegexPRBy "(\\d+)" (\n -> "{" ++ show (length n) ++ "桁の数}") "123abcd45678efghi"
{3桁の数}abcd{5桁の数}efghi

regex-pcre

  • regex-baseのバックエンド
  • compileM = makeRegexM :: -> m Regex, makeRegexOptsM :: -> m Regex

一般にregex-base系の正規表現ライブラリは慣れるまでが難しいのですが, 多相性のおかげで非常に柔軟な結果を得ることが出来ます. 逆にregex-baseに既に慣れている人であれば, このライブラリをすぐに使うことができるでしょう.

このライブラリには, 後述のように日本語文字を正しく扱えないバグがあります.

使い方

型注釈を変えることで様々な結果を得られます.

> "abbbbabb" =~ "(ab*)" :: Bool
True
> "abbbbabb" =~ "(ab*)" :: Int
2
> "abbbbabb" =~ "(ab*)" :: String
"abbbb"
> "abbbbabb" =~ "(ab*)" :: [[String]]
[["abbbb","abbbb"],["abb","abb"]]
> "abbbbabb" =~ "(ab*)" :: MatchArray
array (0,1) [(0,(0,5)),(1,(0,5))]
> "abbbbabb" =~ "(ab*)" :: [MatchArray]
[array (0,1) [(0,(0,5)),(1,(0,5))],array (0,1) [(0,(5,3)),(1,(5,3))]]
> "abbbbabb" =~ "(ab*)" :: [MatchText String]
[array (0,1) [(0,("abbbb",(0,5))),(1,("abbbb",(0,5)))],array (0,1) [(0,("abb",(5,3))),(1,("abb",(5,3)))]]

結果として得られるデータ型はまだまだあります.

=~~はモナドを返します.

> "abbbb" =~~ "(ab*)" :: Maybe String
Just "abbbb"
> "bbbb" =~~ "(ab*)" :: Maybe String
Nothing

pcreのオプションを使う場合は=~が使えません. makeRegexOpts等で正規表現をコンパイルし, match等の関数を使う必要があります.

> let re = makeRegexOpts (compUngreedy .|. compCaseless) defaultExecOpt "(ab*)" :: Regex
> match re "ABBBBABB" :: [[String]]
[["A","A"],["A","A"]]

バグについて

regex-pcre-0.94.4にはStringオーバーロードが日本語の文字などを正しく扱えないというバグがあります.

[Haskell-cafe] regex-pcre is not working with UTF-8 - Google グループ

正規表現 - 日本語を含む文字列から正規表現を使って抽出する方法 - スタック・オーバーフロー

例

> let res1 = "abbbbabb" =~ "ab*" :: [[String]]
> let res2 = "あばばばばあばば" =~ "あば*" :: [[String]]
> mapM_ putStrLn $ concat res1
abbbb
abb
> mapM_ putStrLn $ concat res2
あばばばばあ

-- compUTF8を付けても同様
> let re = makeRegexOpts compUTF8 defaultExecOpt "あば*" :: Regex
> let res3 = re `match` "あばばばばあばば" :: [[String]]
> mapM_ putStrLn $ concat res3
あばばばばあばば

これはpcreが返すオフセットおよび長さと, HaskellのStringのそれとの間のズレが修正されていないことが原因です.

以下に, 回避策を示します. いずれの場合もcompUTF8オプションが必要です.

方法1: ByteStringを使う

Stringの代わりにByteStringを使えば問題を回避できます.

> import qualified Data.ByteString.UTF8 as U
> let res = re `match` (U.fromString "あばばばばあばば") :: [[ByteString]]
> mapM_ (putStrLn . U.toString) $ concat res
あばばばば
あばば

方法2: パッチをあてる

Haskell-cafeにパッチがアップロードされています. ただしこのパッチは未完成でmatchAllTextなどは正しく動作しないようです.

pcre-light

  • シンプル
  • 対象はByteString型
  • compileM = compileM :: -> Either String Regex

使い方

-XOverloadedStringsに注意. ダブルクォートで囲まれた文字列をByteStringやTextのリテラルとして扱ってくれるものです.

> :set -XOverloadedStrings 
> match (compile "(ab*)b" []) "abbbbabb" []
Just ["abbbb","abbb"]

全てのマッチを取り出すには自前のコードを書く必要がありそうです.

import Control.Monad (liftM2)
import qualified Data.ByteString as BS
import Text.Regex.PCRE.Light

gMatch :: Regex -> BS.ByteString -> [PCREExecOption] -> Maybe [[BS.ByteString]]
gMatch re bstr opts =
  let m = match re bstr opts
  in case m of
       Just m' -> liftM2 (:) m $ gMatch re (BS.drop (BS.length $ head m') bstr) opts
       Nothing -> return []

> gMatch (compile "(ab*)b" []) "abbbbabb" []
Just [["abbbb","abbb"],["abb","ab"]]

日本語文字を使う場合はData.ByteString.UTF8.fromStringで変換し, さらにutf8オプションを付加しなければなりません.

> import qualified Data.ByteString.UTF8 as U
> let res = gMatch (compile (U.fromString "(あば*)ば") [utf8]) (U.fromString "あばばばばあばば") []
> mapM_ (putStrLn . U.toString) $ concat $ fromJust res
あばばばば
あばばば
あばば
あば

pcre-heavy

  • pcre-lightがベース
  • 対象はString型, ByteString型, Text型*1
  • 関数による置換
  • QuasiQuotation
  • compileM = compileM :: -> Either String Regex (from pcre-light)

使い方

QuasiQuotationに対応しているので正規表現がそのまま書けます.

> "123-4567-89" =~ [re|\d{3}-(\d{4})-\d{2}|]
True
> scan [re|\d{3}-(\d{4})-\d{2}|] "123-4567-89"
[("123-4567-89",["4567"])]

グローバルな置換, 関数による置換が可能です.

> :set -XScopedTypeVariables
> gsub [re|\d+|] (\(s::String) -> reverse s) "123-4567-89"
"321-7654-98"

日本語もオプション無しでそのまま扱えます.

-- StringとText
> import qualified Data.Text as T
> :set -XOverloadedStrings
> let sres = scan [re|(あば*)|] ("あばばばばあばば" :: String)
> let tres = scan [re|(あば*)|] ("あばばばばあばば" :: T.Text)
> mapM_ (putStrLn . fst) $ sres
あばばばば
あばば
> mapM_ (putStrLn. T.unpack . fst) $ tres
あばばばば
あばば

-XOverloadedStringsが無効な時はConvertibleStringsのメソッドconvertString=csを使ってByteStringを処理できます.

> :unset -XOverloadedStrings 
> let bres = scan [re|(あば*)|] (cs "あばばばばあばば" :: BS.ByteString)
> mapM_ (putStrLn . U.toString . fst) $ bres
あばばばば
あばば

text-icu

  • シンプル
  • 対象はText型
  • compileM = regex' :: -> Either ParseError Regex

text-icuはユニコード操作のためのパッケージ（らしい）です. 正規表現機能をその一部として含んでいます.

使い方

> find (regex [] "(ab*)") "abbbbabb"
Just Match ["abbbb","abbbb"]
> findAll (regex [] "(ab*)") "abbbbabb"
[Match ["abbbb","abbbb"],Match ["abb","abb"]]

Match型からは様々な情報を取り出せます.

> let m = fromJust $ find (regex [] "(\\d{3})-(\\d{4})-(\\d{2})") "123-4567-89"
> group 1 m
Just "123"
> group 2 m
Just "4567"
> prefix 1 m
Just ""
> suffix 1 m
Just "-4567-89"

日本語もそのまま扱えます.

> let res = findAll (regex [] "(あば*)") "あばばばばあばば"
> T> mapM_ (\m -> putStrLn . T.unpack . fromJust $ group 1 m) res
あばばばば
あばば

さいごに

この記事では各ライブラリのおもだった使い方とライブラリ間の差異を紹介しました. ここで挙げたことの他にも, オプションの種類など選択基準となる要素はたくさんあります. ぜひパッケージのドキュメントをあたって, 用途に適したライブラリを探してみてください.

*1:正確には(ConvertibleStrings SBS a, ConvertibleStrings a SBS） => a