AS Hole（AppleScriptの穴） By Piyomaru Software

03/10 シェルソート高速化比較（さらに改良）

先日投稿していただいたshell sortに、若干の改良を加えてさらに高速化したAppleScriptです。

tsuki3さんから投稿していただいたshell sortのコメントに、

ちなみに私の経験上、リストの要素数を得る場合は “lenth of ~” を使うよりも “count ~” を用いた方が速いはずです。また、私のスクリプトでは複数の要素を纏めて set しておりますが、 これを別個にすればより速くなるはずです。

とあったので、すべて試してみました。

MacBook Pro 2010 Core i7 2.66GHz, RAM 8GB, Mac OS X 10.6.8の環境で改良版の「shellSort5」を試してみたところ、shellSort4で５秒かかっていた3万件のソートが４秒に。正直、こんなに速くなるとは思ってもみませんでした。ループ回数が多いので、わずかなスピードアップの集積が大きいんでしょうね。

Classic Mac OSの時代には、サードパーティのOSAX（スクリプティング機能拡張）の機能を呼び出してハードウェア制御（キーボードLEDの点灯制御、シリアルポート経由の機器制御）を行ったり、高度な命令を利用することを目指していました。最終的には200個ぐらいのOSAXをシステムにインストールして使っていたほど。

ソートに関しても、サードパーティのOSAXで提供されるソート命令を利用することが多かったのですが、Mac OS Xの時代になってMac OS X対応できない（or しない）OSAXが多数あったため、OSAXへの依存度を下げることが必要になってきました。のちに、Universal Binary対応や64ビット対応など、さまざまなハードルがあってOSAX側の対応が後手後手に回る中、Mac OS Xへの移行当初からOSAXへの依存度を下げる努力をしてきたため、自分はあまり影響を受けませんでした。また、このOSAX依存度軽減の努力は、AppleScript StudioによるGUIベースのアプリケーション開発時にもおおいに役立ちました（アプリケーションと一緒に再配布できないライセンス条件のOSAXなどもあったため）。

正直なところ、ソートルーチンなんて一度作ってそこそこ満足できれば、見直すことなどほとんどない部品。最初のバージョンからここまでいろいろと高速化ができたのは、多くのScripterの方々の努力と経験によるところが大きく、１人でやっているだけでは、なかなか手が回らないところだと思います。

そういう意味では、こういうBlogを立ち上げて地道に活動してきた意義というのはあるのではないかと。この３月でスタートして４年が経過。掲載Scriptも1,000本を超えました。当初の、「サブルーチン資産に対するMac OS Xバージョンアップの影響検証」というねらいを超えて、技術的な交流の場として機能していけたらいいですね。

スクリプト名：(数値ソート) シェルソート_v2.scpt

set lst to {}
set lstr to (a reference to lst)
repeat 30000 times
　　set lstr’s end to (random number 999)
end repeat
set t to (current date)

set res to my shellSort5(lst)

– 正誤確認用
(*set resr to (a reference to res)
repeat with i from 2 to (count resr)
　　if (resr’s item (i - 1) > resr’s item i) then return false
end repeat*)

return {“” & ((current date) - t) & “秒”}

on shellSort1(lst) – 配列を使用した基本形
　　set len to (count lst)
　　set gap to 1
　　repeat while (gap ≤ len)
　　　　set gap to ((gap * 3) + 1)
　　end repeat
　　repeat while (gap > 0)
　　　　set gap to (gap div 3)
　　　　if (gap < len) then
　　　　　　repeat with i from gap to (len - 1)
　　　　　　　　set {temp, j} to {lst’s item (i + 1), i}
　　　　　　　　repeat while ((j ≥ gap) and (lst’s item (j - gap + 1) > temp))
　　　　　　　　　　set {lst’s item (j + 1), j} to {lst’s item (j - gap + 1), j - gap}
　　　　　　　　end repeat
　　　　　　　　set lst’s item (j + 1) to temp
　　　　　　end repeat
　　　　end if
　　end repeat
　　return lst
end shellSort1

on shellSort2(lst) – 参照 (a reference to…) を使用
　　set {lstr, len, gap} to {a reference to lst, count lst, 1}
　　repeat while (gap ≤ len)
　　　　set gap to ((gap * 3) + 1)
　　end repeat
　　repeat while (gap > 0)
　　　　set gap to (gap div 3)
　　　　if (gap < len) then
　　　　　　repeat with i from gap to (len - 1)
　　　　　　　　set {temp, j} to {lstr’s item (i + 1), i}
　　　　　　　　repeat while ((j ≥ gap) and (lstr’s item (j - gap + 1) > temp))
　　　　　　　　　　set {lstr’s item (j + 1), j} to {lstr’s item (j - gap + 1), j - gap}
　　　　　　　　end repeat
　　　　　　　　set lstr’s item (j + 1) to temp
　　　　　　end repeat
　　　　end if
　　end repeat
　　return lst
end shellSort2

on shellSort3(lst) – レコードと参照、グローバル変数を併用
　　global rec
　　set rec to {list:lst}
　　set {recr, len, gap} to {a reference to rec, count lst, 1}
　　repeat while (gap ≤ len)
　　　　set gap to ((gap * 3) + 1)
　　end repeat
　　repeat while (gap > 0)
　　　　set gap to (gap div 3)
　　　　if (gap < len) then
　　　　　　repeat with i from gap to (len - 1)
　　　　　　　　set {temp, j} to {recr’s list’s item (i + 1), i}
　　　　　　　　repeat while ((j ≥ gap) and (recr’s list’s item (j - gap + 1) > temp))
　　　　　　　　　　set {recr’s list’s item (j + 1), j} to {recr’s list’s item (j - gap + 1), j - gap}
　　　　　　　　end repeat
　　　　　　　　set recr’s list’s item (j + 1) to temp
　　　　　　end repeat
　　　　end if
　　end repeat
　　return recr’s list
end shellSort3

on shellSort4(lst) – スクリプトオブジェクトを使用
　　script o
　　　　property list : lst
　　end script
　　set {len, gap} to {count o’s list’s items, 1}
　　repeat while (gap ≤ len)
　　　　set gap to ((gap * 3) + 1)
　　end repeat
　　repeat while (gap > 0)
　　　　set gap to (gap div 3)
　　　　if (gap < len) then
　　　　　　repeat with i from gap to (len - 1)
　　　　　　　　set {temp, j} to {o’s list’s item (i + 1), i}
　　　　　　　　repeat while ((j ≥ gap) and (o’s list’s item (j - gap + 1) > temp))
　　　　　　　　　　set {o’s list’s item (j + 1), j} to {o’s list’s item (j - gap + 1), j - gap}
　　　　　　　　end repeat
　　　　　　　　set o’s list’s item (j + 1) to temp
　　　　　　end repeat
　　　　end if
　　end repeat
　　return o’s list
end shellSort4

–プレーンなAppleScriptベースでは最速ソート
on shellSort5(aSortList) – スクリプトオブジェクトを使用
　　script oBj
　　　　property list : aSortList
　　end script
　　set len to count oBj’s list’s items
　　set gap to 1
　　repeat while (gap ≤ len)
　　　　set gap to ((gap * 3) + 1)
　　end repeat
　　repeat while (gap > 0)
　　　　set gap to (gap div 3)
　　　　if (gap < len) then
　　　　　　repeat with i from gap to (len - 1)
　　　　　　　　set temp to oBj’s list’s item (i + 1)
　　　　　　　　set j to i
　　　　　　　　repeat while ((j ≥ gap) and (oBj’s list’s item (j - gap + 1) > temp))
　　　　　　　　　　set oBj’s list’s item (j + 1) to oBj’s list’s item (j - gap + 1)
　　　　　　　　　　set j to j - gap
　　　　　　　　end repeat
　　　　　　　　set oBj’s list’s item (j + 1) to temp
　　　　　　end repeat
　　　　end if
　　end repeat
　　return oBj’s list
end shellSort5

▼新規書類に　 ▼カーソル位置に　 ▼ドキュメント末尾に

Posted in 10.5対応, ソート(sorting), 10.6対応, 10.4対応, 10.7対応, 10.8対応 | No Comments »

03/07 シェルソート高速化比較

AppleScriptにおけるシェルソートの高速化について、それぞれ検証するScriptをtsuki3さんから投稿していただきました。

3/3 の記事 “100倍速いシェルソートでリストをソート” 内、解説の項にて 高速化の計測を話題にされておりましたが、数年前に私が書いたスクリプトが それを目的としたものでしたので、投稿いたします。

なお、拙作のスプリクトオブジェクトを用いたものの方が誤差程度ですが、 edama2さんのものより（当方の環境では）速いようです。 ただ、レギュレーションが違うので比較自体に意味が無いのかもしれませんが。

ちなみに私の経験上、リストの要素数を得る場合は “lenth of ~” を使うよりも “count ~” を用いた方が速いはずです。また、私のスクリプトでは複数の要素を纏めて set しておりますが、 これを別個にすればより速くなるはずです。

一度、きちんと比較しておかないと……とは思ってはいたのですが、ついついめんどくさくて手つかずの状態。ちょうどいいところに投稿していただけたので、実測値を計ってみることにしました。

計測するのは、以下の４つ。

　shell sort 1……高速化を一切行っていない、通常のシェルソート
　shell sort 2……オーソドックスな「a reference to」を使用して高速化
　shell sort 3……レコードと参照、グローバル変数を併用
　shell sort 4……スクリプトオブジェクトを使用

……shell sort 3は、ちょっとお目にかかったことのないタイプ。

ひととおり、MacBook Pro 2010 Core i7 2.66GHz, RAM 8GB, Mac OS X 10.6.8の環境でテストしてみると……

スクリプトオブジェクトを使用するものが一番高速（AppleScriptObjCを使うと、そちらの方が速いですが）ということが客観的によく分りました。

スクリプト名：(数値ソート) シェルソート.scpt

set lst to {}
set lstr to (a reference to lst)
repeat 30000 times
　　set lstr’s end to (random number 999)
end repeat
set t to (current date)

set res to my shellSort4(lst)

– 正誤確認用
(*set resr to (a reference to res)
repeat with i from 2 to (count resr)
　　if (resr’s item (i - 1) > resr’s item i) then return false
end repeat*)

return {“” & ((current date) - t) & “秒”}

on shellSort1(lst) – 配列を使用した基本形
　　set len to (count lst)
　　set gap to 1
　　repeat while (gap ≤ len)
　　　　set gap to ((gap * 3) + 1)
　　end repeat
　　repeat while (gap > 0)
　　　　set gap to (gap div 3)
　　　　if (gap < len) then
　　　　　　repeat with i from gap to (len - 1)
　　　　　　　　set {temp, j} to {lst’s item (i + 1), i}
　　　　　　　　repeat while ((j ≥ gap) and (lst’s item (j - gap + 1) > temp))
　　　　　　　　　　set {lst’s item (j + 1), j} to {lst’s item (j - gap + 1), j - gap}
　　　　　　　　end repeat
　　　　　　　　set lst’s item (j + 1) to temp
　　　　　　end repeat
　　　　end if
　　end repeat
　　return lst
end shellSort1

on shellSort2(lst) – 参照 (a reference to…) を使用
　　set {lstr, len, gap} to {a reference to lst, count lst, 1}
　　repeat while (gap ≤ len)
　　　　set gap to ((gap * 3) + 1)
　　end repeat
　　repeat while (gap > 0)
　　　　set gap to (gap div 3)
　　　　if (gap < len) then
　　　　　　repeat with i from gap to (len - 1)
　　　　　　　　set {temp, j} to {lstr’s item (i + 1), i}
　　　　　　　　repeat while ((j ≥ gap) and (lstr’s item (j - gap + 1) > temp))
　　　　　　　　　　set {lstr’s item (j + 1), j} to {lstr’s item (j - gap + 1), j - gap}
　　　　　　　　end repeat
　　　　　　　　set lstr’s item (j + 1) to temp
　　　　　　end repeat
　　　　end if
　　end repeat
　　return lst
end shellSort2

on shellSort3(lst) – レコードと参照、グローバル変数を併用
　　global rec
　　set rec to {list:lst}
　　set {recr, len, gap} to {a reference to rec, count lst, 1}
　　repeat while (gap ≤ len)
　　　　set gap to ((gap * 3) + 1)
　　end repeat
　　repeat while (gap > 0)
　　　　set gap to (gap div 3)
　　　　if (gap < len) then
　　　　　　repeat with i from gap to (len - 1)
　　　　　　　　set {temp, j} to {recr’s list’s item (i + 1), i}
　　　　　　　　repeat while ((j ≥ gap) and (recr’s list’s item (j - gap + 1) > temp))
　　　　　　　　　　set {recr’s list’s item (j + 1), j} to {recr’s list’s item (j - gap + 1), j - gap}
　　　　　　　　end repeat
　　　　　　　　set recr’s list’s item (j + 1) to temp
　　　　　　end repeat
　　　　end if
　　end repeat
　　return recr’s list
end shellSort3

on shellSort4(lst) – スクリプトオブジェクトを使用
　　script o
　　　　property list : lst
　　end script
　　set {len, gap} to {count o’s list’s items, 1}
　　repeat while (gap ≤ len)
　　　　set gap to ((gap * 3) + 1)
　　end repeat
　　repeat while (gap > 0)
　　　　set gap to (gap div 3)
　　　　if (gap < len) then
　　　　　　repeat with i from gap to (len - 1)
　　　　　　　　set {temp, j} to {o’s list’s item (i + 1), i}
　　　　　　　　repeat while ((j ≥ gap) and (o’s list’s item (j - gap + 1) > temp))
　　　　　　　　　　set {o’s list’s item (j + 1), j} to {o’s list’s item (j - gap + 1), j - gap}
　　　　　　　　end repeat
　　　　　　　　set o’s list’s item (j + 1) to temp
　　　　　　end repeat
　　　　end if
　　end repeat
　　return o’s list
end shellSort4

▼新規書類に　 ▼カーソル位置に　 ▼ドキュメント末尾に

Posted in 10.5対応, ソート(sorting), 10.6対応, 10.4対応, 10.7対応, 10.8対応 | No Comments »

03/03 100倍速いシェルソートでリストをソート

edama2さんよりの投稿です

基本的には掲載されている「シェルソートでリストをソート」をスプリクトオブジェクトで処理にしているだけです。サンプルでソートする数が100倍なだけで「100倍速い」という数字には特に根拠はありません。

スクリプト名：100倍速いシェルソートでリストをソート

set theList to {}
set i to 1
repeat 30000 times
　　copy (random number from 100 to 99999) to the end of theList
　　set i to i + 1
end repeat

set s0Time to current date
set aRes to shellSort_order_(theList, false) of me
set s1Time to current date

display dialog (s1Time - s0Time) as string

–シェルソートでリストを昇順ソート（入れ子ではないリスト）
on shellSort_order_(a, isAsc)
　　
　　script a_ref
　　　　property contents : a
　　end script
　　
　　set n to length of a
　　set cols to {1391376, 463792, 198768, 86961, 33936, 13776, 4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1}
　　repeat with h in cols
　　　　if (h ≤ (n - 1)) then
　　　　　　repeat with i from h to (n - 1)
　　　　　　　　set v to item (i + 1) of contents of a_ref
　　　　　　　　set j to i
　　　　　　　　repeat while (j ≥ h) and ((item (j - h + 1) of contents of a_ref) > v)
　　　　　　　　　　set (item (j + 1) of contents of a_ref) to (item (j - h + 1) of contents of a_ref)
　　　　　　　　　　set j to j - h
　　　　　　　　end repeat
　　　　　　　　set item (j + 1) of contents of a_ref to v
　　　　　　end repeat
　　　　end if
　　end repeat
　　
　　if not isAsc then set a to a’s reverse
　　
　　return a
end shellSort_order_

▼新規書類に　 ▼カーソル位置に　 ▼ドキュメント末尾に

Piyomaru Softwareによる解説：

以前に掲載したシェルソートのルーチンの改良版です。ソートというか、巨大なリスト型変数（配列）の操作をAppleScriptで行うとスピードが低下するので、3,000～4,000要素（Item）を超えるサイズのリスト型変数を扱う場合には、何らかの高速化を行うべきです。

AppleScriptにおけるソートの高速化手法にはおよそ３つあって、１つが「a reference to」による間接アクセスによる高速化。

著しく高速化するものの、データを格納する変数と間接アクセスする変数の２つをグローバル宣言する必要があり、効果は大きいものの、副作用も大きい（グローバル宣言した変数が他のルーチンの変数をぶつかっていないか確認が必要、など）ため、そのための作業コストが大きく「手軽」とはいえませんでした。

２つ目が、ここで活用されている「スクリプトオブジェクト内にプロパティを持つ」というアクセス方法で、a reference toと同程度ぐらいには（厳密に計測してはいないのですが）高速化することが知られています。

スクリプトオブジェクトの利用による高速化処理の前後で、サンプルの3万項目の乱数リストをソート所要時間を計測比較してみたところ（MacBook Pro Core i7 2.66GHz, Mac OS X 10.6.8, 8GB RAM）、

　高速化前：2967秒
　高速化後：8秒

と、370倍ぐらい高速になっていました。リストの項目が大きいほど高速化の効果が出やすいものと思われます。

３つめが、Mac OS X 10.6から使えるようになったAppleScript ObjCを用いること。この環境内でCocoaのソートルーチンを呼び出すと速いので、一度すべてのやりかたでどのソート方法が速いのか、比較をしておくべきでしょう。

追記（2012/3/4）：

MacBook Air 2011 (Core i5 1.6GHz、Mac OS X 10.7.3、RAM 4GB）でこの乱数３万件のソートを試してみたところ……

　本ScriptをAppleScript Editor上で実行：７秒
　本ScriptをAppleScriptObjC on Xcodeのプロジェクトで実行：８秒
　AppleScriptObjC on XcodeのCocoaベースのソートでリスト（正確にはレコード）をScriptのオブジェクトに持たせた場合：129秒
　AppleScriptObjC on XcodeのCocoaベースのソートで何も高速化処理を行っていない場合：（計測不能）

Cocoaベースのソートがたいして速くない（純粋にリスト＝NSArrayではないので、同じ処理ではないですが）ことに驚きました。AppleScriptObjCのプログラムも、ソート処理をAppleScriptネイティブのものに書き換えておいたほうがよさそうな……。

あるいは、３万件というデータ件数になると、AppleScriptObjCでもCoreDataを併用することを検討すべきなのかもしれません。データベースに入れてしまえば、３万件ごときのソートなど一瞬でしょうし。

さらに追記（2012/3/4）：

AppleScriptObjCで以下のようなプログラム（単なるArrayをソート）にしてみたところ、３万件でもソートに要する時間は１秒以下でした（MacBook Pro Core i7 2.66GHz, Mac OS X 10.6.8, RAM 8GB）。

AppleScriptObjCファイル名：sortArrayAppDelegate.applescript

–
– sortArrayAppDelegate.applescript
– sortArray
–
– Created by Takaaki Naganoya on 12/03/04.
– Copyright 2012 Piyomaru Software. All rights reserved.
–

script aRef
　　property contents : {}
end script

script sortArrayAppDelegate
　　property parent : class “NSObject”
　　
　　on applicationWillFinishLaunching_(aNotification)
　　　　– Nothing
　　end applicationWillFinishLaunching_
　　
　　on applicationShouldTerminate_(sender)
　　　　return current application’s NSTerminateNow
　　end applicationShouldTerminate_
　　
　　on clicked_(sender)
　　　　
　　　　set aList to {}
　　　　repeat 30000 times
　　　　　　tell current application
　　　　　　　　set the end of (contents of aRef) to (random number from 1000 to 9999) as string
　　　　　　end tell
　　　　end repeat
　　　　
　　　　tell current application
　　　　　　set sTime to current date
　　　　end tell
　　　　
　　　　set theArray to current application’s class “NSMutableArray”’s arrayWithArray_(contents of aRef)
　　　　set bList to theArray’s sortedArrayUsingSelector_(“localizedCaseInsensitiveCompare:”)
　　　　
　　　　tell current application
　　　　　　set eTime to current date
　　　　　　set totalTime to eTime - sTime
　　　　end tell
　　　　
　　　　display dialog (totalTime as string)
　　　　
　　end clicked_
　　
end script

▼新規書類に　 ▼カーソル位置に　 ▼ドキュメント末尾に

Posted in リスト処理(list), 10.5対応, ソート(sorting), 10.6対応, 10.4対応, AppleScriptObjC, 10.7対応, 10.8対応 | No Comments »

01/14 シェルソートでリストをソート

フラットな（入れ子ではない）リストをシェルソートでソートするAppleScriptです。冒頭にあるのはテスト用データ作成部分です。

入れ子になっているリスト、{{1,2,3,4}, {2,3,4,5}, {3,4,5,6}} をソートする機会はめちゃめちゃ多いのですが、単なるフラットなリストだと使用頻度はぐっと低く、わざわざ昇順/降順のシェルソートルーチンを用意していませんでした（もっと遅い部品を使っていました）。

たまたま、スピードにこだわりたい処理があったのでシェルソートで単純なリストの昇順/降順ソートをまとめておきました。

スクリプト名：シェルソートでリストをソート

set theList to {}
set i to 1
repeat 300 times
　　copy (random number from 100 to 999) to the end of theList
　　set i to i + 1
end repeat

set s0Time to current date
set aRes to shellSortDecending(theList) of me
set s1Time to current date

display dialog (s1Time - s0Time) as string
aRes

–シェルソートでリストを昇順ソート（入れ子ではないリスト）
on shellSortAscending(a)
　　set n to length of a
　　set cols to {1391376, 463792, 198768, 86961, 33936, 13776, 4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1}
　　repeat with h in cols
　　　　if (h ≤ (n - 1)) then
　　　　　　repeat with i from h to (n - 1)
　　　　　　　　set v to item (i + 1) of a
　　　　　　　　set j to i
　　　　　　　　repeat while (j ≥ h) and ((contents of item (j - h + 1) of a) > v)
　　　　　　　　　　set (item (j + 1) of a) to (item (j - h + 1) of a)
　　　　　　　　　　set j to j - h
　　　　　　　　end repeat
　　　　　　　　set item (j + 1) of a to v
　　　　　　end repeat
　　　　end if
　　end repeat
　　return a
end shellSortAscending

–シェルソートでリストを降順ソート（入れ子ではないリスト）
on shellSortDecending(a)
　　set n to length of a
　　set cols to {1391376, 463792, 198768, 86961, 33936, 13776, 4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1}
　　repeat with h in cols
　　　　if (h ≤ (n - 1)) then
　　　　　　repeat with i from h to (n - 1)
　　　　　　　　set v to item (i + 1) of a
　　　　　　　　set j to i
　　　　　　　　repeat while (j ≥ h) and ((contents of item (j - h + 1) of a) < v)
　　　　　　　　　　set (item (j + 1) of a) to (item (j - h + 1) of a)
　　　　　　　　　　set j to j - h
　　　　　　　　end repeat
　　　　　　　　set item (j + 1) of a to v
　　　　　　end repeat
　　　　end if
　　end repeat
　　return a
end shellSortDecending