Lispでバケツソート

日経ソフトウェアの2014年6月号で、バケツソートが紹介されていました。
興味深かったので、Lispで実装してみました。

ソース

(defun backet-sort (v backet-count)
  "バケツソート"
  (let ((backet (array-to-backet v backet-count)))
    (backet-to-array backet (length v))))

(defun array-to-backet (arr backet-count)
  "配列からバケツを構成する"
  (let ((backet (make-array backet-count :initial-element 0)))
    (dotimes (i (length arr) backet)
      (let ((n (aref arr i)))
        (setf (aref backet n) (1+ (aref backet n)))))))

(defun backet-to-array (backet array-length)
  "バケツからソート済みの配列を構成する"
  (let ((arr (make-array array-length)))
    (loop with arr-index = 0
          for i below (length backet)
          when (< 0 (aref backet i))
          do (loop repeat (aref backet i)
                   do (setf (aref arr arr-index) i)
                      (setq arr-index (1+ arr-index))))
    arr))


(defun main ()
  "動作確認のための関数"
  (let ((l (loop with state = (make-random-state t)
                 repeat 10
                 collect (random 10 state))))
    (print (sort (make-array (length l) :initial-contents l) #'<))
    (print (backet-sort (make-array (length l) :initial-contents l) 10))))

(main)

なんとなく汚い感じがするのは、きっと自分の腕が未熟だからでしょう。

JavaScriptでは"false"はtrueとして扱われる

タイトルだけでは「そんなバカな」と思われるかもしれませんが、要はtruthy/falsyの話です。

JavaScriptでのTruthy/Falsy
仕様は、ECMAScript Language Specification - 9.2 ToBooleanにあります。これによれば、falseとして扱われるのは次の6つです。

1. undefined
2. null
3. false
4. 0
5. NaN
6. "" (空文字列)

Boolean関数を使って確認してみました。

"false"がtrueとして扱われることが確認できました。

問題になるケース

問題になるケースとしては、サーバーサイドの言語からJavaScriptへ、type="hidden"のinputのvalueへfalseをセットする場合が考えられます。サーバーでセットされた値を使用して、次のようなif文を書くと問題が発生します。

// <input id="someElement" type="hidden" value="false" />のとき
if (document.getElementById('someElement').value) {
    // このブロックが実行される
    ...
}

回避するには、明示的に"true"と比較するのがいいでしょう。

// <input id="someElement" type="hidden" value="false" />のとき
if ("true" === document.getElementById('someElement').value) {
    // このブロックは実行されない
    ...
}

JavaScriptの型は独特のゆるさがあるので、ついついチェックがあまくなりがちです。しかし、今自分がどんな型を扱おうとしているのか把握していないと、思わぬところでハマってしまいます。という記事でした。

おまけ
「Boolean型に変換するAPIはないのか」と思って調べてみましたが、次のような結果に。

参考
ECMAScript Language Specification

unittest.mockの簡単な紹介

単体テストに欠かせないツールのひとつに、モックがあります。
Pythonにも3.3からモックモジュールが追加されました。
unittest.mockといいます。今回はこのモジュールの簡単な使い方を紹介します。

モックが必要になる場面として、システム日付の取得があります。

例えば、当日が閏日かどうか判定する関数を考えてみましょう。

なにも考えずに関数を実装すると、次のようになると思います。

def is_leap():
    d = datetime.date.today()
    if 2 == d.month and 29 == d.day:
        print(str(d) + ' is LEAP')
        return True
    else:
        print(str(d) + ' is NOT LEAP')
        return False

このままではOSの時計を設定しないと試験ができないので、
日付をパラメータとして渡すようにします。

def is_leap(d):
    if 2 == d.month and 29 == d.day:
        print(str(d) + ' is LEAP')
        return True
    else:
        print(str(d) + ' is NOT LEAP')
        return False

日付を注入できるようにしたことで、テストしやすくなりました。
例えば、このようにします。

assert True == is_leap(datetime.date(2012, 2, 29))
assert False == is_leap(datetime.date(2012, 3, 1))

unittest.mockを使うと、次のような感じになります。

d = unittest.mock.MagicMock()
d.month = 2
d.day = 29
assert True == is_leap(d)

モックを使わないほうが単純です。こういう場合はdateオブジェクトを使ったほうがいいでしょう。
さて、現実には全てのコードを自由に変更できるとは限りません。
たとえそんな場合でも、unittest.mock.patchを呼ぶことで、対応できる場合があります。
is_leap関数を修正せずに次のようにします。

with unittest.mock.patch('datetime.date') as dt:
    dt.today().month = 2
    dt.today().day = 29
    assert True == is_leap()

datetime.date.today()メソッドが返すオブジェクトをモックオブジェクトと置き換え、
属性を設定することでテストをパスしています。
確かにこの方法でも試験はできますが、日付をパラメータ化するほうがベターだと思います。

他にも、unittest.mockにはメソッドの呼び出しを記録する機能もあります。
詳しいことはオフィシャルのドキュメントを参照してください。

参考：

26.4. unittest.mock - mock object library

26.5. unittest.mock - getting started

xyzzyでブックマーク機能

Emacsのブックマーク機能で紹介したEmacsのブックマーク機能が便利だったので、xyzzyでも使いたくなりました。
Lispの勉強も兼ねて、自分で実装してみました。
プログラムは記事の最後に載せます。

機能
実装済みの機能は以下のとおりです。

• 現在表示しているバッファをブックマークとして登録する
• ブックマークの一覧を表示する
• ブックマークの一覧からファイルを開く
• ブックマークを削除する

使用方法

まず、プログラムを読み込みます。専用のパッケージを定義したので、合わせてuse-packageします。

(require "bookmark")
(use-package "bookmark")

次に、キーバインドの設定をします。今のところ公開している関数は次の2つです。

1. bookmark-add-current-buffer: 表示しているバッファをブックマークする
2. bookmark-list-bookmarks: ブックマークの一覧を表示する

(global-set-key '(#\C-c #\a #\b) 'bookmark-add-current-buffer)
(global-set-key '(#\C-c #\l #\b) 'bookmark-list-bookmarks)

bookmark-add-current-bufferを呼ぶと、現在のバッファをブックマークします。その際、ブックマーク名を入力できます。

bookmark-list-bookmarksを呼ぶと、ブックマーク一覧を表示します。一覧からファイルの表示と、ブックマークの削除ができます。ブックマークしたファイルの表示は[f]キーを押下し、ブックマークの削除は[d]キーです。

ブックマーク一覧を実装するときは、xyzzy付属のbuf-menu.lが参考になりました。

よろしければ使ってみてください。

Emacs: 検索/置換チュートリアル

Google+で流れてきたEmacsのチュートリアルを日本語に訳してみました。

Emacs:　検索/置換チュートリアル

このページでは、Emacsの検索/置換機能を紹介します。

大文字と小文字を区別するかどうかについて紹介します。

正規表現にマッチした文字列を大文字や小文字に変換する方法について紹介します。

検索/置換コマンド

最も便利な検索/置換コマンドについて紹介します。

これらは、メニューのEdit > Replaceにあります。

コマンド名	キーバインド	対象	目的
query-replace	M-%	有効なリージョン カーソルから後方	対話的な検索/置換
query-replace-regexp	C-M-%	有効なリージョン カーソルから後方	正規表現による対話的な検索/置換
dired-do-query-replace-regexp	diredでQ	マークしたファイル	複数ファイルに対する対話的な検索/置換

例：query-replaceを呼び、検索文字列と置換文字列を入力します。

コマンドが確認を求めた時の一般的なコマンドは以下のとおりです。

• y - 置換を実行する
• n - スキップする
• ! - これ以降確認なしで置換する
• C-g - キャンセル(置換を元に戻すにはundoを呼ぶ)

dired-do-query-replace-regexpについては、Interactively Find/Replace String Patterns on Multiple Filesを参照してください。

一括置換
Emacsにはreplace-stringとreplace-regexpコマンドもあります。
それらはquery-replaceとquery-replace-regexpの対話的でないバージョンです。
一度の実行で確認せずにすべて置換します。
練習段階では、これらはさほど便利ではありません。
対話的なバージョンを使用し、!を入力すれば一括で置換できます。

デフォルトの大小文字区別: 自動
デフォルトでは、検索文字に大文字を含むとき、自動的に大小文字を区別して検索します。そうでなければ、大証文字を区別せずに検索します。
デフォルトでは、置換後の文字列の大小文字検索にマッチした文字列に依存します。
例えば、検索文字列が「here」で置換文字列が「dragon」のときについて考えます。
Emacsは「here」「Here」「HERE」のいずれかを検索します。
そして、「here」を「dragon」で置換し、「Here」を「Dragon」で置換し、「HERE」を「DRAGON」で置換します。

入力したとおりの文字列で置換したいときは、case-replace変数へnilをセットします。set-variableを使用します。

自動大小文字区別のON/OFF
検索と置換の両方で入力した通りの大小文字を使用したいときはtoggle-case-fold-searchを呼ぶか、メニューのOptions > Case-Insensitive Searchを使用します。
キーやエイリアスを割り当てることもできます。(Emacs: How to Define Keys) (Emacs: Defining Alias to Increase Productivity)

正規表現にマッチした文字列の大小文字を強制的に置換する
検索に正規表現を使用しており、大文字や小文字に置換したいとき、「\,(upcase \1)」や「\,(downcase \1)」を使用できます。
例えば、次のようなテキストについて考えます。

<p>once upon a time ...</p>
<p>there is a dragon who lived in ...</p>
<p>princess tana is still witing ...</p> 

すべてのパラグラフを大文字で開始したいとき、<p>に続く一文字をキャプチャする「<p>\{[a-z]\}」のようなパターンを使います。

キャプチャした文字を大文字に置換するために、置換文字列に「<p>\,(upcase \1)」を使用します。「\,」は続く文字列がlisp式であることを示します。「(upcase \1)」はlisp式です。「upcase」はlisp関数で、「\1」は1番目のキャプチャ文字列です。

「\,」を使用したより複雑な置換については、Regex Replace with a Function in Emacs Lispを参照してください。

参考
Emacs: Find/Replace Tutorial

シェルスクリプト初心者の私がまず覚えたこと9つ

今年の4月にシェルスクリプトを書く機会がありました。今までシェルを使った経験は多少あったものの、シェルスクリプトを書くのは初めてでした。シェルスクリプトを書くにあたり、まず抑えたことを紹介します。

1. 1行目のおまじない
2. 変数の使い方
3. 関数の使い方
4. 制御文
5. バッククォート
6. 終了ステータス
7. 設定ファイル
8. 文字列操作
9. 文字列のエスケープ

それぞれについて以下に記載します。

GZIP圧縮に対応したHTTPクライアントを作る

前回の記事で予告したとおり、今回はC#でGZIP圧縮に対応したHTTPクライアントを作ります。
ポイントは3つあります。

1. GZipStreamを使って入力データを圧縮する
2. HttpClientHandlerのAutomaticDecompressionプロパティを設定する
3. HTTPリクエストヘッダのContent-Encodingをgzipに設定する

GZipStreamを使って入力データを圧縮する

圧縮用にMemoryStreamをインスタンス化し、GZipStreamでラップします。

usingをネストしているのはGZipStreamをCloseするタイミングで圧縮が実行されるからです。

byte[] data = null;

using (var memory = new MemoryStream()) {
  using (var gzip = new GZipStream(memory, CompressionMode.Compress)) {
    int input = 0;
    byte[] buffer = new byte[1];

    while (-1 != (input = Console.Read())) {
      buffer[0] = Convert.ToByte(input);
      gzip.Write(buffer, 0, buffer.Length);
    }
  }
  data = memory.ToArray();
}

HttpClientHandlerのAutomaticDecompressionプロパティを設定する

リクエストボディの圧縮は実装する必要がありますが、レスポンスの解凍は.NET Frameworkが対応しています。

var clientHandler = new HttpClientHandler();
clientHandler.AutomaticDecompression = DecompressionMethods.Deflate | DecompressionMethods.GZip;

HTTPリクエストヘッダのContent-Encodingをgzipに設定する

コンテンツがgzip圧縮されていることを示すため、Content-Encodingをgzipに設定します。

using(var client = new HttpClient(clientHandler))
using(var content = new ByteArrayContent(data))
{
  content.Headers.ContentEncoding.Add("gzip");
  using(var message = client.PostAsync(url, content).Result)
  {
    Console.WriteLine(message.Content.ReadAsStringAsync().Result);
  }
}

一般的に、HTTPリクエストが圧縮を必要とするほど大きくなることはありません。

全ての画面データを毎回やりとりするような設計であれば、効果があるかもしれません。

プログラム全体を以下に記載します。