AppleScript でアルゴリズム

掲示板の方でソートについての話題が出ていたので、取り上げてみる。

AppleScript でアルゴリズム？ソート？と思う方もいるかもしれません。AppleScript は速度的に遅いからソートなんてできない、大量のデータを使う必要があるなら、AppleScript 以外の解決方法を見つけた方がいい。というような印象があるような気がします。

こういったことってケースバイケースなので一概にどんな方法がいいとは言えません。タブ区切りのテキストデータで 2 列目でソートしたいというならシェルスクリプトの sort を使えばいいですし、どうしても動作速度が必要なら、AppleScript Studio の Table View（data source）に表示させてしまえばいいし。

ただ、知的好奇心、あるいは興味のために AppleScript でバブルソートや単純選択ソート、ハッシュマップや二分木といった有名なアルゴリズムを書いてみるのも面白いかもしれません。圧縮や暗号化や検索なんかも。例えば、次のスクリプトは単純なクイックソート。C 言語で紹介されていたものをそのまま AppleScript に置き換えたものです。

Script Editor で開く

set tmp to {}
repeat with i from 1 to 1000
    set end of tmp to i
end repeat

set theList to {}
repeat with i from 1 to 1000
    set end of theList to some item of tmp
end repeat

set cd to current date
qSort(1, count theList, a reference to theList)
display dialog (current date) - cd

(*
bottom = 最小値、top = 最大値、theList = ソートを行うリスト
*)
on qSort(bottom, top, theList)
    if bottom is greater than or equal to top then return

    set base to item bottom of theList
    set lower to bottom
    set upper to top

    repeat while (lower is less than upper)
        repeat while (lower is less than or equal to upper and item lower of theList is less than or equal to base)
            set lower to lower + 1
        end repeat

        repeat while (lower is less than or equal to upper and item upper of theList is greater than base)
            set upper to upper - 1
        end repeat

        if (lower is less than upper) then
            set tmp to item lower of theList
            set item lower of theList to item upper of theList
            set item upper of theList to tmp
        end if
    end repeat

    set tmp to item bottom of theList
    set item bottom of theList to item upper of theList
    set item upper of theList to tmp
    qSort(bottom, upper - 1, theList)
    qSort(upper + 1, top, theList)
end qSort

これでも 1000 項目で 0 〜 1 秒。10000 項目で 8 〜 9 秒。ベースの取り方と再帰の部分、ほとんどソートされているときの最適化を施せば、もう少し速くなるのでは？と思う。

まぁ、AppleScript はアプリケーションを操作できるのでソートも検索もアプリケーションに任せてしまうのが一番手っ取り早いのですが。