●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
