dan13llljws
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:
while True:
while comp(a[left], pivot_vlaue):
left += 1
while left < right and not comp(a[right], pivot_value):
right -= 1
....
while True:
while comp(a[left], pivot_vlaue):
left += 1
while left < right and not comp(a[right], pivot_value):
right -= 1
....
It really requires you have < since otherwise when a[left] == pivot_value left will go out of bound. Take a look at
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
std::vector<int> a(100, 1);
std::sort(a.begin(), a.end(), [&](int x, int y){
return x <= y;
});
}
/*
[M] dan13 % g++ -std=c++20 test.cpp && ./a.out
zsh: segmentation fault ./a.out
but when I do < it is fine.
*/
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
std::vector<int> a(100, 1);
std::sort(a.begin(), a.end(), [&](int x, int y){
return x <= y;
});
}
/*
[M] dan13 % g++ -std=c++20 test.cpp && ./a.out
zsh: segmentation fault ./a.out
but when I do < it is fine.
*/
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

var start = time.now()
sort(...)
var end = time.now()
print(end - start)

var start = time.now()
sort(...)
var end = time.now()
print(end - start)
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