Timeline for My BRESort adaptive sorting engine in C
Current License: CC BY-SA 4.0
24 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 14 at 20:16 | comment | added | LazyCauchPotato | With a proper TimSort implementation, on sequential data, TimSort clearly wins: 333μs vs 667μs full 2.0x faster at 50K elements But on random and real-world patterns, BRESort is on top. Test I ran: True random data: BRESort 1.26-1.80x faster GPS coordinates: BRESort 2.00x faster (6ms vs 12ms) Database timestamps: BRESort 2.00x faster (6ms vs 12ms) Sensor data: BRESort 1.56x faster (9ms vs 14ms) E-commerce prices: BRESort 2.00x faster (6ms vs 12ms) | |
| Oct 14 at 19:31 | comment | added | LazyCauchPotato | I should've been more specific about the qsort baseline. I benchmarked against what I found to be the fastest implementation in my environment. Do you recommend any particular qsort implementation that would make for a more objective comparison? And you're absolutely correct about small inputs, that was more of a proof of concept for the entropy analysis and bitwise extraction approach. The current latest version handles 32/64-bit integers and floating-point data, where algorithm selection actually matters. | |
| Oct 13 at 22:49 | comment | added | David Conrad | Frame challenge: how does it compare to TimSort? | |
| Oct 13 at 22:08 | comment | added | John Bollinger |
Nobody much cares about the performance of sorting small inputs. Pretty much any algorithm will do. Even Bubble Sort, for very small inputs. And for elements of type char, there is little reason for any choice other than counting sort. Especially not if choosing anything else involves first expending a significant fraction of the time that a counting sort would require, as your analysis phase does.
|
|
| Oct 13 at 21:54 | comment | added | John Bollinger |
"It achieves 3.6-4.2x speedup over stdlib qsort" -- there is no single "stdlib qsort". Your sort may outperform the qsort of your particular C implementation, but that's not the same thing.
|
|
| Oct 13 at 0:43 | comment | added | mdfst13 | I have an Edit Tags button, but that may be a privilege. Before you get that, you can use the Edit button to edit things including the tags (which are towards the bottom of that interface). | |
| Oct 13 at 0:42 | history | edited | mdfst13 |
edited tags
|
|
| Oct 11 at 18:09 | comment | added | LazyCauchPotato | I'm new to the platform, still getting acquainted with it. Unfortunately don't know how to change the tags after the question has been posted. Sure the more appropriate are something like: adaptive-algorithms algorithm-selection performance-optimization | |
| Oct 11 at 17:41 | comment | added | LazyCauchPotato | No, you're not missing anything - you're absolutely right! BRESort (Bitwise Relationship Extraction Sort) uses intelligent algorithm\engine selection based on data pattern analysis, not genetic algorithms. I've removed the incorrect tag. The system analyzes bit patterns, entropy, and data structure to choose the optimal sorting algorithm (insertion sort, quicksort, radix sort, etc.) for each specific dataset. The full version is coming soon - it's capable of analyzing 32/64-bit integers and floating-point data with the same intelligent approach. | |
| Oct 11 at 15:07 | answer | added | chux | timeline score: 4 | |
| Oct 11 at 12:20 | answer | added | toolic | timeline score: 4 | |
| Oct 11 at 12:20 | history | edited | toolic | CC BY-SA 4.0 |
added 5 characters in body
|
| Oct 11 at 7:25 | history | became hot network question | |||
| Oct 11 at 7:17 | comment | added | LazyCauchPotato | Oh...you're absolutely right about the insertion sort bug, I accidentally left identical code in both branches. The manual unrolling should actually optimize for tiny arrays. Regarding BRESort_byte() naming: yes, I chose bytes as the starting point because counting sort is particularly effective there, but the adaptive selection concept could definitely extend to other types. I have already tested on float data with promissing results, it has slightly different analysis heuristics, but the core 'analyze then choose' is the same. Thanks for superb review...have a lot of fixing to do... | |
| Oct 11 at 6:50 | answer | added | greybeard | timeline score: 6 | |
| Oct 11 at 6:28 | history | edited | greybeard | CC BY-SA 4.0 |
take review direction preference out of code block
|
| Oct 11 at 4:14 | comment | added | greybeard |
Pondering the name BRESort_byte(): Do you plan to come up with routines for different keys/records?
|
|
| Oct 11 at 3:56 | comment | added | greybeard |
In bres_insertion_sort()'s Manual unrolling for small array-if-else, the controlled statements look identical.
|
|
| Oct 11 at 0:01 | history | edited | Chris | CC BY-SA 4.0 |
edited body
|
| Oct 10 at 23:55 | history | edited | LazyCauchPotato | CC BY-SA 4.0 |
added 10244 characters in body
|
| Oct 10 at 23:42 | answer | added | Chris | timeline score: 8 | |
| Oct 10 at 22:46 | history | edited | toolic | CC BY-SA 4.0 |
added 6 characters in body; edited tags; edited title
|
| S Oct 10 at 22:42 | review | First questions | |||
| Oct 10 at 22:46 | |||||
| S Oct 10 at 22:42 | history | asked | LazyCauchPotato | CC BY-SA 4.0 |