2017/09/28

Python Tips:Python で文字列を切り詰めたい

Python で文字列を切り詰める方法についてご紹介します。

いろんな方法があるように思いますが、今回はその中で次の 2 つの方法をご紹介してみます。

  • A. スライスで切り詰める
  • B. テンプレートに埋め込むときに切り詰める


A. スライスで切り詰める


こちらは文字列のスライスを使って切り詰める方法です。こちらはシンプルですね。

s1 = '露と落ち 露と消えにし 我が身かな 浪速のことは 夢のまた夢'
s1_truncated = s1[:10]

print(s1_truncated)
# => 露と落ち 露と消えに

関数化するなら例えば次のような形になるでしょうか。

def truncate(string, length, ellipsis='...'):
    '''文字列を切り詰める

    string: 対象の文字列
    length: 切り詰め後の長さ
    ellipsis: 省略記号
    '''
    return string[:length] + (ellipsis if string[length:] else '')

print(truncate('露と落ち 露と消えにし 我が身かな 浪速のことは 夢のまた夢', 10))
# => 露と落ち 露と消えに...
print(truncate('朝ぼらけ', 10))
# => 朝ぼらけ
# => 


B. テンプレートに埋め込むときに切り詰める


こちらは文字列型の format() メソッドの機能を使った方法です。

s2 = '嬉しやと 二度さめて一眠り うき世の夢は 暁の空'

print('{:.10}'.format(s2))
# => 嬉しやと 二度さめて

{} の中で : の後に .数字 という形で書くと文字数を指定することができます。この例では文字を最大 10 文字になるように切り詰めています。

この {:.10} という形は元々、小数点数の小数点以下の桁数を指定するためのものだと思うのですが、数字以外の場合にも動作して、数字以外の場合は文字数を指定できるものになっているようです。

公式のドキュメントでは次のように説明されています。

The precision is a decimal number indicating how many digits should be displayed after the decimal point for a floating point value formatted with 'f' and 'F', or before and after the decimal point for a floating point value formatted with 'g' or 'G'. For non-number types the field indicates the maximum field size - in other words, how many characters will be used from the field content. The precision is not allowed for integer values.

6.1. string — Common string operations — Python documentation

以上です。


参考

How to truncate a string using str.format in Python? - Stack Overflow

2017/09/19

サンプルコード:フィボナッチ数を対数時間で求める

今回はフィボナッチ数を対数時間で求めるプログラムについてです。



Wikipedia より)


フィボナッチ数とは、次の漸化式で表せる数列です。

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) (n >= 2)

実際に各値を求めると次のような数値になります。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

Wikipedia には次のような一文があります。

フィボナッチ数(フィボナッチすう、英: Fibonacci number)は、イタリアの数学者レオナルド・フィボナッチ(ピサのレオナルド)にちなんで名付けられた数である。

フィボナッチ数 - Wikipedia
Fibonacci - Wikipedia

なんでも、 12 世紀頃の数学者であり「フィボナッチ」(ボナッチの息子)と(後に)呼ばれた、イタリアのレオナルドさん発案だそうです。

余談ですが、「レオナルド」はイタリアあたりの歴史にやたらに登場しますね。日本でいう「ごんべえ」的な感じでしょうか。

それはさておき。

フィボナッチ数の値は解析的に求めることもできますが、プログラミングの課題としては、再帰アルゴリズムあるいは動的計画法を使って解くことが求められることが多いようです。

まずはロジックが最もシンプルな線形時間でのアプローチを先に見てみましょう。


線形時間での求解


単純なループを使った動的計画法アプローチでは、線形時間 O(n) で解くことができます。



これは直感的な求め方ですね。続いて対数時間で求めるアプローチです。


対数時間での求解


フィボナッチ数は直感に反し、対数時間 O(log(n)) で求めることができます。

ポイントは次のとおりです。

  1. 行列で考えた場合、フィボナッチ数の漸化式は F(n) = P * F(n - 1)(ただし P((1, 1), (1, 0) という行列)で表せる。
  2. 結果、 F(n)F(n) = P^n * (1, 0)^T で求めることができる。
  3. ミソは P^n の計算で、これは単純に Pn 回積を繰り返して求めることもできるが、例えば n = 2^m となる場合(例えば n = 64 なら m = 6 )にかぎると、 P^64 = (P^32)^2 = ((P^16)^2)^2 = (((P^8)^2)^2)^2 = ((((P^4)^2)^2)^2)^2 = (((((P^2)^2)^2)^2)^2)^2 ということで、 2 乗を 6 回繰り返す形でも求めることができる(つまり指数時間で求められる)。これは 63 回積を繰り返すより断然早い。
  4. n = 2^m とならない n については、 n = 2^m1 + 2^m2 + 2^m3 + ... という形に分解することで(要は 2 進数表現にすることによって)各部を 2^m の形に表すことができる。この事実を利用すると、 P^n = P^(2^m1 + 2^m2 + 2^m3 + ...) = P^(2^m1) * P^(2^m2) * P^(2^m3) * ... で求められる。

詳細のロジックに興味のある方は、次のページの解説がとても丁寧でわかりやすいのでそちらをご覧になってみてください。

The Nth Fibonacci Number in O(log N)

実際のサンプルコードは次のとおりです。



コード上のポイントは次のとおりです。

  • フィボナッチ数を求める関数は get_fibonacci() で、それ以外の関数はすべてヘルパー関数です。
  • if __name__ == '__main__': 以下の部分はすべてテストコードです。
  • 上の 4. の 2 の乗数への分解を行う関数は get_2exponent_series() です。
  • 上の 3. の部分を担う関数は pow_matrix() です。
  • 行列の積の計算は multiply_matrix() で行っています。単純な 2 x 2 行列の計算なので、ライブラリは使わずそのまま計算しています。間違いやすいのでケアレスミスに注意が必要です。
  • やや本筋から外れる、キャッシングと畳み込みの計算には標準ライブラリ functoolslru_cache()reduce() を使っています。

以前の「ハノイの塔」のサンプルと同じく、ホワイトボードコーディングの本の中に出てきたので個人的なエクササイズを兼ねて書いてみました。

この話題(「フィボナッチ数を対数時間で求める方法」)については学生時代にちらっと学んだことがある気がするのですが、その詳細は完全に忘れてしまっていたので、今回改めて調べて「おぉ、これはすごい!」ととても感動しました(笑)。

再帰や動的計画法は「問題の本質をいかにシンプルな形で捉え抽出することができるか」がポイントで、このあたりは汎用の問題解決能力とも直結する気がします。私はこのあたりは特段苦手というわけではありませんが、「ものすごく得意」「閃きまくって仕方がない!」というわけでもないので、こういう問題解決が得意な人を見るとうらやましくなります。

2017/09/06

ライブラリ: watchdog

Python のライブラリである watchdog をご紹介してみます。

watchdog : Python Package Index

今回は次の組み合わせで動作確認をしています。

python 3.6.1 
watchmedo 0.8.3 

watchdog とは


watchdog とはファイルの変更を監視して、ファイルが変更されたら何らかの処理を行う自動化ツール作成のためのライブラリです。

watchdog を import してスクリプトを書く方法と、 watchmedo というコマンドを利用する方法の 2 つの利用方法が用意されています。

私はライトな使い方しかしておらず「コマンドを使用する方法」だけで事足りてしまっているので、今回は後者のみの紹介とさせていただきます。スクリプトを書く方法に興味のある方は公式のドキュメントをご覧になってみてください。

Watchdog — watchdog documentation

インストール


pip でそのままインストールしましょう。

$ pip install watchdog

基本的な使い方


上述のとおり、今回は watchdog が提供するコマンド watchmedo を使った方法をご紹介します。

といっても使い方はシンプルで、 watchmedo コマンドに監視対象と実行したいコマンドをオプションでただ渡すだけで OK です。

以下は私が PHP のプロジェクトで PHPUnit のテストを書いている最中に使ったコマンドです。 PHPUnit のテストファイルが更新されたら(私がファイルを保存したら)自動で対象のテストファイルに対してテストを実行するというものです。

watchmedo shell-command \
--patterns="*Test.php" \
--ignore-directories \
--recursive \
--command='./vendor/bin/phpunit ${watch_src_path} && echo ""'

watchmedo にサブコマンド shell-command を指定して実行しています。使用しているオプションについて以下にかんたんに説明します。

  • --patterns 対象のファイル名のパターン。
  • --ingore-directories ディレクトリを無視する場合につける。
  • --recursive 再帰的に子孫ディレクトリをウォッチする場合につける。
  • --command ファイルの変更が検出されたときに実行したいコマンド。

私がいま確認したところ、公式のドキュメントには詳しい記述がありませんが、 --command オプションで指定するコマンドの中では以下のパラメータを利用することができます。

${watch_src_path} 変更されたファイルのパス
${watch_dest_path} ファイル移動が発生するイベントにおいて移動先のファイルのパス
${watch_event_type} イベントのタイプ
${watch_object} ファイルかディレクトリか

以上です。

このあたりについては Node.js まわりでの開発が最近活発ですが Node.js は流行り廃りのサイクルが他の言語に比べて短いような気もするので、この Python の watchdog など短期間では廃りにくい方法をひとつ知っておくと便利だと思います。

参考

Watchdog — watchdog documentation
GitHub - gorakhargosh/watchdog: Python library and shell utilities to monitor filesystem events.