Fastest sort

Get help with using AutoHotkey (v1.1 and older) and its commands and hotkeys
mast4rwang
Posts: 141
Joined: 19 Jul 2017, 09:59

Fastest sort

15 Jan 2019, 16:52

I've read this article about sorting: https://en.wikipedia.org/wiki/Quicksort and I made some sort scripts, some using my own way, some similar to the logic of quicksort but it seems that nothing is faster than the default string sort. Here is a code from https://sites.google.com/site/ahkref/cu ... /sortarray which uses pivots to optimize sorting and still it is several times slower than using the simple method. Why is that and is it possible to sort faster than the default sort if I want to sort only numbers?

Pivoting string sort:
Spoiler

Simple method:
User avatar
FanaticGuru
Posts: 1906
Joined: 30 Sep 2013, 22:25

Re: Fastest sort

15 Jan 2019, 18:55

A sort truly implemented in AHK is never going to be as fast as a the Sort command which is implemented in C++. The Sort command is probably a Quicksort at its core.

Using the Sort command to sort an array object is mostly the time it takes to convert to a string and then convert back to an array object. The actual Sort command is probably only a fraction of the conversion time.

FG
Hotkey Help - Help Dialog for Currently Running AHK Scripts
AHK Startup - Consolidate Multiply AHK Scripts with one Tray Icon
Hotstring Manager - Create and Manage Hotstrings
[Class] WinHook - Create Window Shell Hooks and Window Event Hooks
IMEime
Posts: 750
Joined: 20 Sep 2014, 06:15

Re: Fastest sort

15 Jan 2019, 20:13

Fast...
Fast is good always.

I have met AHK because it is fast to learn.
I use AHK because it is fast to change code.
I will use AHK because it is fast to learn again when I totally forgot its command.
As you can see I do not have that kind 'fast' in my inventory.

Yes, I know AHK is slow in some case and very slow for some other cases.
If you find some nice way, tell me please, I will check it out.

I have tested fast MS Excel and fast MS Word codes.
Now, trying to test fast SQLite, but its is difficult to me...
coffee
Posts: 133
Joined: 01 Apr 2017, 07:55

Re: Fastest sort

15 Jan 2019, 23:32

FanaticGuru wrote:
15 Jan 2019, 18:55
A sort truly implemented in AHK is never going to be as fast as a the Sort command which is implemented in C++. The Sort command is probably a Quicksort at its core.
It uses qsort from maykrosoft, so YEET.

mast4rwang wrote:
15 Jan 2019, 16:52

Code: Select all

Array[pivot]
I'm gonna let someone else spoil your fun and tell you what happens when you do that :'(
mast4rwang
Posts: 141
Joined: 19 Jul 2017, 09:59

Re: Fastest sort

16 Jan 2019, 15:43

coffee wrote:
15 Jan 2019, 23:32
FanaticGuru wrote:
15 Jan 2019, 18:55
A sort truly implemented in AHK is never going to be as fast as a the Sort command which is implemented in C++. The Sort command is probably a Quicksort at its core.
It uses qsort from maykrosoft, so YEET.

mast4rwang wrote:
15 Jan 2019, 16:52

Code: Select all

Array[pivot]
I'm gonna let someone else spoil your fun and tell you what happens when you do that :'(
Let me guess.... It slows down the script? :D
This function is actually really slow even though it is posted on that website and uses pivots. I think my own sketch sorts were faster while testing:
Spoiler
But as FG wrote, if it uses c++ sort I guess there is no chance to surpass the default sort ^^
User avatar
FanaticGuru
Posts: 1906
Joined: 30 Sep 2013, 22:25

Re: Fastest sort

17 Jan 2019, 13:41

mast4rwang wrote:
16 Jan 2019, 15:43
But as FG wrote, if it uses c++ sort I guess there is no chance to surpass the default sort ^^
I assume the default sort is very good. If it is Qsort by Microsoft then it is used in thousands of programs. I imagine it has been picked over and optimized by many different people.

The only problem is that AHK uses it only for strings. It would be nice if it could sort arrays with variable dimensions where the dimension to sort on as a parameter. Other languages have this.

Ironically AHK is probably converting the string to an array to be sorted in C++.

It would be great if someone implimented this option in AHK through some Mcode or a Dll; or some other way to get a multi-dimensional array sort at C++ speed.

FG
Hotkey Help - Help Dialog for Currently Running AHK Scripts
AHK Startup - Consolidate Multiply AHK Scripts with one Tray Icon
Hotstring Manager - Create and Manage Hotstrings
[Class] WinHook - Create Window Shell Hooks and Window Event Hooks
mast4rwang
Posts: 141
Joined: 19 Jul 2017, 09:59

Re: Fastest sort

17 Jan 2019, 15:41

FanaticGuru wrote:
17 Jan 2019, 13:41
mast4rwang wrote:
16 Jan 2019, 15:43
But as FG wrote, if it uses c++ sort I guess there is no chance to surpass the default sort ^^
It would be great if someone implimented this option in AHK through some Mcode or a Dll; or some other way to get a multi-dimensional array sort at C++ speed.

FG
Yeah and share the code so everyone can help optimize it :thumbup:
coffee
Posts: 133
Joined: 01 Apr 2017, 07:55

Re: Fastest sort

18 Jan 2019, 02:41

mast4rwang wrote:
16 Jan 2019, 15:43
Let me guess.... It slows down the script? :D
xd, you are just not accessing direct memory addresses like you would in a compiled language (and maybe google's v8? i know they do some fuckery with hidden classes), i.e you are not going straight to the element, you may have to go over a few, in addition to some prechecks before. You are incurring a lookup (currently implemented as a binary search).
Anything like that implemented in autohotkey can only be compared to other autohotkey implementations. You would have to screw up on purpose to come up with a slower sorting, searching or parsing algorithm in c++ compared to something done in autohotkey.
User avatar
rommmcek
Posts: 1470
Joined: 15 Aug 2014, 15:18

Re: Fastest sort

23 Jan 2019, 12:44

@mast4rwang: I believe that your SortArray() function doesn't respect order of appearance completely (except in special cases).
I made here a bad proposal to improve it, so I deleted it!
However one of my affirmation stands: The SortArray() function isn't the fastest in all occasions!
Last edited by rommmcek on 23 Jan 2019, 21:04, edited 4 times in total.
User avatar
nnnik
Posts: 4500
Joined: 30 Sep 2013, 01:01
Location: Germany

Re: Fastest sort

23 Jan 2019, 13:14

Recommends AHK Studio

Return to “Ask for Help (v1)”

Who is online

Users browsing this forum: Descolada, garry, marypoppins_1, Rohwedder, RussF and 136 guests