dan13llljws
MModular
•Created by Jack Clayton on 5/11/2024 in #community-showcase
mojo-sort
Just watched the video td. I think its the other way around?
47 replies
MModular
•Created by Jack Clayton on 5/11/2024 in #community-showcase
mojo-sort
When I really get a chance to dig into pdqsort, I will be able to discuss more!
47 replies
MModular
•Created by Jack Clayton on 5/11/2024 in #community-showcase
mojo-sort
Really? I guess it really depends on how you implement your partition. I know for the implementation where pick the pivot as last element and you do:
It really requires you have
<
since otherwise when a[left] == pivot_value
left will go out of bound.
Take a look at
I think we <
or <=
is just a convernsion, we can make either work. But it is ultimately the question of "what is the best convention for the users".47 replies
MModular
•Created by Jack Clayton on 5/11/2024 in #community-showcase
mojo-sort
ahhhh, I haven't got a chance to take a look yet
47 replies
MModular
•Created by Jack Clayton on 5/11/2024 in #community-showcase
mojo-sort
I was curious why do our cmp_fn implement “less than equal” rather than “less than”? This seems unconventional.
47 replies
MModular
•Created by Jack Clayton on 5/11/2024 in #community-showcase
mojo-sort
@Maxim I benchmarked various partition scheme for quicksort (current stdlib implementation, an improved version I have internally, your implementation). Here is the benchmark result: (old: stdlib, new: my implementation, new left only: your implementation heapsort: just for reference).
47 replies
MModular
•Created by Jack Clayton on 5/11/2024 in #community-showcase
mojo-sort
@Maxim I made a few comments on your PR. I don’t know a way to work around the list not being captured. You can still put the random list initialization in call_fn and still get a good comparison result.
47 replies
MModular
•Created by Jack Clayton on 5/11/2024 in #community-showcase
mojo-sort
I might be running the benchmark wrong, but somehow std sort appears a lot slower on benchmark while if I just do
then std sort consistently do better than raw insertion sort
47 replies
MModular
•Created by Jack Clayton on 5/11/2024 in #community-showcase
mojo-sort
I noticed something really weird about the benchmark. Running insertion sort on 64 elements takes longer than 32??
47 replies
MModular
•Created by Jack Clayton on 5/11/2024 in #community-showcase
mojo-sort
I have looked at a few, haven't run benchmark on them though.
47 replies
MModular
•Created by Jack Clayton on 5/11/2024 in #community-showcase
mojo-sort
The benchmark PR is great, and I am looking forward to it. I was more interested in making something possible for comparison (comparing past implementations and perhaps to
std::sort
).
As I played around with the sort module a bit more, I noticed that the current implementation actually SHOOT UP drastically as number of elements in the list blows up. (I implemented Heapsort for fun and the current quicksort is actually ~20x worse, not sure why).
I am interested in refactoring the entire module algorithm-wise if no one else is actively working on it. 👀47 replies
MModular
•Created by Jack Clayton on 5/11/2024 in #community-showcase
mojo-sort
Is anyone actively working on making quicksort -> introsort
47 replies