レコードのふしぎ

ありゃー、Sony...。

いや、もうこれだけでなんとなく察するものがあるという人も多いのではないでしょうか。このサイトでは、あんまり企業や製品のことについて言及することは避けようと思っているのですが、あまりと言えばあまりな成り行きについ。

閑話休題。「AppleScript でアルゴリズム」でクイックソートを掲載したのですが、面白いことをデザイナーの池田さんが教えてくれました。

池田さんのサイトでは「AppleScript 実験室」と題していろいろな実験結果を掲載されています。Mac OS X になってから、AppleScript でいろいろ実験をしてその結果を掲載しているサイトというのは少ないので、こういうサイトはとても貴重です。

さて、その「AppleScript 実験室」には「レコード内のリストの参照」というコンテンツがあります。池田さんが行った実験というのは、「レコード内のリストの要素の参照と通常のリストの要素の参照、どれぐらいアクセス速度が異なるか」というものです（詳しくは、池田さんのサイトの方を参照してください）。おそらく、リストを参照するよりレコード内のリストを参照する方が遅くなるだろう...という予測をもとに実験を行ったのだと思いますが、予想外の結果になっています。レコード内のリストを参照した方が速いのです。

この書き方だと誤解がありますが、リストに a reference to を使うより、レコードに a reference to を使う方が速い、という方が正確ですね。以下の結果を見てもらうと分かりますが。

実験結果をクイックソートに適用したものを送ってきてくださいました。これを動かしてみると、確かに速いのです。なぜ？

クイックソートでは分かりにくいので、以下のようなスクリプトを作って試してみました。

set theList to {}
repeat with i from 1 to 10000
    set end of theList to i
end repeat

set cd to current date
repeat 100000 times
    item 10 of theList
end repeat

(current date) - cd

整数値をリストに 1 万項目入れて、10 番目の要素を 10 万回取り出すだけのスクリプトです。これは、環境によって結果が異なりますが、iMac G5 では約 160 秒。これではあまりにも遅いので、通常は a reference to を使ってリストの参照を用います。

set theList to {}
set theListRef to a reference to theList -- リストを参照に変換

repeat with i from 1 to 10000
    set end of theListRef to i
end repeat

set cd to current date
repeat 100000 times
    item 10 of theListRef -- リストの参照にアクセス
end repeat

(current date) - cd

こうするだけで約 3 秒になります。次に池田さんが行った実験を適用します。

set theList to {}
set theListRef to a reference to theList

repeat with i from 1 to 10000
    set end of theListRef to i
end repeat

set theRecord to {numList:{}}
set theRecordRef to a reference to theRecord -- レコードの参照に変換
set numList of theRecordRef to theList

set cd to current date
repeat 100000 times
    item 10 of numList of theRecordRef -- レコードの参照にアクセス
end repeat

(current date) - cd

こうすると、さらに速くなって約 1 秒。レコードにアクセスする方が速いのかと思い、a reference to を使わずに比較してみるけど、リストのときと変わりません。

set theList to {}

repeat with i from 1 to 10000
    set end of theList to i
end repeat

set theRecord to {numList:{}}
set numList of theRecord to theList

set cd to current date
repeat 5000 times
    item 10 of numList of theRecord -- ここ
end repeat

(current date) - cd

このスクリプトの numList of theRecord を theList に変えても速度的に差はないんですね。a reference to で参照に変換したときだけ速いんです。原因不明。この結果を理解するには、AppleScript の内部に踏み込まないといけないような。どなたか、なぜ速くなるかご存知でしょうか？

誤解のないように、追記。a reference to を使うと速度的には速くなりますが、乱用すると逆に遅くなります。なんでもかんでも速くなるわけではないので。

続きを読む

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 はアプリケーションを操作できるのでソートも検索もアプリケーションに任せてしまうのが一番手っ取り早いのですが。

続きを読む