Skip to content

Instantly share code, notes, and snippets.

@Putnam3145
Created June 7, 2020 20:39
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Putnam3145/232a509ebc605f2b250fb274b4d32776 to your computer and use it in GitHub Desktop.
Save Putnam3145/232a509ebc605f2b250fb274b4d32776 to your computer and use it in GitHub Desktop.
Some programming junk food. Felt like implementing a parallel quicksort and was baffled at how fast it is.
import std.stdio;
import std.traits : isOrderingComparable;
import std.range;
import std.algorithm.sorting;
import std.algorithm.mutation;
import std.typecons : Nullable;
import std.parallelism : totalCPUs;
auto parallelQuicksort(T)(T[] list,uint maxThreads = totalCPUs)
if(isOrderingComparable!T)
{
if(list.length < 64 || maxThreads <= 1)
{
return sort(list);
}
import std.parallelism : scopedTask, taskPool;
auto pieces = partition3(list,list[$/2]);
auto right = scopedTask!parallelQuicksort(pieces[2],maxThreads/2);
right.executeInNewThread();
parallelQuicksort(pieces[0],maxThreads/2);
right.workForce();
return assumeSorted(list);
}
auto moreParallelQuicksort(T)(T[] list)
if(isOrderingComparable!T)
{
if(list.length < 64)
{
return sort(list);
}
import std.parallelism : scopedTask, taskPool;
auto pieces = partition3(list,list[list.length/2]);
auto leftSorted = scopedTask!moreParallelQuicksort(pieces[0]);
auto rightSorted = scopedTask!moreParallelQuicksort(pieces[2]);
taskPool.put(leftSorted);
taskPool.put(rightSorted);
leftSorted.workForce();
rightSorted.workForce();
return assumeSorted(list);
}
auto insertionSort(T)(T[] list)
if(isOrderingComparable!T)
{
foreach(i;1..list.length)
{
auto j = i;
while(j>0 && list[j-1] > list[j])
{
list.swapAt(j,j-1);
j -= 1;
}
}
return assumeSorted(list);
}
void justQuicksort4Head(T)(T[] list, T likelyMin, T likelyMax)
{
if(list.length < 64)
{
sort(list);
}
if(list.length < 512)
{
import std.algorithm.searching : minElement,maxElement;
likelyMin = minElement(list);
likelyMax = maxElement(list);
}
import std.parallelism : scopedTask, taskPool;
auto pieces = partition3(list,(likelyMin+likelyMax)/2);
auto leftSorted = scopedTask!moreParallelQuicksort(pieces[0]);
auto rightSorted = scopedTask!moreParallelQuicksort(pieces[2]);
taskPool.put(leftSorted);
taskPool.put(rightSorted);
leftSorted.workForce();
rightSorted.workForce();
}
auto sortWithInfo(T)(T[] list,T likelyMin,T likelyMax)
{
import std.parallelism : parallel;
import std.math : abs;
list.justQuicksort4Head(likelyMin,likelyMax);
return assumeSorted(list);
}
int slightlyTweak(int a)
{
import std.random : uniform;
return a + uniform!"[]"(-10,10);
}
int slightlyTweakAndSquash(int a)
{
import std.random : uniform;
return (a/100) + uniform!"[]"(-1,1);
}
mixin template SortingAlgoTest(alias func)
{
unittest
{
import std.array : array;
import std.range : generate, takeExactly;
import std.random : uniform;
import core.time : MonoTime,dur;
writeln(__traits(identifier,func),":");
long rollingAverage = 0;
auto averagedSoFar = 0;
foreach(i;0..3)
{
int[] arr = generate!(() => uniform(-10000000, 10000000)).takeExactly(10000000).array;
immutable auto start = MonoTime.currTime;
func(arr);
immutable auto thisTime = (MonoTime.currTime - start).total!"hnsecs";
foreach(idx;1..arr.length)
{
import std.conv : to;
immutable int prev = arr[idx-1];
immutable int curr = arr[idx];
assert(prev <= curr,"Not sorted! Index "~idx.to!string~" is "~curr.to!string~", less than "~prev.to!string);
}
rollingAverage = (thisTime + (rollingAverage * averagedSoFar))/(averagedSoFar+1);
averagedSoFar++;
}
writeln("Random array (huge range): ",dur!"hnsecs"(rollingAverage));
rollingAverage = 0;
averagedSoFar = 0;
foreach(i;0..3)
{
int[] arr = generate!(() => uniform(-100, 100)).takeExactly(1000000).array;
immutable auto start = MonoTime.currTime;
func(arr);
immutable auto thisTime = (MonoTime.currTime - start).total!"hnsecs";
assert(isSorted(arr));
rollingAverage = (thisTime + (rollingAverage * averagedSoFar))/(averagedSoFar+1);
averagedSoFar++;
}
writeln("Random array (many duplicates): ",dur!"hnsecs"(rollingAverage));
{
import std.range : iota;
int[] arr = iota(500000,-500000,-1).array;
immutable auto start = MonoTime.currTime;
func(arr);
writeln("Reversed array: ",MonoTime.currTime - start);
assert(isSorted(arr));
}
{
import std.range : iota;
import std.parallelism : taskPool;
int[] arr = taskPool.amap!slightlyTweak(iota(-500000,500000,1),100000).array;
immutable auto start = MonoTime.currTime;
func(arr);
writeln("Nearly sorted: ",MonoTime.currTime - start);
assert(isSorted(arr));
}
{
import std.range : iota;
import std.parallelism : taskPool;
int[] arr = taskPool.amap!slightlyTweakAndSquash(iota(-500000,500000,1),100000).array;
immutable auto start = MonoTime.currTime;
func(arr);
writeln("Nearly sorted (many duplicates): ",MonoTime.currTime - start);
assert(isSorted(arr));
}
}
}
mixin SortingAlgoTest!parallelQuicksort;
mixin SortingAlgoTest!moreParallelQuicksort;
unittest // this one takes function arguments, so it needs its own test, natch
{
import std.array : array;
import std.range : generate, takeExactly;
import std.random : uniform;
import core.time : MonoTime,dur;
writeln(__traits(identifier,sortWithInfo),":");
long rollingAverage = 0;
auto averagedSoFar = 0;
foreach(i;0..3)
{
int[] arr = generate!(() => uniform(-10000000, 10000000)).takeExactly(10000000).array;
immutable auto start = MonoTime.currTime;
sortWithInfo(arr,-10000000,10000000);
immutable auto thisTime = (MonoTime.currTime - start).total!"hnsecs";
foreach(idx;1..arr.length)
{
import std.conv : to;
immutable int prev = arr[idx-1];
immutable int curr = arr[idx];
assert(prev <= curr,"Not sorted! Index "~idx.to!string~" is "~curr.to!string~", less than "~prev.to!string);
}
rollingAverage = (thisTime + (rollingAverage * averagedSoFar))/(averagedSoFar+1);
averagedSoFar++;
}
writeln("Random array (huge range): ",dur!"hnsecs"(rollingAverage));
rollingAverage = 0;
averagedSoFar = 0;
foreach(i;0..3)
{
int[] arr = generate!(() => uniform(-100, 100)).takeExactly(1000000).array;
immutable auto start = MonoTime.currTime;
sortWithInfo(arr,-100,100);
immutable auto thisTime = (MonoTime.currTime - start).total!"hnsecs";
assert(isSorted(arr));
rollingAverage = (thisTime + (rollingAverage * averagedSoFar))/(averagedSoFar+1);
averagedSoFar++;
}
writeln("Random array (many duplicates): ",dur!"hnsecs"(rollingAverage));
{
import std.range : iota;
int[] arr = iota(500000,-500000,-1).array;
immutable auto start = MonoTime.currTime;
sortWithInfo(arr,-500000,500000);
writeln("Reversed array: ",MonoTime.currTime - start);
assert(isSorted(arr));
}
{
import std.range : iota;
import std.parallelism : taskPool;
int[] arr = taskPool.amap!slightlyTweak(iota(-500000,500000,1),100000).array;
immutable auto start = MonoTime.currTime;
sortWithInfo(arr,-500000,500000);
writeln("Nearly sorted: ",MonoTime.currTime - start);
assert(isSorted(arr));
}
{
import std.range : iota;
import std.parallelism : taskPool;
int[] arr = taskPool.amap!slightlyTweakAndSquash(iota(-500000,500000,1),100000).array;
immutable auto start = MonoTime.currTime;
sortWithInfo(arr,-5000,5000);
writeln("Nearly sorted (many duplicates): ",MonoTime.currTime - start);
assert(isSorted(arr));
}
}
mixin SortingAlgoTest!sort;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment