sort with custom `cmp_fn`

In Go, I can easily sort a slice with something like:

sort.Slice(my_slice, func(i, j int) bool {
    return my_slice[i][2] < my_slice[j][2]
})

sort.Slice(my_slice, func(i, j int) bool {
    return my_slice[i][2] < my_slice[j][2]
})

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

bunnyOP•8mo ago

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?

from testing import assert_equal

fn main() raises:
    var my_list = List[List[Int]](
        List(1, 2, 9),
        List(7, 8, 1),
        List(4, 5, 6),
    )

    # TODO: sort my_list on the basis of each sub-list's index 2

    var want = List[List[Int]](
        List(7, 8, 1), # 1 is smallest
        List(4, 5, 6), # 6 is mid
        List(1, 2, 9), # 9 is largest
    )

    for i in range(len(my_list)):
        for j in range(len(my_list[i])):
            print("i:", i, "& j:", j)
            assert_equal(
                my_list[i][j],
                want[i][j],
            )

from testing import assert_equal

fn main() raises:
    var my_list = List[List[Int]](
        List(1, 2, 9),
        List(7, 8, 1),
        List(4, 5, 6),
    )

    # TODO: sort my_list on the basis of each sub-list's index 2

    var want = List[List[Int]](
        List(7, 8, 1), # 1 is smallest
        List(4, 5, 6), # 6 is mid
        List(1, 2, 9), # 9 is largest
    )

    for i in range(len(my_list)):
        for j in range(len(my_list[i])):
            print("i:", i, "& j:", j)
            assert_equal(
                my_list[i][j],
                want[i][j],
            )

Martin Dudek•8mo ago

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...

bunnyOP•8mo ago

Awesome! Ty. ❤️ At first MojoCON, I'm gonna owe a lot of people a free coffee....... ☕

Martin Dudek•8mo ago

check carefully, everything on this website is just trying things and probably buggy.

bunnyOP•8mo ago

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. 🙂

Maxim•8mo ago

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.

bunnyOP•8mo ago

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.mojo

bunnyOP•8mo ago

I should have added the list of changes I made:

bunnyOP•8mo ago

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 😄

Maxim•8mo ago

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

bunnyOP•8mo ago

@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. 😐

Maxim•8mo ago

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. ❤️

Gaming

Programming

sort with custom `cmp_fn`