2015-08-18

swiftで外部コマンド実行

頭に#!/usr/bin/swiftって書いておくと

chmod a+x hoge.swift
./hoge.swift #swift hoge.swiftでも起動できる

って感じでスクリプトみたいに起動できることを知ったので、勉強がてら手元にあるperl スクリプトをswift翻訳してた。その際のメモ。

perlの

my $status = system "ls hoge/"  #ret-code
my $ret = `ls hoge/ `           #output

こういうのをswiftでどう書けばいいんだっけ？と思って調べた。

OSXアプリはほとんど書いたことないので、使ったことなかったけどNSTaskでできるみたい。 task.standardOutput (NSPipe)で外部コマンドの出力を受け取ることができる。カレントディレクトリを指定して実行したい場合は、task.currentDirectoryPathにセットしておけばいい。

func stdOutOfCommand(cmd: String, arguments args: [String], currentDirPath currentDir: String? = nil) -> String {
    var task: NSTask = NSTask()
    task.launchPath = cmd
    task.arguments = args
    if currentDir != nil { task.currentDirectoryPath = currentDir! }
    let pipe: NSPipe = NSPipe()
    task.standardOutput = pipe
    task.launch()
    let out: NSData = pipe.fileHandleForReading.readDataToEndOfFile()
    let outStr: String? = NSString(data: out, encoding: NSUTF8StringEncoding) as? String
    return outStr == nil ? "" : outStr!
}

var ret = stdOutOfCommand("/bin/ls", arguments: ["hoge/"])

対話(入力を要求する)形式の場合は、waitForDataInBackgroundAndNotify()でバックグラウンド待機と通知するようにして、 NSNotificationCenterでNSFileHandleDataAvailableNotificationを受け取るようにする必要がある。

taskの終了まで待ちたい場合はtask.waitUntilExit()で待つ。終了ステータスはtask.terminationStatusで取得できる。

下の例だと、入力の制御はNSFileHandle.fileHandleWithStandardInput()を使っている。

flushしてなかったり、addObserverのobjectをinPipeにしててはまった...orz

func scriptWithCmd(cmd: String, arguments args: [String], currentDirPath currentDir: String? = nil) -> Int32 {
    //set task
    let input: NSFileHandle = NSFileHandle.fileHandleWithStandardInput()
    let inPipe: NSPipe = NSPipe()
    let outPipe: NSPipe = NSPipe()
    let task: NSTask = NSTask()
    task.launchPath = cmd
    task.arguments = args
    if currentDir != nil { task.currentDirectoryPath = currentDir! }
    task.standardOutput = outPipe
    task.standardInput = inPipe
    task.launch()
    
    //notification
    input.waitForDataInBackgroundAndNotify()
    outPipe.fileHandleForReading.waitForDataInBackgroundAndNotify()
    NSNotificationCenter.defaultCenter().addObserverForName(NSFileHandleDataAvailableNotification, object: input, queue: nil,
        usingBlock : { (notification: NSNotification!) in
            let inData: NSData = input.availableData
            if inData.length > 0 {
                inPipe.fileHandleForWriting.writeData(inData)
                input.waitForDataInBackgroundAndNotify()
            } else {
                inPipe.fileHandleForWriting.closeFile()
            }
        }
    )
    NSNotificationCenter.defaultCenter().addObserverForName(NSFileHandleDataAvailableNotification, object: outPipe.fileHandleForReading, queue: nil,
        usingBlock:  { (notification: NSNotification!) in
            let outData: NSData = outPipe.fileHandleForReading.availableData
            let outStr: NSString = NSString(data: outData, encoding: NSUTF8StringEncoding)!
            print(outStr)
            fflush(__stdoutp)
            outPipe.fileHandleForReading.waitForDataInBackgroundAndNotify()
        }
    )
    
    task.waitUntilExit()
    return task.terminationStatus
}

他の言語で外部コマンド呼び出し簡易メモ

以前少し調べてたやつ

Perl

exec()もあるけど戻ってこないのでsystem()を使う。バッククォート便利.

my $status = system "ls hoge/"  #ret-code
my $ret = `ls hoge/ `           #output

C

以前perlだと遅すぎるので、C/C++でやろうとして色々やっていた時のメモ

system()

#include <stdlib.h>
    int ret = system("ls hoge/");

popen()/pclose()

POSIXだとpopen/pcloseとか使える.

#include <stdio.h>
#include <stdlib.h>
#include <err.h>
#define BUF 256
int main (void) {
    FILE *fp;
    char buf[BUF];
    char *cmd = "/bin/ls hoge/";
    
    if ((fp=popen(cmd,"r")) == NULL) {
        err(EXIT_FAILURE, "%s", cmd);
    }
    while(fgets(buf, BUF, fp) != NULL) {
        fputs(buf, stdout);
    }
    pclose(fp);

    return 0;
}

exec*()

popenだと入出力が同時にできないので、pipe(), dup(), fork(), exec*()あたりを使う必要がある。

参考

C++

PStreams(POSIX)が使えそう

Java

ProcessBuilderを使うみたいだが、シェルが直接解釈するコマンドは直接は実行できない？

参考

2015-04-09

Effective Objective-C 2.0 第４章(プロトコルとカテゴリ)

Objective-C

項目23 オブジェクト間通信には、DelegateとDataSourceプロトコルを使う

@class myClass;
@protocol myDelegate <NSObject>
@optional
- (void)optionalMethod1:(myClass*)test;
- (void)optionalMethod2:(myClass*)test;
@end
@interface myClass : NSObject
- (void)doSomethingWithDelegate:(id<myDelegate>)delegate;
@end

デリゲートを持つクラスのプロパティは通常所有関係にならないのでweak属性となることが多い
optionalなデリゲートメソッドが頻繁に呼ばれる場合は、delegateのセッターでメソッドが実装されているかをビットフィールドでキャッシュしとくといい

#import "myClass.h"
@interface myClass () {
    struct {
        unsigned int optionalMethod1 : 1;
        unsigned int optionalMethod2 : 1;
    } _delegateFlags;
}
@property (nonatomic, weak) id<myDelegate> delegate;
@end
@implementation myClass
- (void)setDelegate:(id<myDelegate>)delegate {
    _delegate = delegate;
    _delegateFlags.optionalMethod1 = [delegate respondsToSelector:@selector(optionalMethod1:)];
    _delegateFlags.optionalMethod2 = [delegate respondsToSelector:@selector(optionalMethod2:)];
}
- (void)doSomethingWithDelegate:(id<myDelegate>)delegate {
    self.delegate = delegate;
    dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{
        //dosomething...
        if (_delegateFlags.optionalMethod1) {
            [_delegate optionalMethod1:self];
        }
    });
}
@end

デリゲートメソッドの引数には代わりに処理しているインスタンスを渡すようにしておくと、どのインスタンスからの通知かを判断できる

- (void)optionalMethod1:(myClass *)test {
    if (test == self.instance1) {
        NSLog(@"optionalMethod1:instance1");
    } else if (test == self.instance2) {
        NSLog(@"optionalMethod1:instance2");
    }
}

項目24 カテゴリを使ってクラスの実装を管理できるサイズに分割せよ

カテゴリでクラスを分割実装できる。
非公開のメソッドを分割したカテゴリで使いたい場合は、Privateというカテゴリを作ってそのヘッダをインポートする。そのヘッダは非公開とする。

項目25 サードパーティクラスに追加するカテゴリで使う名前には必ずプレフィックスを付ける

自分のものでないクラスに追加するカテゴリの名前、カテゴリメソッドにはプレフィックスをつけようず

同じ名前のメソッドが追加されていると、どの実装が呼び出されるか分からなくなるから、無意識にオーバーライドしないようにするためにプレフィックスを付ける。

項目26 カテゴリではプロパティを使わないようにする

カプセル化されたデータのためのプロパティ宣言は、全てメインインターフェース定義に集める
カテゴリではプロパティ宣言ではなくメソッドを使う(クラス拡張(無名)カテゴリを除く)

カテゴリでプロパティ宣言をしても、インスタンス変数の自動合成できないので、@dynamicやassociated Objectを使う必要がある。

基本的にはメインインターフェース定義、無名カテゴリにプロパティ宣言を集めた方が良い。

項目27 実装の詳細を隠すためにクラス延長カテゴリを活用せよ

非公開メソッドのドキュメンテーションに使える
実装でC++クラスを使う場合便利(ヘッダにC++の要素があれば、そのヘッダをインポートするファイルはObjective-C++として扱わないといけない)
非公開のプロパティ、プロトコル準拠は無名カテゴリで宣言すると良い。ゲッタだけ公開したい場合は、ヘッダでreadonlyにしておいて無名カテゴリでreadwriteにすることもできる。

クラス延長(無名)カテゴリ

通常のカテゴリとは異なり、拡張しようとしているクラスの実装ファイルで定義しなければならない
通常どおり@propertyでインスタンス変数の自動合成が行われる
ヘッダでreadonlyになっているプロパティをreadwriteにできる

項目28 プロトコルを使って無名オブジェクトを提供せよ

id<xxx>ってやつです。具体的なクラス名(型)を隠せる。そんだけ。

2015-03-31

プログラミングHaskell第６章(再帰関数)まとめ

Haskell

再帰関数定義のための５段階の工程 ${}$

1:型を定義する

pow :: Int a => a -> a -> a

2:場合分けをする

数値なら(0, n), リストなら([], x:xs)などで場合分けする

pow a n | (n == 0) = 
        | (n > 0)  =

3:簡単な方を定義する

たいていの場合、基底部の方が簡単

pow a n | (n == 0) = 1
        | (n > 0)  =

4:複雑な方を定義する

たいていの場合、再帰部の方が複雑

pow a n | (n == 0) = 1
        | (n > 0)  = a * pow (n-1)

5:一般化し簡単にする

必要なら、任意の型に変えたり、使われていない変数をワイルドカードに置き換えたり, 式をまとめたりする。

pow :: (Integral b, Num a) => a -> b -> a
pow a n | (n == 0) = 1
        | (n > 0)  = a * pow a (n-1)

もう少し工夫すると、

\[ a^n = \begin{cases} 1 & (n = 0)\\ (a\cdot a)^{\frac{n}{2}} & (\text{if }n\text{ is even.})\\ a\cdot a^{n-1} & (\text{if }n\text{ is odd.}) \end{cases} \]

$O (\log n): n$は負でない整数

pow :: (Integral b, Num a) => a -> b -> a
pow a n | (n == 0)          = 1
        | (n > 0 && even n) = pow (a*a) (n `div` 2)
        | (n > 0 && odd n)  = a * pow a (n-1)

多重再帰

関数自身が自分自身を複数参照する再帰

$ F_0 = 0 \\ F_1 = 1 \\ F_{n+2} = F_n + F_{n+1} \text{ }(n\geq 0) $

fibonacci :: Int -> Int
fibonacci n | n == 0 = 0
            | n == 1 = 1
            | n >= 2 = fibonacci (n-2) + fibonacci (n-1)

相互再帰

二つ以上の関数が互いを参照し合う再帰

evens :: [a] -> [a]
evens [] = []
evens (x:xs) = x : odds xs
odds :: [a] -> [a]
odds [] = []
odds (_:xs) = evens xs

2015-03-29

ソート、整列(sorting)

Algorithm Java Haskell

リポジトリ

Arrays.sortに習って、a[fromIndex, toIndex)がソートされるようにしてみる。また、javaにはswap()がないので適当に実装しておく。

public static final void xxxSort(T a[], int fromIndex, int toIndex) { ... }
public static final int[] swap(int[] x, int i, int j){
    int tmp = x[i]; x[i] = x[j]; x[j] = tmp; return x;
}

交換ソート(Exchange sorts)

バブルソート, 基本交換法, 隣接交換法, 交換法(bubble sort)

http://en.wikipedia.org/wiki/Bubble_sort

隣接要素交換を繰り返してソート。特に最適化していないナイーブな実装だと安定な内部ソート。

比較回数 ${T=\sum_{k=1}^{n-1}k = \frac{n(n-1)}{2} }$ 回

交換回数は最悪 ${T}$ 回、平均 ${\frac{1}{2}T = \frac{n(n-1)}{4}}$ 回

${ O(n^2)}$

右のほうに小さな数がある場合に交換回数が多くなってしまう。

bsort :: Ord a => [a] -> [a]
bsort []  = []
bsort [x] = [x]
bsort xs  = bsort (init xs') ++ [last xs']
      where xs' = sweep xs
            sweep [y] = [y]
            sweep (y1:y2:ys) | (y2 < y1) = y2 : sweep (y1:ys)
                             | otherwise = y1 : sweep (y2:ys)

mergeCountの検証用に戻り値は交換回数になっている。

public static final int bubbleSort(int a[], int fromIndex, int toIndex){
    int swapCount = 0;
    int n = toIndex - fromIndex;
    for (int i = 0; i < n; ++i)
        for (int j = fromIndex+1; j < toIndex-i; ++j)
            if (a[j-1] > a[j]) { swap(a, j-1, j); ++swapCount; }
    return swapCount;
}

シェーカーソート(cocktail sort, bidirectional bubble sort, cocktail shaker sort, shaker sort, ripple sort, shuffle sort, shuttle sort)

http://en.wikipedia.org/wiki/Cocktail_sort

バブルソートのスキャン方向を双方向にして、右に小さい値がある場合に遅いバブルソートの欠点を改良したもの。

安定な内部ソート。 ${O(n^2)}$

さらに端に連続して交換していない要素があれば、その分スキャン範囲を狭められる。ほとんど整列している系列に対して高速。

奇偶転置ソート(odd-even sort)

http://en.wikipedia.org/wiki/Odd%E2%80%93even_sort

バブルソートの改良版の一つ。はじめに、 ${a_0 \text{と} a_1, a_2\text{と}a_3, a_4\text{と}a_{5}\cdots }$ を(必要なら)交換し、次に、 ${a_1 \text{と} a_2, a_3\text{と}a_4, a_5\text{と}a_6\cdots }$ を(必要なら)交換する。これを交換が発生しなくなるまで繰り返す。

安定な内部ソート ${ O(n^2)}$

２要素の交換は独立に行うことができるので、並列化できる。

public static final void oddEvenSort(int a[], int fromIndex, int toIndex) {
    boolean swapped = true;
    while (swapped) {
        swapped = false;
        for (int i = fromIndex; i < toIndex-1; i+=2) //odd-even
            if (a[i] > a[i+1]) { swap(a, i, i+1); swapped = true; }
        for (int i = fromIndex+1; i < toIndex-1; i+=2) //even-odd
            if (a[i] > a[i+1]) { swap(a, i, i+1); swapped = true; }
    }
}

櫛ソート(comb sort)

http://en.wikipedia.org/wiki/Comb_sort

バブルソートの改良版。隣同士の交換ではなく、間隔(gap)が ${h}$ あいたものと交換する。 ${h}$ をだんだん小さくしていって、交換が発生しなくなるまで繰り返す。

非安定な内部ソート。最悪 ${O(n^2)}$ , 平均的にはだいたい ${O(n \log n)}$ ぐらいになる。

${h=n}$
かつ交換が行われなくなるまで以下を繰り返す。
- ${ h\leftarrow \max \{ \lfloor \frac{h}{1.3} \rfloor , 1 \} }$
- ${ a_{i} > a_{i+h} }$ なら ${ a_{i} }$ と ${ a_{i+h} }$ を交換する

${ h=9,10 }$ となったとき、強制的に ${ h=11 }$ とすることで高速化したアルゴリズムを、Comb sort 11と呼ぶ。

public static final void combSort(int a[], int fromIndex, int toIndex) {
    boolean swapped = true;
    int h = fromIndex - toIndex;
    while (h > 1 || swapped) {
        swapped = false;
        h = Math.max(h*10/13, 1);
        for (int i = fromIndex;i+h < toIndex;++i)
            if (a[i] > a[i+h]) { swap(a, i, i+h); swapped = true; }
    }
}

クイックソート(quicksort)

http://en.wikipedia.org/wiki/Quicksort

${O(n \log n)}$

適当にピボットを選択する
ピボットより小さい数を前方、大きい数を後方に移動させる（分割）
二分割された各々のデータを、それぞれソートする

非安定ソート。安定化も可能だが、マージソートのほうが速い場合が多い。 pivotにmedianを使うといい感じになる。

qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (pivot:xs) = qsort left ++ [pivot] ++ qsort right
      where left  = [l|l <- xs, l <= pivot]
            right = [r|r <- xs, r > pivot]

public static final void quickSort(int a[], int fromIndex, int toIndex) {
    if (fromIndex < toIndex) {
        int p = a[(fromIndex + toIndex) / 2];
        int l = fromIndex - 1, r = toIndex;
        while (true) {
            while (a[++l] < p);
            while (a[--r] > p);
            if (l >= r) break;
            swap(a, l, r);
        }
        quickSort(a, fromIndex, l);
        quickSort(a, r + 1, toIndex);
    }
}

ボゴソート(bogosort, stupid sort, slowsort, random sort, shotgun sort, monkey sort)

http://en.wikipedia.org/wiki/Bogosort

${O((n+1)!)}$

整列が完了するまで、猿に要素を交換させる。

配列でなく、コレクションならshuffle()を使えば良い。

private static final boolean isSorted(int a[], int fromIndex, int toIndex) {
    for (int i = fromIndex+1; i < toIndex; ++i) if (a[i-1] > a[i]) return false;
    return true;
}
public static final void bogoSort(int a[], int fromIndex, int toIndex) {
    int n = toIndex - fromIndex;
    Random r = new Random();
    while (isSorted(a, fromIndex, toIndex) == false)
        swap(a, fromIndex+r.nextInt(n), fromIndex+r.nextInt(n));
}

選択ソート(Selection sorts)

選択ソート(selection sort)

http://en.wikipedia.org/wiki/Selection_sort

バブルソートのように隣同士を交換するのではなく、未ソートの系列から最小の要素を選んで交換する。非安定な内部ソート。

比較回数は ${\sum_{k=1}^{n-1}k = \frac{n(n-1)}{2}}$ , １回のスキャンにつき交換は最大１回なので、計算量は ${O(n^{2})}$ 。

public static final void selectionSort(int a[], int fromIndex, int toIndex) {
    for (int i = fromIndex; i < toIndex; ++i) {
        int minIndex = i;
        for (int j = i+1; j < toIndex; ++j)
            if (a[minIndex] > a[j]) minIndex = j;
        swap(a, i, minIndex);
    }
}

ヒープソート(heapsort)

http://en.wikipedia.org/wiki/Heapsort

ヒープを構築して、最大値(ルート)を取り除いて並べる→ヒープ再構築→最大値を取り除いて並べるを繰り返す。データ自体以外に必要となる作業領域は固定だが、並列化できない。ランダムアクセスが必要になるので連結リストなどのソートには適さない。

${O(n \log n)}$ の非安定ソート。

２分ヒープ木(binary heap tree)

配列で実現できる。どの親 ${\geq }$ 子(または親 ${\leq}$ 子)を満たした２分木(binary tree)。兄弟同士の大小関係は任意なので、半順序木(partial ordered tree)とも呼ばれる。

${a[0]}$ をルートとした時、

${a[i]}$ の親は ${a\left[ \left\lfloor \frac{i-1}{2} \right\rfloor \right]}$
${a[i]}$ の左の子は ${a[2i+1]}$
${a[i]}$ の右の子は ${a[2i+2]}$

ヒープ化

ルート以外(左部分木と右部分木)がヒープ化されているとする。
ルートと子を比べて、ルートの方が値が大きい場合はルートを含めてヒープ化が完了している。
ルートの方が値が小さい場合は、大きい方の子と交換する。そのサブツリーに対して、交換が終了するまで繰り返せばヒープ化が完了する。

要素数を ${n}$ とすると、完全２分木の高さは ${\lfloor \log n\rfloor}$ なので、計算量は ${O(\log n)}$

配列のヒープ化

リーフのみからなるサブツリーは、ヒープ化されているとみなせる。そのリーフの親をルートとして、上記ヒープ化手順でヒープ化すると、ヒープ化されたサブツリーができる。これをボトムアップに行っていくことで配列全体をヒープ化できる。

private static final int parentIndexOf(int childIndex, int rootIndex) { return rootIndex + (childIndex-rootIndex-1)/2; }
private static final int leftChildIndexOf(int parentIndex, int rootIndex) { return rootIndex + 2*(parentIndex-rootIndex)+1; }
private static final int rightChildIndexOf(int parentIndex, int rootIndex) { return rootIndex + 2*(parentIndex-rootIndex)+2; }
private static final void heapify(int a[], int fromIndex, int toIndex, int rootIndex) {
    int left = leftChildIndexOf(fromIndex, rootIndex), right = rightChildIndexOf(fromIndex, rootIndex);
    int largest = (left < toIndex && a[left] > a[fromIndex]) ? left : fromIndex;
    if (right < toIndex && a[right] > a[largest]) largest = right;
    if (largest != fromIndex) {
        swap(a, fromIndex, largest);
        heapify(a, largest, toIndex, rootIndex);
    }
}
public static final void heapSort(int a[], int fromIndex, int toIndex) {
    for (int i = parentIndexOf(toIndex-1, fromIndex); i >= fromIndex; --i) heapify(a, i, toIndex, fromIndex); //build heap
    for (int i = toIndex-1; i >= fromIndex+1; --i) {
        swap(a, fromIndex, i);
        heapify(a, fromIndex, i, fromIndex);
    }
}

挿入ソート(insertion sorts)

挿入ソート(insertion sort)

http://en.wikipedia.org/wiki/Insertion_sort

１番目の要素をソート済みリストに加えて、続く要素をソート済みリストの適切な位置に挿入していく。安定な内部ソート。 ${ O(n^2) }$

ほとんどソート済みの系列に対して高速に動作する。データ構造が配列だと、挿入操作のコストが多いが、連結リストなど挿入コストが小さい構造だと効果的。

特に、ソート済みリストの挿入位置を２分探索する場合を２分挿入ソート(binary insertion sort)という。

isort :: Ord a => [a] -> [a]
isort [] = []
isort (x:xs) = insert x (isort xs)
      where insert x []                 = [x]
            insert x (y:ys) | (x <= y)  = x:y:ys
                            | otherwise = y:insert x ys

シェルソート(shell sort)

http://en.wikipedia.org/wiki/Shellsort

コムソートと同様に適当な間隔 ${h}$ をあけて取り出した系列に対して挿入ソートを行う。

非安定な内部ソート。最悪計算量は ${O(n\log^{2} n)}$ 。

${ h_{i+1}=3h_{i} +1 = 1,4,13,40,121, \cdots, \frac{3^{i} -1}{2}, \cdots}$ < ${n}$ を大きい方から採用すると ${O(n^{1.25})}$ となる。

分配整列(Distribution sorts)

バケットソート、ビンソート(bucket sort, bin sort)

http://en.wikipedia.org/wiki/Bucket_sort

アルファベットの数(扱う値の種類数) ${k}$ が少なく(有限で)、アルファベットの全順序関係を把握できているようなデータ系列に対して可能なソート。

各アルファベットに対応する ${k}$ 個のバケツを用意する(バケツは対応するアルファベットで整列しているものとする)
データ系列をスキャンして対応するバケツに入れる。
バケツに入れたものを順番に取り出して並べる。

データ数を ${n}$ としたとき、計算量は ${O(n + k)}$ の安定ソートとして実装できる。

ただし、メモリも普通に実装すると ${O(n+k)}$ 程度必要になる。

１つのバケツに複数のアルファベットを当てはめて(例えば、0-99, 100-200, 300-400, ...でバケツを分けて)、バケツの中でソートしても良い(ソートコストが小さい必要あり)。

特に、バケツを各アルファベットの(累積)度数表として実装したものを度数ソート、計数ソート、分布数えソート((distribution) counting sort)と呼ぶ。

//k = Integer.MAX_VALUEだと大きすぎるので、k = Character.MAX_VALUEとしている
public static final void countingSort(char a[], int fromIndex, int toIndex) {
    int[] freq = new int[Character.MAX_VALUE+1];
    int n = toIndex - fromIndex;
    char tmp[] = new char[n]; System.arraycopy(a, fromIndex, tmp, 0, n);
    for (int i = 0; i < n; ++i) freq[tmp[i]]++;
    for (int k = 1; k < freq.length; ++k) freq[k] += freq[k-1];
    for (int i = n-1; i >= 0; --i) a[fromIndex + (--freq[tmp[i]])] = tmp[i];
}

基数ソート(radix sort)

http://en.wikipedia.org/wiki/Radix_sort

データの種類が有限で、値の範囲が既知で、データが「3桁の整数」や「2文字のアルファベット」など決まった形式であることが適用条件。下位桁を安定ソートし、続いてその上位の桁を順次安定ソートしていく。

${K}$ 桁のデータ ${n}$ 個に対して、 ${O(n)}$ のソートアルゴリズムで基数ソートする場合、 ${O(Kn)}$ でソートできる。

スリープソート(sleep sort)

http://dis.4chan.org/read/prog/1295544154

一時期話題になったスリープソート(笑)。バケットソートのバケツをスリープ(タイマー)に置き換えたもの。

各要素の値に応じたタイマー(sleep)をセットする。
各タイマーを一斉に走らせる。
sleepが終了したものから対応する値を並べる。

特徴：

要素数だけスレッド作るとかやばい。一斉スタートも数が多いと多少の誤差が出るはず。
要素数が少なくても大きな値があると、長い時間スリープすることになる(n-bestが欲しい場合はあまり問題にはならないかも)。
スリープ値を適当な数で割ったり、対数をとったりしてうまくスケーリングすると良いが、スリープ値が小さすぎたり、スリープ値の差があまりない場合、誤差で正しく整列されないことがある。
マルチスレッドプログラミングの練習に使える？

public static final void sleepSort(char a[], int fromIndex, int toIndex) {
    final int n = toIndex - fromIndex;
    final List<Character> sorted = Collections.synchronizedList(new ArrayList<Character>(n*2));
    Thread t[] = new Thread[n];
    for (int i = 0; i < n; ++i) {
        final Character item = a[fromIndex+i];
        t[i] = new Thread() {
            final Character element = item;
            final long time = item*10; //差が小さすぎると順序が逆転してしまうので
            public void run() {
                try {
                    Thread.sleep(time);
                    sorted.add(element);
                } catch (InterruptedException e) {}
            }
        };
    }
    //start timer
    for (int i = 0; i < t.length; ++i) t[i].start();
    //wait
    try {
        for (int i = 0; i < t.length; ++i) t[i].join();
    } catch (InterruptedException e) {}
    //copy
    for (int i = 0; i < t.length; ++i) a[fromIndex+i] = sorted.get(i);
}

マージソート(Merge sorts)

マージソート(merge sort, mergesort)

http://en.wikipedia.org/wiki/Merge_sort

(ナイーブな)クイックソートと比べると、最悪計算量は少ないが、通常(ランダムデータの場合)はクイックソートのほうが速い。

左右に分割してそれぞれソートし、それらを(整列するように)マージしていく。マージは左右のソート済み部分列の左端から順に(昇順なら)小さい方を、等しければ左側優先で選んでいけば安定になる。

通常, 分割またはマージの際に ${O(n)}$ の外部記憶を要する。

分割していくと木の高さが ${O(\log n)}$ 、各深さのマージの計算量は ${O(n)}$ 、全体で ${O(n\log n)}$ 。

msort :: Ord a => [a] -> [a]
msort []  = []
msort [x] = [x]
msort xs  = merge (msort left) (msort right)
      where (left, right) = splitAt ((length xs) `div` 2) xs
            merge [] ys                     = ys
            merge xs []                     = xs
            merge (x:xs) (y:ys) | (x <= y)  = (x:merge xs (y:ys))
                                | otherwise = (y:merge (x:xs) ys)

ところで、 ${ a_0, a_1, \cdots, a_{n-1}}$ のbubbleSortによる交換回数 ${T}$ は、

${ T=\sum_{i=0}^{n-1} f(i) }$ となる

ただし、$f(i)=\left | \{ j|j < i, b_{j} > a_{i} \} \right |$,

${b_0, b_1, \cdots, b_{n-1}}$ はソート済みの要素とする。

なので、マージソートするときに ${f(i)}$ をカウントすれば ${O(n\log n)}$ で ${T}$ が求まる。

public static int mergeCount(int[] a, int fromIndex, int toIndex){
    int count = 0;
    int n = toIndex - fromIndex;
    if(n > 1){
        int mid = fromIndex + n/2;
        count += mergeCount(a, fromIndex, mid); count += mergeCount(a, mid, toIndex);
        int[] temp = new int[n]; System.arraycopy(a, fromIndex, temp, 0, n);
        //merge index i-> x, j-> left subsequence of x, k-> right subsequence of x
        for(int i = fromIndex, j = 0, k = n/2; i < toIndex; ++i){
            if(j == n/2)             a[i] = temp[k++];
            else if(k == n)             a[i] = temp[j++];
            else if(temp[j] <= temp[k]) a[i] = temp[j++];
            else                      {a[i] = temp[k++]; count += n/2 - j; }
        }
    }
    return count;
}

2015-03-11

はてなブログ用の数式エスケープスクリプト作った

Perl

ここでも指摘されているように、はてなブログのmarkdownモードで数式を使おうとすると、エスケープとかではまることが多いので、簡易スクリプト(Perl)書いた。

~~\$ ...\$,\\[...\\]で囲まれた数式をはてな記法[tex:{...}]にして、括弧内をエスケープする。~~ 最初に[tex{...}]を書いていればそれ以降は, \$...\$, \\[...\\]が使えるみたいなのでカッコはそのままにしました。

_→\_
^→\^
\{→\\{
\}→\\}
[→\\[
]→\\]

バッククオートで囲まれたところに\$ ...\$,\\[...\\]が含まれているとその中も誤ってエスケープしてしまうけど、面倒になってきたのでもういいや。

必要になったら、そのうち修正すると思います。

#!/usr/bin/perl
use strict;
use warnings;
use utf8;
local $| = 1;

my $markdown = "";
while (my $line = <STDIN>) { $markdown .= $line; }

my $output = "";
while ($markdown =~ /((\\\\\(.*?\\\\\))|(\\\\\[.*?\\\\\]))/s) { # \\(......\\) or \\[ ......\\]
    my $left = $`;
    my $openingBracket = substr($&, 0, 3);
    my $mid = substr($&, 3, -3); #\\(, \\), \\[, \\] を削除
    my $right = $';
    $mid =~ s/\\\\/\\\\\\\\/g; #\\->\\\\
    $mid =~ s/\^/\\\^/g;
    $mid =~ s/_/\\_/g;
    $mid =~ s/\\\{/\\\\\{/g;
    $mid =~ s/\\\}/\\\\\}/g;
    $mid =~ s/\[/\\\\\[/g;
    $mid =~ s/\]/\\\\\]/g;
    #$output .= ($left. "[tex:{" . $mid . "}]");
    if ($openingBracket eq "\\\\(") {
        $output .= ($left. "\\\\(" . $mid . "\\\\)");
    } else {
        $output .= ($left. "\\\\[" . $mid . "\\\\]");
    }
    $markdown = $right;
}

print "$output$markdown\n";

perlメモ

Perlではマッチングの位置情報は@+,@-に格納される。

$-[0] : マッチング(全体)の開始位置
$+[0] : マッチング(全体)の終了位置
$` : substr($str, 0, $-[0])
$& : substr($str, $-[0], $+[0] - $-[0])
$' : substr($str, $+[0])
*? : *(前のパターンの0回以上の繰り返し)の最小マッチング.量指定子の後に?をつけると最小マッチングになる。

参考

通常Perlでは正規表現のワイルドカード.は改行を除き全ての文字にマッチする(これもたまに忘れていてはまる)。

//sは１行モード指定(super dot mode)でこれをつけると.で改行を含む全ての文字がマッチするようになる。

ここでも指摘されている通り、名前が少しややこしい。

2015-03-07

プログラミングHaskell第５章(リスト内包表記)まとめ

Haskell

zip

２つのリストを取り、対応する要素をタプルにしたリストを作る。２つのリストの長さが違う場合は、短い方のリストと同じ長さのリストとして扱う。

pairs :: [a] -> [(a,a)]
pairs xs = zip xs (tail xs) 
-- pairs [1, 2, 3, 4] -----> [(1,2),(2,3),(3,4)]

文字列

StringはCharのリストと等価 ${ (String \equiv [Char] ) }$

従って、"abc"::Stringは['a', 'b', 'c']::[Char]の略記となる。

Prelude> :t (!!)
(!!) :: [a] -> Int -> a
Prelude> "abcd" !! 2
'c'
Prelude> zip "abc" [1,2,3,4]
[('a',1),('b',2),('c',3)]

リスト内包表記

集合の内包表記のように、Haskellではリスト内包表記ができる。簡易forループ的な使い方もできる。

例: ${ \{1,2,3\} \times \{4,5,6\} = \{(x, y) | x \in \{1,2,3\} , y \in \{4,5,6\} \} }$

Prelude> [(x, y)| x <- [1,2,3], y <- [4,5,6]]
[(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]
-- 生成器の列挙順を変えると生成される要素の順番が変わる
Prelude> [(x, y)| y <- [4,5,6], x <- [1,2,3]]
[(1,4),(2,4),(3,4),(1,5),(2,5),(3,5),(1,6),(2,6),(3,6)]
-- concat :: [[a]] -> [a]を使うと
concat [[(x, y) | y <- [4,5,6]] | x <- [1,2,3]]
[(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

例: ${ \{(x, y)| x\in\{1,2,3,4\}, y\in\{1,2,3,4\}, x\leq y \} }$

Prelude> [(x,y)|x<-[1..4], y<-[1..4], x <= y]
[(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)]
-- 前方の生成器で使った変数を、後方の生成器でも使用できる
Prelude> [(x,y)|x<-[1..4], y<-[x..4]]
[(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)]

例:length :: [a] -> Int

length xs = sum [1 | _ <- xs]

例:positions

positions :: Eq a => a -> [a] -> [Int]
positions x xs = [p | (e,p) <- zip xs [0..(length xs)-1], x == e]
-- positions 1 [1,2,3,1,3,2,1,3,1] ----> [0,3,6,8]

2015-03-01

プログラミングHaskell第４章(関数定義)まとめ

Haskell

cons演算子「:」

既存のリストの先頭に新しい要素を追加したリストを作成する
cons演算子は右結合

Prelude> :t (:)
(:) :: a -> [a] -> [a]
Prelude> 1 : [2, 3]
[1,2,3]
Prelude> 1 : (2 : (3 : [])) -- [1, 2, 3]はこれの略記
[1,2,3]
Prelude> 1 : 2 : 3 : [] -- 右結合なので括弧はいらない
[1,2,3]

関数 ${\leftrightarrow }$ 演算子の変換

a -> b -> cのような関数を２項演算子のように使ったりその逆もできる。

演算子 ${\rightarrow }$ 関数

関数をバックスラッシュで囲む

div 13 2    -- div :: Integral a => a -> a -> a
13 `div` 2  -- 2項演算子として使う

関数 ${\rightarrow }$ 演算子

演算子を()で囲む(セクション)。

True && False   -- &&は2項演算子
(&&) True False -- (&&) :: Bool -> Bool -> Bool

関数定義

関数名 :: 関数の型
関数定義

ghciで関数定義す場合は、letをつけて、一行で定義するか:{:}でくくって複数行で書く。レイアウト規則に注意

Prelude> :{
Prelude| let alwaysTrue :: Bool -> Bool
Prelude|  alwaysTrue _ = True
Prelude| :}

<interactive>:18:2: parse error on input `alwaysTrue'
Prelude> :{
Prelude| let alwaysTrue :: Bool -> Bool
Prelude|     alwaysTrue _ = True
Prelude| :}
Prelude> alwaysTrue False
True

条件式(if文)

if文による定義では、else節は省略不可能
レイアウト規則にも注意

signum :: Int -> Int
signnum n = if n < 0 then -1
            else if n == 0 then 0
            else 1

ガード付きの等式

最初のガードがTrueなら最初の結果が選ばれ、そうでないなら次のガードが評価される。
ガードotherwiseが使用できる。標準ライブラリで単にotherwise = True
ガード付きの等式による定義では、ガードotherwiseを必ずしも置く必要なないが、どのガードもTrueにならなければエラーが発生する。

signnum n | n < 0     = -1
          | n == 0    = 0
          | otherwise = 1

ガードと戻り値の順番が、下のような数学的な記述と逆なのを除くと結構わかりやすい構文ですね。

$ signnum(n)= \begin{cases} -1 & (n < 0) \\ 0 & (n = 0) \\ 1 & (otherwise) \end{cases} $

パターンマッチ

値、変数、_(ワイルドカード)パターン

同じ型の候補の中からマッチするものを返すよう関数定義できる。
最初のパターンにマッチすれば最初の結果が選ばれ、そうでないなら次のパターンをみる。

ワイルドカードと変数の違い

ワイルドカードは右辺には使えないが変数はおk
引数にワイルドカードが複数あっても良いが同じ名前をもつ変数があってはいけない

(&&) :: Bool -> Bool -> Bool
True  && b = b 
False && _ = False

-- ◯　同じ等式にワイルドカードが複数あるのはおk
True && True = True
_    && _    = False

-- ×　同じ等式に同じ引数名があるのはNG
b && b = b
_ && _ = False

-- ◯ガード付き等式を使えばこのようにかける
b && c | b == c    = b
       | otherwise = False

タプル・パターン

fst :: (a, b) -> a
fst (x, _) = x
snd :: (a, b) -> b
snd (_, y) = y

リスト・パターン

-- 要素数が3のリストで頭が'a'ならTrue、そうでないならFalse
axxTest :: [Char] -> Bool
axxTest ['a', _, _] = True
axxTest _  = False
-- 先頭要素が'a`のリストならTrue、そうでないならFalse
firstATest :: [Char] -> Bool
firstATest ('a' : _) = True -- 関数適用は演算子より優先順位が高いため()でくくる必要がある
firstATest _ = False

${ n+k }$ パターン

${ n }$ は整数、 ${ k }$ は正の整数定数
${ n+k }$ パターンは ${ k }$ 以上の整数にしかマッチしない
関数適用の方が優先順位が高いので()でくくる必要がある

※Haskell 2010で仕様から削られてます。使わないほうが良いでしょう。

ghciで使う場合はXNPlusKPatternsオプションを使う

ghci -XNPlusKPatterns

ファイルにオプションを書けばコマンドラインオプションは不要

{-# LANGUAGE NPlusKPatterns #-}
pred :: Int -> Int
pred 0       = 0
pred (n + 1) = n
-- 負の数にはマッチしないのでpred (-1)はNG

where節

where節の直前で定義した関数内でwhere節で定義した局所関数や局所変数を使う事ができる。レイアウト規則に注意。

halve :: [a] -> ([a], [a])
halve xs = (take l xs, drop l xs)
         where l = length xs `div` 2
-- splitAt :: Int -> [a] -> ([a], [a])を使うと
halve xs = splitAt (length xs `div` 2) xs

${ \lambda }$ 式(lambda expression)

バックスラッシュで ${ \lambda }$ 式(無名関数)が使用できる。

カリー化された関数の形式的な意味づけに利用できる

mul3 x y z = x*y*z
mul3 = \x -> (\y -> (\z -> x*y*z))
mul3 = (\x y z -> x*y*z) -- こう書くこともできる

関数を返す関数定義に便利

-- const関数は、「引数が何であっても指定した定数 x を返す関数」を返す
const :: a -> b -> a
const x _ = x
-- 関数を返すことがわかりやすい書き方
const :: a -> (b -> a)
const x = \_ -> x

where節に書く局所関数を簡略記述できる

-- map :: (a -> b) -> [a] -> [b]
-- map関数は、リストの各要素に関数を適用したリストを返す
evens :: Int -> [Int]
evens n = map (\x -> x*2) [0..n-1]

セクション

${ \oplus }$ を演算子とすると、式 ${ (\oplus ), (x\oplus ), (\oplus y) }$ をセクションという。

${ (\oplus ) = \lambda x \rightarrow (\lambda y \rightarrow x \oplus y) }$
${ (x\oplus ) = \lambda y \rightarrow x \oplus y }$
${ (\oplus y) = \lambda x \rightarrow x \oplus y }$

主な利用方法

部分適用した関数などの定義
演算子の型の宣言(演算子そのものは正しい式ではないので演算子$\rightarrow$関数変換する)
他の関数に演算子を渡す

他の言語で外部コマンド呼び出し簡易メモ

C

参考

項目23 オブジェクト間通信には、DelegateとDataSourceプロトコルを使う

項目24 カテゴリを使ってクラスの実装を管理できるサイズに分割せよ

項目25 サードパーティクラスに追加するカテゴリで使う名前には必ずプレフィックスを付ける

項目26 カテゴリではプロパティを使わないようにする

項目27 実装の詳細を隠すためにクラス延長カテゴリを活用せよ

クラス延長(無名)カテゴリ

項目28 プロトコルを使って無名オブジェクトを提供せよ

再帰関数定義のための５段階の工程

1:型を定義する

2:場合分けをする

3:簡単な方を定義する

4:複雑な方を定義する

5:一般化し簡単にする

多重再帰

相互再帰

交換ソート(Exchange sorts)

バブルソート, 基本交換法, 隣接交換法, 交換法(bubble sort)

シェーカーソート(cocktail sort, bidirectional bubble sort, cocktail shaker sort, shaker sort, ripple sort, shuffle sort, shuttle sort)

奇偶転置ソート(odd-even sort)

櫛ソート(comb sort)

クイックソート(quicksort)

ボゴソート(bogosort, stupid sort, slowsort, random sort, shotgun sort, monkey sort)

選択ソート(Selection sorts)

選択ソート(selection sort)

ヒープソート(heapsort)

２分ヒープ木(binary heap tree)

挿入ソート(insertion sorts)

挿入ソート(insertion sort)

シェルソート(shell sort)

分配整列(Distribution sorts)

バケットソート、ビンソート(bucket sort, bin sort)

基数ソート(radix sort)

スリープソート(sleep sort)

マージソート(Merge sorts)

マージソート(merge sort, mergesort)

perlメモ

zip

文字列

リスト内包表記

cons演算子「:」

関数演算子の変換

関数定義

条件式(if文)

ガード付きの等式

パターンマッチ

値、変数、_(ワイルドカード)パターン

タプル・パターン

リスト・パターン

パターン

where節

式(lambda expression)

セクション

再帰関数定義のための５段階の工程 ${}$

関数 ${\leftrightarrow }$ 演算子の変換

${ n+k }$ パターン

${ \lambda }$ 式(lambda expression)