OLD Style AppleScriptによる、複数キーを指定できる2D ListのソートScriptです。
最大限に高速化してだいたいこのぐらいで、1万要素の2D Listに対して3つのソートキーを指定してソートを実行して2秒といったところ。Cocoaのソート機能を使ったほうが高速です。
ただし、本ソートルーチンを使うとListの中にアプリケーションのオブジェクトを格納できるので、割と使い道はあります。
AppleScript名:複数キーによるソートテスト3.1 |
–複数キーによるソートテスト3(複数キーを許容。キー数無制限) script orig property aList : {} end script –テストデータ作成 set aList of orig to {} repeat 10000 times –3次まですべてのキーを使ったソートが発生するよう、1次、2次キーは乱数範囲をわざと狭くしてある set the end of aList of orig to {"a", random number from 1 to 10, random number from 1 to 10, random number from 1 to 100} end repeat set sDat to current date –ソート時間計測(開始時刻) –item 2をPrimary key、item 3とitem 4をサブキーにして降順ソート set resList to multiKeySortDescending(aList of orig, {2, 3, 4}) of multiKeySort set eDat to current date –ソート時間計測(終了時刻) return (eDat – sDat) –複数キーによるソート script multiKeySort script spd property bList : {} –1次キーでソートした結果が入る property cList : {} –1次キーでソートした結果のうち、1次キーで同じ値が連続する範囲が入る {{1,3},{10,20}} property dList : {} –2次キーで再ソートする対象の一部のリストが入る(ワーク用) property eList : {} –2次キーで再ソートした結果のリストが入る(ワーク用) end script –複数キー(Primary, Secondary……)による降順ソート。キーは指定用のリストに入れる –falseが返ってきたらエラー on multiKeySortDescending(aList, keyList) –Initialize –set aList of spd to {} set bList of spd to {} –■■■■ ここからパラメータのチェック ■■■■ –型チェック set aLen to length of keyList if class of keyList is not equal to list then return false –キー値のリストがlistではなかった場合error end if –ソート対象の2D Listの要素数を取得 set tmpLen to length of first item of aList repeat with i in keyList if i > tmpLen then return false –キー値として指定した内容が、ソート対象のリストの要素数よりも大きかった場合error end if end repeat –キー指定内容で重複がないかチェック set dupList to detectDuplicates(keyList) of me if dupList is not equal to {} then return false –指定したキーで重複があったらerror end if –キー指定内容に0が入っていないかチェック if 0 is in keyList then return false –■■■■ パラメータのチェックここまで ■■■■ set firstKeyNo to first item of keyList –1次キーで2D Listをソート(降順) set bList of spd to shellSortListDescending(aList, firstKeyNo) of me –複数キーによるソート検証および実行ループ repeat with iii from 1 to aLen – 1 set cList of spd to {} set dList of spd to {} set eList of spd to {} –n次キーの値が連続する箇所を探す set curData to missing value set sucF to false –データ連続箇所検出中フラグ(false=非連続、true=連続中) set biginItem to 0 set endItem to 0 set itemC to 0 repeat with i in bList of spd set thisData to item (item iii of keyList) of i –n次キー –現在の値と前の値が等しい(連続箇所を検出した、あるいは連続箇所の中にいる) if curData = thisData then if sucF = false then set biginItem to itemC set sucF to true else if sucF = true then –連続箇所の検索継続中、何もしない end if else –現在の値と前の値が等しくない(連続していない、あるいは連続箇所の末尾を検出した) if sucF = true then set the end of cList of spd to {biginItem, itemC} set sucF to false end if set curData to thisData end if set itemC to itemC + 1 end repeat –n次キーの連続状態の検出中のままリスト末尾に来た場合には、最終データを出力する if sucF = true and curData = thisData then set the end of cList of spd to {biginItem, itemC} end if –n次キーによる重複箇所がない場合には、n次キーによるソート結果をそのまま返す if cList of spd = {} then return bList of spd end if –n+1次キーによる部分ソートし直し repeat with i in cList of spd set {tmpB, tmpE} to i copy items tmpB thru tmpE of (bList of spd) to (dList of spd) set (eList of spd) to shellSortListDescending((dList of spd), (item (iii + 1) of keyList)) of me set tmpCounter to 1 repeat with ii from tmpB to tmpE copy item tmpCounter of (eList of spd) to item ii of (bList of spd) set tmpCounter to tmpCounter + 1 end repeat end repeat end repeat return (bList of spd) end multiKeySortDescending –リスト中から重複項目をリストアップする on detectDuplicates(aList) set aCount to length of aList set duplicationList to {} repeat aCount times set anItem to contents of (first item of aList) set aList to rest of aList if anItem is in aList then set the end of duplicationList to anItem end if end repeat return duplicationList end detectDuplicates –シェルソートで入れ子のリストを降順ソート on shellSortListDescending(aSortList, aKeyItem) 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 (contents of item aKeyItem of (oBj’s list’s item (j – gap + 1)) < item aKeyItem of 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 shellSortListDescending end script |
(Visited 28 times, 1 visits today)