• Open Menu Close Menu
  • Apple
  • Shopping Bag
  • Apple
  • Mac
  • iPad
  • iPhone
  • Watch
  • TV
  • Music
  • Support
  • Search apple.com
  • Shopping Bag

Lists

Open Menu Close Menu
  • Terms and Conditions
  • Lists hosted on this site
  • Email the Postmaster
  • Tips for posting to public mailing lists
Re: Sort a List with Integers & Letters ( Reverse Speed Results When Using TEXT)
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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
  • Follow-Ups:
    • Re: Sort a List with Integers & Letters ( Reverse Speed Results When Using TEXT)
      • From: "Nigel Garvey" <email@hidden>
References: 
 >Re: Sort a List with Integers & Letters (From: "Nigel Garvey" <email@hidden>)

  • Prev by Date: Re: Scripting Filemaker 8.5.. (HEEELP)
  • Next by Date: FMP 8.5 and AppleScript
  • Previous by thread: Re: Sort a List with Integers & Letters
  • Next by thread: Re: Sort a List with Integers & Letters ( Reverse Speed Results When Using TEXT)
  • Index(es):
    • Date
    • Thread