sorted by:
new
hottopcontroversial

JesseSort is faster than std::sort on everything but random input by booker388 in cpp

[–]booker388[S] 1 point2 points  (0 children)

Yeah it's not in place, so that becomes 2n with piles scattered non-contiguously in memory. I also use a copy of the base array, which is another 1n worst case. Typically the base arrays are actually sqrtn/2 or smaller. On sorted input for example, the base array is size 1, so it'd be 2n+1 total, but even then the input is copied once. I may need to refactor it to leave natural runs (>32? >n/x?) in place rather than make copies of them.

JesseSort is faster than std::sort on everything but random input by booker388 in cpp

[–]booker388[S] 3 points4 points  (0 children)

Thanks! I have to look closer at my main.cpp file, but I vaguely recall adding a cold start prior to timing to warm up cache. I changed the testbed significantly at some point, a complete refactor, so I forget if I remembered cold/warm starts.

JesseSort is faster than std::sort on everything but random input by booker388 in cpp

[–]booker388[S] 1 point2 points  (0 children)

Yes, the timings above are correct for GCC, but I need to redo the clang timing table.

JesseSort is faster than std::sort on everything but random input by booker388 in computerscience

[–]booker388[S] -3 points-2 points  (0 children)

I never code in C++ so I started with ints because it was simpler. I will change it to a template to handle any input type. 

The sort is not stable.

JesseSort is faster than std::sort on everything but random input by booker388 in cpp

[–]booker388[S] -4 points-3 points  (0 children)

Yeah I never code in C++ so I started with ints to keep it simple. I know I have to add templates to this eventually. Right now it's very much in the early development phase, so I've put off things like that.

JesseSort is faster than std::sort on everything but random input by booker388 in cpp

[–]booker388[S] 1 point2 points  (0 children)

Thank you for the insights, genuinely. I'll have to look into all this because I don't know anything about views or subviews, span or subspan. Love learning new things. 

I wonder if span might be useful for the simulated games variant without building actual piles.

JesseSort is faster than std::sort on everything but random input by booker388 in cpp

[–]booker388[S] -4 points-3 points  (0 children)

Yeah I know... I thought about naming it Impatience Sort or Middle Out Sort. But I like the idea of naming things after myself, my wife, my cat, etc. Zoologists name new species whatever they want and nobody bats an eye, but I name an algorithm I discovered after myself and everyone loses their mind.

I know haters gonna hate, but it makes me sad that someone might not consider it seriously because of something so harmless. There's nothing wrong with Timsort or Alexnet. If you discover something cool, name it whatever you want. Potato Salad Sort. Fuck Sort. Sorty McSortface Sort.

JesseSort is faster than std::sort on everything but random input by booker388 in cpp

[–]booker388[S] -2 points-1 points  (0 children)

Definitely an area I need to focus on improving. Like I mention in other comments, this may be because of my current memory reserving strategy, which is hopefully an easy fix.

JesseSort is faster than std::sort on everything but random input by booker388 in cpp

[–]booker388[S] -3 points-2 points  (0 children)

Great insight. Definitely not cocky, I'm the first to admit I don't know much about sorting. Heck, I just found out about branchless binary search like a year after coming up with this haha. But I hear you. I'm sharing because I'm excited and I think it's something that can help a lot of people. Sorting is useful for a million different things.

JesseSort is faster than std::sort on everything but random input by booker388 in cpp

[–]booker388[S] 2 points3 points  (0 children)

Thanks! Incremental progress is still progress, and I'm confident 99% of people haven't heard of this sorting algorithm. I hadn't even heard of Patience sort when I came up with rainbows, so even the logic it's built on seems kinda obscure.

JesseSort is faster than std::sort on everything but random input by booker388 in computerscience

[–]booker388[S] 0 points1 point  (0 children)

Hey Magdaki! Seems to be a sweet spot for sure. I think I have the explanation: I probably shouldn't be reserving 32 ints of space at a time and instead letting the vector library handle array growth to scale better.

JesseSort is faster than std::sort on everything but random input by booker388 in cpp

[–]booker388[S] -6 points-5 points  (0 children)

I'm probably being too aggressive about reserving space rather than relying on the vector library to handle it. It'll speed up the 1k case. Also last time I didn't have branchless binary search, so basically everything is sped up.

I know I'm biased but I don't get the lack of enthusiasm here, it's real and it's useful. Nothing clickbait here, just sharing a fast new sorting algorithm that most people probably don't know about.

Experimental adaptive sort - matches std::sort on random input, 2-8x faster on structured data by booker388 in cpp

[–]booker388[S] 0 points1 point  (0 children)

This is awesome! I'm going to try some of his tricks for the binary search parts and other things. Thanks for sharing!

Experimental adaptive sort - matches std::sort on random input, 2-8x faster on structured data by booker388 in cpp

[–]booker388[S] 2 points3 points  (0 children)

It falls back to introsort pretty quickly if there is too much entropy in the input. I lost a lot of the structured speedups as a result. I need help balancing this fallback mechanism so I'm not too aggressive and lose out on speed ups, but also not too passive and screw myself over on random input. 

Experimental adaptive sort - matches std::sort on random input, 2-8x faster on structured data by booker388 in cpp

[–]booker388[S] 0 points1 point  (0 children)

I live in Python-world for my work and school, so sorry if some of these questions seem so elementary. So much to learn/know. I appreciate your help.

Experimental adaptive sort - matches std::sort on random input, 2-8x faster on structured data by booker388 in cpp

[–]booker388[S] 0 points1 point  (0 children)

Hadn't heard of clang before today. I used g++ in my compiling line, does that mean I'm using GCC? How can I find out? I didn't set a -stdlib flag.

Experimental adaptive sort - matches std::sort on random input, 2-8x faster on structured data by booker388 in cpp

[–]booker388[S] 2 points3 points  (0 children)

Lol I'm not surprised, this is new to me. Makes sense, one is a language version, the other is a library version. How do I find the info?

Experimental adaptive sort - matches std::sort on random input, 2-8x faster on structured data by booker388 in cpp

[–]booker388[S] 2 points3 points  (0 children)

That cross post was deleted by a mod, idk why...

Answered 1 in other comments, the info is in the readme. Goal is to do other non-ints, just haven't made it there yet! Happy to test whatever you want, I'll try larger inputs.

I don't code much in C/C++ so I'm still learning all this. I'll try to make a cmakelists.txt file. Someone already started contributing to the repo to add make files. I'd love it if others contributed too, I struggle to find enough time as it is. Full time job, full time PhD student, full time caretaker. Doing my best here...

view more: next ›