与えられた1次元配列のデータのすべての順列組み合わせパターンを計算し、そのとおりに配列を並べて連結した文字列を、すべての順列組み合わせパターンについて生成して返す(Permutations)AppleScriptです。
初版ではありもののサブルーチンを組み合わせて、検証を行うには十分なものでした(v2)。ただし、本来その用途に作成したものではないルーチンを寄せ集めて作ったので、組み合わせ数が増えると処理時間がかかりすぎるきらいがありました。
そこで、こうした処理(Permutations)を英語でどう呼ぶのかを調べ、AppleScriptの実装例を調べたら、灯台下暗し。MacScripter.netにありました。
ただし、そのままではいまひとつ使いにくかったので、きちんと組み合わせた文字列を1次元配列で返すように組んでみたところ、オリジナル版よりは処理時間はかかっていますが、初版からくらべると大幅に処理速度とメモリ使用効率が改善されました。
MacScripter.net掲載サンプル処理結果:{{“A”, “T”, “G”, “C”}….}
本Scriptの処理結果:{“ATGC”, “ATCG”…..}
4要素の順列組み合わせ計算:5倍速
5要素の順列組み合わせ計算:10倍速
6要素の順列組み合わせ計算:30倍速
7要素の順列組み合わせ計算:67倍速
8要素の順列組み合わせ計算:(計測不能)
というように、大規模データになればなるほど高速化の度合いが高くなります。AppleScriptにしては大規模データを扱う演算なので、Cocoaの機能を積極的に利用することで高速化を行なっています。
開発機として用いているMacBook Pro 2012 Retina(Core i7 2.6GHz)と、MacBook Pro 13 2017 (Dual Thunderbolt)で処理時間を計測してみたところ、2012のMBPのほうがわずかに高速でした。
AppleScript名:与えられた文字列の1D Listのすべての順列組み合わせパターン文字列を返す v3.scptd |
— 2014-10-06 Original By Nigel Garvey@macscripter.net — 2019-06-19 Modified By Takaaki Naganoya use AppleScript version "2.4" use scripting additions use framework "Foundation" script spdPerm property permutations : missing value end script on run –Test by MacBook Pro 2012 Retina Core i7 2.6GHz –set theList to {"A", "T", "G", "C", "1"} –0.05 secs (5 digits) 120 items. –set theList to {"A", "T", "G", "C", "1", "2"} –0.21secs (6 digits) 720 items. set theList to {"A", "T", "G", "C", "1", "2", "3"} –1.44 secs (7 digits) 5,040 items. –set theList to {"A", "T", "G", "C", "1", "2", "3", "4"} –11.54 secs (8 digits) 40,320 items. –set theList to {"A", "T", "G", "C", "1", "2", "3", "4", "5"} –107.27 secs (9 digits) 362,880 items. set aRes to permute(theList) of me return length of aRes end run on permute(theList as list) set theArray to current application’s NSMutableArray’s arrayWithArray:theList set (permutations of spdPerm) to current application’s NSMutableArray’s array() prmt(theArray, 0, (count theList) – 1) –Return AppleScript string list set aFinishArray to current application’s NSMutableArray’s new() set anEnum to (permutations of spdPerm)’s objectEnumerator() repeat set aValue to anEnum’s nextObject() if aValue = missing value then exit repeat set aStr to aValue’s componentsJoinedByString:"" (aFinishArray’s addObject:aStr) end repeat return aFinishArray as list end permute on prmt(theArray, theStart as number, theEnd as number) if (theStart = theEnd) then (permutations of spdPerm)’s addObject:theArray else repeat with x from theStart to theEnd set theCopy to theArray’s mutableCopy() –swap if (x > theStart) then (theCopy’s exchangeObjectAtIndex:theStart withObjectAtIndex:x) prmt(theCopy, theStart + 1, theEnd) end repeat end if end prmt |