|
Super Fast String Sorts Update(30/03/2007)
|
Email
|
| Submitted on: |
3/30/2007 1:28:28 PM |
| By: |
Tai Chi Minh Ralph Eastwood
|
| Level: |
Intermediate |
| User Rating: |
By 19 Users |
| Compatibility: |
VB 5.0, VB 6.0 |
| Views: |
17210 |
|
(About the author) |
|
|
|
I have implemented two of the algorithms 'popular' MSD Radix Sorts
based on the implementations done by Peter M. McIlroy and Keith Bostic in
their paper Engineering Radix Sort. Of the techniques used were VBSpeed techniques
such as safearray 'hacking' and others.
These algorithms go extremely fast, about 10x faster than a standard iterative version of
a QuickSort algorithm. This is shown the the accompanying benchmark...
Please compile to native with all advanced options checked to get best results, but I think it performs pretty well in IDE as well.
Updated with TriQuickSort instead of QuickSort.
Updated with TriQuickSort fixed+2x faster
Updated with TriQuickSort Non-Recursive, rd's strSwapTable, Export to CSV
Updated with some GUI changes and Ulli's algos
|
 |
| |
|
 Download code
Note: Due to the size or complexity of this submission, the author has submitted it as a .zip file to shorten your download time. Afterdownloading it, you will need a program like Winzip to decompress it.Virus note:All files are scanned once-a-day by Planet Source Code for viruses, but new viruses come
out every day, so no prevention program can catch 100% of them. For your own safety, please:
- Re-scan downloaded files using your personal virus checker before using it.
- NEVER, EVER run compiled files (.exe's, .ocx's, .dll's etc.)--only run source code.
- Scan the source code with Minnow's Project Scanner
If you don't have a virus scanner, you can get one at many places on the net
including:McAfee.com
|
Terms of Agreement:
By using this code, you agree to the following terms...
- You may use
this code in your own programs (and may compile it into a program and distribute it in compiled format for languages that allow it) freely and with no charge.
- You MAY NOT redistribute this code (for example to a web site) without written permission from the original author. Failure to do so is a violation of copyright laws.
- You may link to this code from another website, but ONLY if it is not wrapped in a frame.
- You will abide by any additional copyright restrictions which the author may have placed in the code or code's description.
|
Other 3 submission(s) by this author
|
|
Report Bad Submission
|
Your Vote
|
| |
Other User Comments
|
 1/2/2007 2:43:54 PM: Steppenwolfe
Looks good. Did not get the wider variance in speeds between algos you suggest though. Also, qsort algo in example is poorly optimized, (for loop, redim preserve, should shuffle pointers not strings, etc), so a better comparison, (or a fairer one, would be with an optimized triquicksort, like in one of RDE's examples.
(If this comment was disrespectful, please report it.)
|
1/2/2007 2:57:28 PM: Tai Chi Minh Ralph Eastwood
I'm considering releasing my sorting functions for long integers written in assembly, which goes a few times faster than any vb equivalent :D.
(If this comment was disrespectful, please report it.)
|
1/2/2007 11:03:26 PM: David J. Fritts
I'd like to see your asm version. It'd probably be just as fast using an asm dll vs asm tricks I'd think. Just about the same. I like not having dependencies, but it'd also be a bit more complex. I would hope you have a highly optimized quicksort for asm, because its so easy to optimize on that low-level.
(If this comment was disrespectful, please report it.)
|
1/3/2007 12:19:24 AM: Tai Chi Minh Ralph Eastwood
Thanks Steppenwolfe, will look into that. Btw, Herman Hesse or the band?
(If this comment was disrespectful, please report it.)
|
1/3/2007 12:20:14 AM: Tai Chi Minh Ralph Eastwood
Yea somehow I managed to get an old version of my quicksort, - I Ihad a pointer version somewhere lol.
(If this comment was disrespectful, please report it.)
|
1/3/2007 9:29:52 AM: Steppenwolfe
Hesse, band was good too.. StringX = StringY, copying strings in this way is very slow in vb, and to be avoided whenever possible. Also, Do loops with a counter are faster then For loops, (and Do/Until is usually faster then Do While). I have a bench project I used on various versions of triquicksort for my listview, and a couple typelibs that might be usefull here, email me if you want it.
(If this comment was disrespectful, please report it.)
|
1/3/2007 10:38:13 AM: RB
In the module MQsortString.bas is an undefined variable "lbx" this will be "0" when the program executes.
Use "OPTION EXPLICIT" would have found this problem. What should the variable really be?
(If this comment was disrespectful, please report it.)
|
1/3/2007 3:11:12 PM: Tai Chi Minh Ralph Eastwood
Yes I usually have Option Explicit, but copying and pasting is not recommended lol.
I need to fix it, will do in about half an hour.
(If this comment was disrespectful, please report it.)
|
1/4/2007 1:28:58 AM: Tai Chi Minh Ralph Eastwood
I will update more changes sometime later, Steppenwolf, your ideas look good :)
(If this comment was disrespectful, please report it.)
|
2/6/2007 3:30:53 AM: pietro ing. cecchi
thanks Tai Chi Minh!
this new sort looks promising...:)
5 from me
(If this comment was disrespectful, please report it.)
|
2/8/2007 3:40:29 AM: Rde
Hi Tai Chi/Ralph
As you claim these algos are truly much faster than any of my algos!
Well worth 5 globes. Keep it up.
Happy coding,
Rd :)
(If this comment was disrespectful, please report it.)
|
3/29/2007 1:48:03 PM: ULLI
This screenshot seems a bit misleading because for larger data volumes the black benchmark beats all others by a factor of almost two *smile*
(If this comment was disrespectful, please report it.)
|
3/30/2007 12:21:48 AM: Tai Chi Minh Ralph Eastwood
I do not seem to get that?
(If this comment was disrespectful, please report it.)
|
3/30/2007 1:25:46 AM: Tai Chi Minh Ralph Eastwood
Your benchmark appears to be in IDE mode, i grant that your IDE-mode benchmarking is far faster than mine. However, for me, native compilation of algorithms is faster than yours.
(If this comment was disrespectful, please report it.)
|
3/30/2007 1:29:23 AM: Tai Chi Minh Ralph Eastwood
I've just tested it again, i find i get different results on different computers, how strange.
(If this comment was disrespectful, please report it.)
|
3/30/2007 4:23:26 AM: ULLI
@Ralph - sometimes operand alignment is a key speed factor. And different CPUs may behave differently depending on instruction queue lengths, instruction overlap or branch predition.
(If this comment was disrespectful, please report it.)
|
3/30/2007 7:55:58 AM: Tai Chi Minh Ralph Eastwood
Ok, i worked out the problem, i was using keysize = 1 on your algorithm. I found out when I put in the sort tests and yours wasn't sorting the data terribly well :). But now your radix sort is actually slower than your quickie sort. I will upload my new version shortly.
(If this comment was disrespectful, please report it.)
|
3/30/2007 9:29:14 AM: ULLI
@Ralph
in GenerateRandomStrings try this:
Mid$(asOutString(i), j, 1) = Chr$(Int(Rnd * 256))
(If this comment was disrespectful, please report it.)
|
3/30/2007 9:33:20 AM: ULLI
and if that doesn't work try this:
Mid$(asOutString(i), j, 1) = Chr$(Int(Rnd * 255) + 1)
(If this comment was disrespectful, please report it.)
|
1/17/2008 4:46:19 AM: Rde
Hi again Ralph
After taking another look at your *very fast* optimized TriQuickSort of Philippe Lords I see a simple fix for vb's variable array base indices.
Change this line in all sorting subs in CTriQuickSort class:
' Get the String array ptr
m_saStringPtrArrayHeader.pvData = VarPtr(sArray(0))
To this:
' Get the ptr to the first String descriptor
m_saStringPtrArrayHeader.lLbound = lLowerBound
m_saStringPtrArrayHeader.pvData = VarPtr(sArray(lLowerBound))
Happy coding,
Rd :)
(If this comment was disrespectful, please report it.)
|
Add Your Feedback
Your feedback will be posted below and an email sent to
the author. Please remember that the author was kind enough to
share this with you, so any criticisms must be stated politely, or they
will be deleted. (For feedback not related to this particular code, please
click here instead.)
To post feedback, first please login.
|
