イケッチロゴ

Applescript実験室

イケッチトップページ

作品

リンク


Applescript実験室

自作スクリプト


●N×logNとなるソートのハンドラ-4(前回のマージソートを修正)

“レコードのリストの参照”の実験結果をもとに、それをマージソートに摘要させてみた。もともとリストを合併する部分でレコードの参照を使っていたので、「若干速くなったかな」という感じです。前回のマージソートが異常に速く感じたのは、レコードのリストの参照が速いことを知らずに使っていたからでした。
今回は移植しやすいようにハンドラ内で使用する参照形式を、ハンドラの前で設定してグローバル宣言しています。そのため各ハンドラの方がハンドラを呼び出す側よりも先にきています。


--以下がマージソートのルーチンとそれに使用するレコード

global margeSortRecRef

set margeSortRec to {stackList:{}, refList:{}}

set margeSortRecRef to a reference to margeSortRec

on mergeSort(theList)

set n to 1

set i to 2

set stackList of margeSortRecRef to theList

set countTheList to count stackList of margeSortRecRef

set refList of margeSortRecRef to {}

repeat until i > countTheList

set end of refList of margeSortRecRef to merge({item (i - 1) of stackList of margeSortRecRef}, {item i of stackList of margeSortRecRef})

set i to i + 2

end repeat

repeat while n < countTheList

set i to 2

set stackList of margeSortRecRef to {}

repeat until i > (count refList of margeSortRecRef)

set end of stackList of margeSortRecRef to merge(item (i - 1) of refList of margeSortRecRef, item i of refList of margeSortRecRef)

set i to i + 2

end repeat

if (count refList of margeSortRecRef) mod 2 > 0 then set end of stackList of margeSortRecRef to item -1 of refList of margeSortRecRef

set n to n * 2

set refList of margeSortRecRef to stackList of margeSortRecRef

end repeat

set stackList of margeSortRecRef to {}

return item 1 of refList of margeSortRecRef

end mergeSort


--以下がソート済みのリストを合体させるルーチンとそれに使用するレコード

global mergeRecRef

set mergeRec to {listA:{}, listB:{}, mergeList:{}}

set mergeRecRef to a reference to mergeRec

on merge(list_1, list_2)

set mergeList of mergeRecRef to {}

if list_1 is {} then return list_2

if list_2 is {} then return list_1

set {listA of mergeRecRef, listB of mergeRecRef} to {list_1, list_2}

set {numA, numB} to {1, 1}

set {A, B} to {item 1 of listA of mergeRecRef, item 1 of listB of mergeRecRef}

repeat

if A > B then

set {end of mergeList of mergeRecRef, numB} to {B, numB + 1}

if numB > (count listB of mergeRecRef) then exit repeat

set B to item numB of listB of mergeRecRef

else

set {end of mergeList of mergeRecRef, numA} to {A, numA + 1}

if numA > (count listA of mergeRecRef) then exit repeat

set A to item numA of listA of mergeRecRef

end if

end repeat

if numA > (count listA of mergeRecRef) then

repeat until (count listB of mergeRecRef) < numB

set end of mergeList of mergeRecRef to item numB of listB of mergeRecRef

set numB to numB + 1

end repeat

else

repeat until (count listA of mergeRecRef) < numA

set end of mergeList of mergeRecRef to item numA of listA of mergeRecRef

set numA to numA + 1

end repeat

end if

set {list_1, list_2, listA of mergeRecRef, listB of mergeRecRef} to {{}, {}, {}, {}}

return mergeList of mergeRecRef

end merge


set n to {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

set numList to {}

set numListRef to a reference to numList

repeat 1000 times

set end of numListRef to (some item of n) * 10000 + (some item of n) * 1000 + (some item of n) * 100 + (some item of n) * 10 + (some item of n)

end repeat


set T to current date

repeat 1 times --速度を計測するために何回か繰り返す

mergeSort(numList)

end repeat

(current date) - T



Iketch Design Office, All Rights Recerved.