pdqsort
nytm-spelling-bee
| pdqsort | nytm-spelling-bee | |
|---|---|---|
| 9 | 2 | |
| 2,288 | 32 | |
| - | - | |
| 0.0 | 0.0 | |
| 5 months ago | about 5 years ago | |
| C++ | C++ | |
| zlib License | GNU General Public License v3.0 or later |
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
pdqsort
- Pattern-Defeating Quicksort (Pdqsort)
-
Faster sorting algorithm
I found that this exists: https://github.com/orlp/pdqsort
-
How sorting algorithms work
Their sort_unstable algorithm is based on this pattern-defeating quicksort.
-
Timsort – the fastest sorting algorithm you’ve never heard of
Closely related is pattern defeating quicksort ( https://github.com/orlp/pdqsort ), which adapts quicksort to take advantage of sorted runs. I've adapted a few quicksorts to pdqsort and seen good speedups (as people were often sorting partially sorted data)
Basically: Timsort is to mergesort as pdqsort is to quicksort
- I tried creating a sorting algorithm in C language.
- Do Low-Level Optimizations Matter?
-
Discussion Thread
I was thinking of optimal C++ over native types. I just spoke up because if your intuition of quicksort is that 50k elements should take 20ms you’re drastically underestimating computer performance. They’re crazy fast and optimized sorting algorithms are downright scary.
-
Beating Up on Qsort (2019)
Just for fun, I added pdqsort to the benchmark:
https://github.com/orlp/pdqsort
Here are some of the results on an Ivy Bridge hackintosh:
size, qsort, inline, sort, stable_sort, pdqsort, radix7 -
Which sorting algorithm did you implement in your programming language?
sort_unstable is a pattern-defeating quicksort (https://github.com/orlp/pdqsort) added with RFC#1884 (https://github.com/rust-lang/rfcs/pull/1884).
nytm-spelling-bee
- HiFive Unmatched – A RISC-V Linux development platform
-
Do Low-Level Optimizations Matter?
If you are designing a sorting algorithm component for production, it is critical to take into account all the blips and wrinkles that real components will face.
But when you are investigating how and why your CPU has the performance characteristics it has evolved, all those complications directly interfere with learning. The goal here was not to make a production-grade sorting tool; it was to understand what affects performance, using the sorting problem as a microscope.
The method is generally useful. Some years back I spent months refining a one-page program[1] to generate a list of word puzzles. After the first day, the list of puzzles was of no interest, but refining the means to produce it faster taught me a great deal.
[1] https://github.com/ncm/nytm-spelling-bee
What are some alternatives?
fluxsort - A fast branchless stable quicksort / mergesort hybrid that is highly adaptive.
riscv-bitmanip - Working draft of the proposed RISC-V Bitmanipulation extension
American Fuzzy Lop - american fuzzy lop - a security-oriented fuzzer
riscv-sbi-doc - Documentation for the RISC-V Supervisor Binary Interface
quadsort - Quadsort is a branchless stable adaptive mergesort faster than quicksort.
ips4o - In-place Parallel Super Scalar Samplesort (IPS⁴o)
ZBar - Clone of the mercurial repository http://zbar.hg.sourceforge.net:8000/hgroot/zbar/zbar
ZXing - ZXing ("Zebra Crossing") barcode scanning library for Java, Android
C++ Format - A modern formatting library
ZPM - The C++ package manager based on premake5
stb - stb single-file public domain libraries for C/C++
UNITS - a compile-time, header-only, dimensional analysis and unit conversion library built on c++14 with no dependencies.