Text Only | Text with Attachments

QB64.org Forum

Active Forums => QB64 Discussion => Topic started by: codeguy on January 26, 2020, 07:02:13 am

Title: Array intersection for arbitrary n numeric data
Post by: codeguy on January 26, 2020, 07:02:13 am: Your best bet for array intersection of indeterminate size arrays is to sort both and do a modified merge, as appears in the classical MergeSort algorithm or a very slow brute-force approach with unsorted data. FlashSort as it appears in my posted sorting library and test code will be your friend resulting in nearly linear constant-case performance without limitations imposed by Hashtable use for the very same purpose. Just some friendly advice. I advise against the use of QuickSort as it has terrible performance in rare but very realistic cases. I also advise against this because FlashSort is roughly 37% faster than QuickSort in all cases, sometimes even faster and needs only a bit more than n/8 auxiliary to perform its speedy numeric wizardry. Construction of the resulting intersection as I've stated is almost child's play.
Title: Re: Array intersection for arbitrary n numeric data
Post by: SMcNeill on January 26, 2020, 07:32:42 am: Somehow, this seems like an answer to somebody’s question, but I don’t know what the question was. Is this for a new version of JEOPARDY — The QB64 Edition!!
Title: Re: Array intersection for arbitrary n numeric data
Post by: Qwerkey on January 26, 2020, 07:42:52 am: Quote from: codeguy on January 26, 2020, 07:02:13 am
Construction of the resulting intersection as I've stated is almost child's play.

Oh crumbs! Do I feel an idiot! codeguy's paragraph is just a string of words which make absolutely no sense to me at all. I can only quote Tom Lehrer:

It's so simple,
So very simple
That only a child can do it!
Title: Re: Array intersection for arbitrary n numeric data
Post by: bplus on January 26, 2020, 10:11:37 am: Quote
Just some friendly advice. I advise against the use of QuickSort as it has terrible performance in rare but very realistic cases.

Hi codeguy, What realistic cases does QuickSort have terrible performance?
Title: Re: Array intersection for arbitrary n numeric data
Post by: codeguy on January 26, 2020, 08:34:25 pm: QuickSort fails to be speedy in 3 specific cases.
Highly redundant data, sorted, and array constructions where middle element is always least or greatest in the range if you're always using the middle element as your pivot. It's a LONG discussion and there are ways to construct this EASILY. This is why I recommend against using QuickSort if you do not know the data is fairly randomly arranged.

FlashSort in ALL my experience and attempts to thwart its generally stellar performance for numbers has never let me down. If you INSIST on using QuickSort, I recommend IntroSort, a mix of QuickSort, heapsort and InsertionSort, guaranteed faster than QuickSort worst case and
relatively speedy and in-place, meaning no auxiliary as is necessary for FlashSort or MergeSort. All these algorithms and then some are in my contributed sorting library.
Title: Re: Array intersection for arbitrary n numeric data
Post by: codeguy on January 26, 2020, 08:46:38 pm: https://www.qb64.org/forum/index.php?topic=530.msg3830#msg3830 (https://www.qb64.org/forum/index.php?topic=530.msg3830#msg3830)

CodeGuy Standard Sorting library.

It even does union/intersection. Cool, huh?
Edited for CORRECT link to my massive and tested library. Thanks for tolerating my lengthy technical posts.
Title: Re: Array intersection for arbitrary n numeric data
Post by: codeguy on January 26, 2020, 09:19:18 pm: Quote from: SMcNeill on January 26, 2020, 07:32:42 am
Somehow, this seems like an answer to somebody’s question, but I don’t know what the question was. Is this for a new version of JEOPARDY — The QB64 Edition!!

This was in answer to a question appearing in another topic thread which I was unable for whatever reason to respond with the explanation of one of my favorite methods to find the union and intersection of arrays.