Re: Sort a List with Integers & Letters ( Reverse Speed Results When Using TEXT)
Re: Sort a List with Integers & Letters ( Reverse Speed Results When Using TEXT)
- Subject: Re: Sort a List with Integers & Letters ( Reverse Speed Results When Using TEXT)
- From: Bill Hernandez <email@hidden>
- Date: Thu, 12 Apr 2007 00:33:41 +0000
(*
Nigel,
I ran some further tests today, and was really surprised at the
outcome...
Here's the scenario :
I had 11 windows open in BBEdit, two were untitled 3, and untitled
4, the rest had been saved and had files associated with them.
I wanted to write a little script to save my session, with aliases to
the files I was working on prior to quitting, so when I open BBedit
the next day it will launch all the previous evenings documents.
In the process of doing this I ran the following script (down at
the bottom):
Nigel,
I just ran some more tests and once again was surprised at how wrong
my initial assumptions were..
New Conclusions :
The original tests I ran the other day showed when sorting 1000
random numbers whose value was between (1 and 1000)
MERGE_SORT was absolutely lightning quick
with QUICK_SORT in a distant second place, and
ASCII_SORT in an even more distant 3rd place, out at the far end of
the galaxy
ran the comparisons for 500, and 1000 items in the random list
MERGE_SORT(aList, 1, -1) --> (for 500 -> 0.132 seconds), (for 1000 -
> 0.303 seconds)
QUICK_SORT(aList, 1, -1) --> (for 500 -> 0.899 seconds), (for 1000 ->
2.629 seconds)
ASCII_SORT(aList) --> (for 500 -> 34.793 seconds), (for 1000 ->
245.098 seconds)
In the process of sorting some text paths (11 to 14 paths) ranging
in length between 123 and 178 characters the reverse has come to pass.
How BIZARRE!
As the length of the strings increase MERGE_SORT absolutely dies...
and adding a few more strings really kills it...
Amazingly QUICK_SORT is just a hair faster than ASCII_SORT, and they
are both much faster than MERGE_SORT
Thanks for again for posting the MERGE_SORT(...)
Best Regards,
Bill Hernandez
Plano, Texas
HERE ARE THE RESULTS
PRIOR TO SORTING
temp.txt................................
HardDisk:Users:dabney:user_scripting:user:
400_AS_Studio:current_projects::temp.txt
bb_insert_clipping.txt..................
HardDisk:Users:dabney:user_scripting:user:
400_AS_Studio:current_projects::bb_insert_clipping.txt
write_to_new_dirs.txt...................
HardDisk:Users:dabney:user_scripting:user:
400_AS_Studio:current_projects::write_to_new_dirs.txt
results_01.txt..........................
HardDisk:Users:dabney:user_scripting:user:
400_AS_Studio:current_projects::results_01.txt
PosixPath to MacPath.txt................
HardDisk:Users:dabney:user_scripting:user:
400_AS_Studio:current_projects::PosixPath to MacPath.txt
explore_handlers_main.txt...............
HardDisk:Users:dabney:user_scripting:user:
400_AS_Studio:current_projects::explore_handlers_main.txt
explore_handlers.txt....................
HardDisk:Users:dabney:user_scripting:user:
400_AS_Studio:current_projects::explore_handlers.txt
bb_include_test.txt.....................
HardDisk:Users:dabney:user_scripting:user:
400_AS_Studio:current_projects::bb_include_test.txt
bb_GetOpenWindowList.txt................
HardDisk:Users:dabney:user_scripting:user:
400_AS_Studio:current_projects::bb_GetOpenWindowList.txt
convert_script_to_pieces.txt.........
HardDisk:Users:dabney:user_scripting:user:
400_AS_Studio:current_projects::convert_script_to_pieces.txt
add_to_list.txt.........................
HardDisk:Users:dabney:user_scripting:user:
400_AS_Studio:current_projects::add_to_list.txt
AFTER SORTING
add_to_list.txt.........................
HardDisk:Users:dabney:user_scripting:user:
400_AS_Studio:current_projects::add_to_list.txt
bb_GetOpenWindowList.txt................
HardDisk:Users:dabney:user_scripting:user:
400_AS_Studio:current_projects::bb_GetOpenWindowList.txt
bb_include_test.txt.....................
HardDisk:Users:dabney:user_scripting:user:
400_AS_Studio:current_projects::bb_include_test.txt
bb_insert_clipping.txt..................
HardDisk:Users:dabney:user_scripting:user:
400_AS_Studio:current_projects::bb_insert_clipping.txt
convert_script_to_pieces.txt.........
HardDisk:Users:dabney:user_scripting:user:
400_AS_Studio:current_projects::convert_script_to_pieces.txt
explore_handlers_main.txt...............
HardDisk:Users:dabney:user_scripting:user:
400_AS_Studio:current_projects::explore_handlers_main.txt
explore_handlers.txt....................
HardDisk:Users:dabney:user_scripting:user:
400_AS_Studio:current_projects::explore_handlers.txt
PosixPath to MacPath.txt................
HardDisk:Users:dabney:user_scripting:user:
400_AS_Studio:current_projects::PosixPath to MacPath.txt
results_01.txt..........................
HardDisk:Users:dabney:user_scripting:user:
400_AS_Studio:current_projects::results_01.txt
temp.txt................................
HardDisk:Users:dabney:user_scripting:user:
400_AS_Studio:current_projects::temp.txt
write_to_new_dirs.txt...................
HardDisk:Users:dabney:user_scripting:user:
400_AS_Studio:current_projects::write_to_new_dirs.txt
ASort 11 --> 0.051 seconds -- ASCII_SORT
QSort 11 --> 0.056 seconds -- QUICK_SORT
MSort 11 --> 4.723 seconds -- MERGE_SORT
ASort 11 --> 0.045 seconds
QSort 11 --> 0.038 seconds
MSort 11 --> 4.399 seconds
ASort 11 --> 0.047 seconds
QSort 11 --> 0.037 seconds
MSort 11 --> 4.293 seconds
ASort 11 --> 0.053 seconds
QSort 11 --> 0.038 seconds
MSort 11 --> 4.392 seconds
ASort 11 --> 0.045 seconds
QSort 11 --> 0.037 seconds
MSort 11 --> 4.231 seconds
ASort 11 --> 0.045 seconds
QSort 11 --> 0.04 seconds
MSort 11 --> 4.214 seconds
ASort 11 --> 0.045 seconds
QSort 11 --> 0.037 seconds
MSort 11 --> 4.374 seconds
ASort 11 --> 0.048 seconds
QSort 11 --> 0.041 seconds
MSort 11 --> 4.239 seconds
ASort 11 --> 0.044 seconds
QSort 11 --> 0.037 seconds
MSort 11 --> 4.347 seconds
ASort 11 --> 0.044 seconds
QSort 11 --> 0.04 seconds
MSort 11 --> 4.392 seconds
*)
HERE"S THE DEMO PROGRAM, IT REQUIRES SEVERAL BBEDIT WINDOWS OPEN
-- +---------+---------+---------+---------+---------+---------
+---------+---------+
property bh_msg_display_list_title : "Sample Text Message -> Display
List..."
property bh_msg_display_list_button_ok : "Continue..."
property bh_msg_display_list_button_cancel : "-------->"
property bh_delim_text : ":"
property bh_delim_posix : "/"
property bh_delim_paragraph : return
-- +---------+---------+---------+---------+---------+---------
+---------+---------+
property temp_dir : (path to temporary items folder from user domain)
as text
property g_counter : 0
-- +---------+---------+---------+---------+---------+---------
+---------+---------+
on run
set g_counter to g_counter + 1
set filler to
".......................................................................
........."
tell application "BBEdit"
set aWindow to get every text window
set str to ""
repeat with thisWindow in aWindow
select thisWindow
set w_ref to text window 1
set d_ref to text document 1 of w_ref
set w_props to get properties of d_ref
set w_name to (characters 1 thru 40 of (name of w_props & filler))
as string
if (file of w_props = missing value) then
set str to str & w_name & return
else
set str to str & w_name & space & (file of w_props as string) &
return
end if
end repeat
-- Get rid of the last carriage return, to avoid an empty line
set aResults to (items 1 thru -2 of (get paragraphs of str))
set NoOfItems to count of aResults
set res_str to ""
repeat 10 times
set aList to aResults
set t to (GetMilliSec)
tell me to set aList to bh_ASCII_Sort(aList) -- Sort all items of
aList
set T1 to "ASort " & NoOfItems & " --> " & ((GetMilliSec) - t) /
1000 & " seconds " --> (for 11 paths -> .077 seconds)
set aList to aResults
set t to (GetMilliSec)
tell me to set aList to bh_QSort(aList, 1, -1) -- Sort items 1
thru -1 of aList
set T2 to "QSort " & NoOfItems & " --> " & ((GetMilliSec) - t) /
1000 & " seconds " --> (for 11 paths -> .139 seconds)
set aList to aResults
set t to (GetMilliSec)
tell me to bh_Merge_Sort(aList, 1, -1) -- Sort items 1 thru -1 of
aList
aList
set T3 to "MSort " & NoOfItems & " --> " & ((GetMilliSec) - t) /
1000 & " seconds " --> (for 11 paths -> 3.972 seconds),
set res_str to res_str & T1 & return & T2 & return & T3 & return &
return
end repeat
display dialog temp_dir
set temp_file to quoted form of (POSIX path of temp_dir) &
"results_" & (characters -2 thru -1 of ("00" & g_counter) as string)
& ".txt"
set runCmd to "echo " & quoted form of (str & return & res_str) & "
> " & temp_file
do shell script runCmd
set runCmd to "open " & temp_file
do shell script runCmd
set str_prompt to "TODAY IS : " & my bh_date_GetFullDate(current
date) -- "User Message..."
choose from list aList ¬
with title bh_msg_display_list_title ¬
with prompt str_prompt ¬
OK button name bh_msg_display_list_button_ok ¬
cancel button name bh_msg_display_list_button_cancel ¬
with multiple selections allowed and empty selection allowed
end tell
end run
-- +---------+---------+---------+---------+---------+---------
+---------+---------+
on bh_Merge_Sort(theList, l, r)
(*
REQUIRES :
GetMilliSec.osax (if you want to track execution time, otherwise
comment it out...)
CALLED :
set t to (GetMilliSec)
bh_Merge_Sort(aList, 1, -1) -- Sort items 1 thru -1 of aList
aList
display dialog ((GetMilliSec) - t) / 1000 --> (for 500 -> .132
seconds), (for 1000 -> .303 seconds)
*)
script o
property lst : theList
property extract : missing value
on msort(l, r)
set m1 to (l + r) div 2
set m2 to m1 + 1
if (m1 - l > 1) then
msort(l, m1)
else
set leftVal to item l of my lst
set rightVal to item m1 of my lst
if (rightVal < leftVal) then
set item l of my lst to rightVal
set item m1 of my lst to leftVal
end if
end if
if (r - m2 > 1) then
msort(m2, r)
else if (r > m2) then
set leftVal to item m2 of my lst
set rightVal to item r of my lst
if (rightVal < leftVal) then
set item m2 of my lst to rightVal
set item r of my lst to leftVal
end if
end if
set my extract to items l thru r of my lst
set leftIdx to 1
set leftLen to m2 - l
set rightIdx to leftLen + 1
set extractLen to r - l + 1
set leftVal to beginning of my extract
set rightVal to item rightIdx of my extract
repeat with i from l to r
if (rightVal < leftVal) then
set item i of my lst to rightVal
if (rightIdx < extractLen) then
set rightIdx to rightIdx + 1
set rightVal to item rightIdx of my extract
else
repeat with i from (i + 1) to r
set item i of my lst to item leftIdx of my extract
set leftIdx to leftIdx + 1
end repeat
exit repeat
end if
else
set item i of my lst to leftVal
if (leftIdx < leftLen) then
set leftIdx to leftIdx + 1
set leftVal to item leftIdx of my extract
else
exit repeat
end if
end if
end repeat
end msort
end script
set listLen to (count theList)
if (listLen > 1) then
if (l < 0) then set l to listLen + l + 1
if (r < 0) then set r to listLen + r + 1
if (r = l) then
else
if (l > r) then
set temp to l
set l to r
set r to temp
end if
o's msort(l, r)
end if
end if
return -- nothing
end bh_Merge_Sort
-- +---------+---------+---------+---------+---------+---------
+---------+---------+
on bh_ASCII_Sort(my_list)
set the index_list to {}
set the sorted_list to {}
set counter to 0
--=counter
repeat (the number of items of my_list) times
set counter to counter + 1
set the low_item to ""
repeat with i from 1 to (number of items of my_list)
if i is not in the index_list then
set this_item to item i of my_list as text
if the low_item is "" then
set the low_item to this_item
set the low_item_index to i
else if this_item comes before the low_item then
set the low_item to this_item
set the low_item_index to i
end if
end if
end repeat
set the end of sorted_list to the low_item
set the end of the index_list to the low_item_index
end repeat
return the sorted_list
end bh_ASCII_Sort
-- +---------+---------+---------+---------+---------+---------
+---------+---------+
on bh_QSort(aArray, start_val, no_of_elements)
if (no_of_elements = -1) then
set no_of_elements to count of aArray
end if
set i to start_val
set j to no_of_elements
set v to item ((start_val + no_of_elements) div 2) of aArray -- pivot
repeat while (j > i)
repeat while (item i of aArray < v)
set i to i + 1
end repeat
repeat while (item j of aArray > v)
set j to j - 1
end repeat
if (not i > j) then
tell aArray to set {item i, item j} to {item j, item i} -- swap
set i to i + 1
set j to j - 1
end if
end repeat
if (start_val < j) then set aArray to bh_QSort(aArray, start_val, j)
if (no_of_elements > i) then set aArray to bh_QSort(aArray, i,
no_of_elements)
return aArray
end bh_QSort
-- +---------+---------+---------+---------+---------+---------
+---------+---------+
on bh_date_GetFullDate(theDate)
if ((theDate = "") or (theDate = missing value)) then
set theDate to current date
end if
set DS to date string of (theDate)
set TS to time string of (theDate)
tell application "Finder"
set TS to ((get characters 1 thru -7 of TS) & (get characters -3
thru -1 of TS)) as string
end tell
return (DS & " (" & TS & ")")
end bh_date_GetFullDate
-- +---------+---------+---------+---------+---------+---------
+---------+---------+
_______________________________________________
Do not post admin requests to the list. They will be ignored.
AppleScript-Users mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
Archives: http://lists.apple.com/archives/applescript-users
This email sent to email@hidden