この記事は iOSその2 Advent Calendar 2016 第17日目の記事です。

はじめに

ソフトウェアエンジニアなのにアルゴリズムのこと全くわからないのはちょっとどうかと思い、
Swiftの練習がてら蟻本の問題を解いている。

iOSというよりは完全にSwiftの話になってしまったが、まぁいいや…。

筆者のバックグラウンド

アルゴリズムや計算機科学をしっかり学んだことは無い。
わかりやすいところでは、AtCoder Beginner ContestのC問題が解けたり解けなかったりするくらい。

やっていること

上記の通り、蟻本の内容をSwiftで実装しながら読み進めている。
蟻本自体のサンプルはCやC++で記述されている。

レポジトリはここ。
https://github.com/almichest/Ari

進め方

蟻本のページ数に対応した名前のclassを作り実装。
動作確認したらやはり蟻本のページ数に対応した内容でコミット。
あとで確認するときにわかりやすくて良い。

動作確認したいわけではないファイルまでビルド対象になってしまうのは鬱陶しいが、大した時間がかかるわけでもないので気にしない。

lower_boundを実装してみた話

読み進めていく中で、STLのlower_bound が使われていた。
(SwiftではSTL無いしどうしたもんかなー。c++をobjcでラップしたインターフェースでも作るかな〜)
とか考えたのだが、せっかくなので、とSwiftのGenericsを活かしたlower_bound的なextensionを作ってみた。

コードは以下の通り。必要だったのでバイナリサーチも実装してある。

ArrayExtension.swift


import Foundation

enum ArrayExtensionError: Error {
    case generics
    case invalidTarget
}

protocol Target: Equatable, Comparable {
}

extension Int: Target {}
extension Float: Target {}
extension Double: Target {}
extension UInt64: Target {}

extension Array where Element: Target {

    /* value <= array[x] となる 最小のxを返す */
    func lowerBound<T: Target>(_ value: T) throws -> Int {
        guard value is Array.Iterator.Element else { throw ArrayExtensionError.generics }
        guard let last = self.last , value <= last as! T else { throw ArrayExtensionError.invalidTarget }

        let index = try! binarySearch(value)

        if self.count <= index {
            throw ArrayExtensionError.invalidTarget
        }

        let found = self[index] as! T

        if value <= found {
            return index
        }

        if found <= value && index < self.count - 1 {
            return index + 1
        }

        throw ArrayExtensionError.invalidTarget
    }

    func binarySearch<T: Target>(_ value: T) throws -> Int {
        guard value is Array.Iterator.Element else { throw ArrayExtensionError.generics }
        var lo = 0
        var hi = self.count - 1
        while lo < hi {
            let mid = lo + (hi - lo) / 2
            if (self[mid] as! T) < value {
                lo = mid + 1
            } else {
                hi = mid
            }
        }
        return lo
    }
}

EquatableとComparableを実装したクラスのArrayならなんでも使える。
多分ちゃんと動いていると思う。動かないサンプルがあったら教えてください。

やってみて思ったこと

薄々感づいてはいたが、アルゴリズムのセンスがない。初級の時点でだいぶつらい。
とは言え、単純に同じ言語で写経するよりは考えることが多いので、身になることはある。と思う。
問題を解くときに幅優先かな～深さ優先かな〜dpにするとしたらなにで漸化式立てるかな〜、程度のことは考えるようになった。
きっと無駄ではない。
新しい言語を勉強するときはアルゴリズムをネタにするのは割と良い気がしてきた。
標準入出力、Array、HashMapなどの基本的な要素は網羅できるし。

終わりに

とりあえず時間をかけてもいいからARCの問題を解けるくらいにはなりたい。