sort with custom `cmp_fn`
In Go, I can easily sort a slice with something like:
The portion
func(i, j int) bool { return my_slice[i][2] < my_slice[j][2] }
is an anonymous function (lambda) that is used to determine sort order. Therefore, that quick one-liner (3-liner for readibility) will sort based on the value of index 2
. As a result, if my_slice
starts as:
[ [1, 2, 1], [2, 3, 9], [3, 4, 5] ]
then it will sort to:
[ [1, 2, 1], [3, 4, 5], [2, 3, 9] ]
Looking at the doc page for algorithm.sort, it appears to take a cmp_fn
arg (like the above anonymous function). Does anybody have sample code I can peek at for how to actually implement? ...tiny brain is confused. 😊12 Replies
Derp. The
cmp_fn
is for partition
. For some reason, I thought it was sort
too. This is what I get for trying to multi-task. #bonk-self
But I guess my Q remains:
Has anybody designed a clean method for custom sort functions?
i did something here.
https://joyofmojo.com/generic_quicksort/
As i couldnt find anything in Mojo itself i ended up implementing quicksort myself before i realized i dont actually need sort in my project 😄
Joy of Mojo
Generic Quicksort
Context Mojo Reference: Sort Mojo Version: 24.2.1 Demo: Sorting a Group of People by Age This demo showcases how to sort a group of people based on their age using a versatile QuickSort algorithm. This generic QuickSort implementation can be used to sort arrays of any type, provided a custom comparison function is specified. The flexibility of t...
Awesome! Ty. ❤️
At first MojoCON, I'm gonna owe a lot of people a free coffee....... ☕
check carefully, everything on this website is just trying things and probably buggy.
yep, dumping into a file rn. ...but might have to mess with it tomorrow. I just noticed the time and need to be up early. 🙂
I did multiple sorting algorithms here: https://github.com/mzaks/mojo-sort but stopped maintaining it for lack of time. If you are interested I am gladly accepting PRs 😄
GitHub
GitHub - mzaks/mojo-sort
Contribute to mzaks/mojo-sort development by creating an account on GitHub.
Awesome! I'll look at it later today when I have some free time. ❤️
@Maxim , I'm derping hard here. I did some edits that were obvious (
s/let /var /
and the like), but I'm stumbling on how to adjust the function signature. If you have free time to do a moment of hand-holding so I can work through this one signature, then I think I can help with the file-by-file update to current Mojo syntax.
https://github.com/dimitrilw/mojo-sort/blob/quick_sort/quick_sort/sort.mojoI should have added the list of changes I made:
![No description](https://cdn.answeroverflow.com/1235229292837863536/image.png)
order changes were made is bottom-to-top -- that's just screenshot of the branch's commit history
and I will rebase into single commit with more clear notes before PR... I just do sloppy one-liners when in "just make it work" mode 😄
Hey @bunny I just pushed an update, there are still a few issues like multi key sort seems to be buggy, and radix sort seems to crash, which I think is rather a compiler bug, but I need more investigation. Otherwise insertion sort, selection sort, quick sort, count sort, radix sort 11, radix sort 13 and radix sort 16 seem to work fine.
There is also a fast binary search implementation in the repo based on https://en.algorithmica.org/hpc/data-structures/binary-search/ which seems to perform 1.7 to 2.4 times faster than regular binary search on m1
@Maxim , you're awesome. ❤️
I really need to learn about the SIMD data type. Honestly, I've always seen SIMD stuff as magical. Time for me to peek behind the curtain.
Re the faster binary search on m1:
First, I'm assuming "m1" = Apple Silicon M1 chipset. If that assumption is wrong, then everything following is garbage. 😄
Have you bench'ed the two searches on other hardware? I'd help, but I'm on M1 Max, not Intel/M2/AMD/etc.
If the performance is substantially better for different hardware, then I wonder if we would benefit from a wrapper binary-search which has a sys check for hardware type before using a given optimized binary search algo. What do you think?
And that "we" in the phrase "we would benefit" wasn't to steal your glory. It was more a "we, the Mojo users that depend on the awesome work of peeps like you." 😊
Last:
I'm reading all the diffs. Just reviewing your code changes is really helping me better understand Mojo.
No joke: I find that after doing basics in a new language (hello world, a sudoku solver, whatever), then I learn best by refactoring existing code and/or reviewing the refactors that others have made. So this is helpful for me in far more ways than "yay, free search algos!" Ty! :bunhop:
hrm... really miss my various "bunny" emoji. 😐
I can do a benchmark run on intel i7 as well, will check if I can find time tomorrow. But generally it seems to be on par with the article I linked to:
As typical for predication, this trick is very fragile to compiler optimizations — depending on the compiler and how the function is invoked, it may still leave a branch or generate suboptimal code. It works fine on Clang 10, yielding a 2.5-3x improvement on small arrays:And btw thanks for the kind words, it is always good to read that things you build are helpful to others. ❤️