Easy way to sort streams by size?

MichaelBenjamin · 8 May 2010

if the performance is not important, then:

stream/mono to float x24, into float array and through sort float array to display

aliasant · 8 May 2010

TomC wrote: For an educational project I want to sort 24 streams by size.

By sorting I mean for each single sample compare all 24 inputs in1 - in24 and sort them so that out1 has the smallest value and out24 the greatest value, and of course out2 the second smallest and so on. Load and latency are no issues.

All I came up was a mess and ugly.

Anyone has an idea how to do this more elegant and nice? I hate ugly code.

Tom

What did your first code idea look like? It is an interesting project indeed. Maybe start with 3 or 4 channels instead of 24 just to downscale it and make it easyer to grasp? It sounds like it would be a big code comparing and sorting all them channels but maybe it wont use that much cpu after optimisation.... Will this be like a 24 band Normalizer or silmilar? That could be fun... Use the largest band/channel to determine the gain of all the other bands. Should alias pretty bad but with a smoothing algo, RMS or similar it could work... but this is probably not at all what your doing... Im just dreaming.... 😉 Need food..

infuzion · 8 May 2010

TomC wrote: For an educational project I want to sort 24 streams by size.

What do you call "size"? Most extreme values (eg [+4..-8] vs [+1..-1])? Loudest RMS? Biggest dynamic range?

TomC · 8 May 2010

infuzion wrote: TomC wrote: For an educational project I want to sort 24 streams by size.

What do you call "size"? Most extreme values (eg [+4..-8] vs [+1..-1])? Loudest RMS? Biggest dynamic range?

I mean each single sample.

in1 has a value of 0.34 in2 has a value of -0.25 in3 has a value of 0.76 in4 has a value of -0.12 in5 has a value of 0.0003

the outs should be:

out1 = -0.25 out2 = -0.12 out3 = 0.0003 out4 = 0.34 out5 = 0.76

Mono2float won't work because it must be sample accurate. I just don't care if it needs 100% CPU time. Or if I have 4000 samples latency.

Tom

exonerate · 8 May 2010

Well I would try something like this....

streamin in1;streamout out1; streamin in2;streamout out2; streamin in3;streamout out3; streamin in4;streamout out4; streamin in5;streamout out5; streamin in6;streamout out6; streamin in7;streamout out7; streamin in8;streamout out8;

float inOuts = 8; //Number of inputs and outputs

float i, outAr[8]; float inTmp,cnt,tmp,tmp2,index,outTmp,tmp3,tmp4; float isLessThan;

//Fill array with inputs inTmp = in1&(i==0) + in2&(i==1) +in3&(i==2) +in4&(i==3); inTmp = inTmp +in5&(i==4) +in6&(i==5) +in7&(i==6) +in8&(i==7);

outAr[i] = inTmp;

//Inner loop loop(8) { tmp = outAr[cnt+i]; tmp2 = outAr[index]; isLessThan = (tmp>tmp2);

index = index - isLessThan&(index-cnt);

cnt = cnt+1; cnt = cnt&(cnt<inOuts); }

//Swap tmp4 = outAr[i]; tmp3 = outAr[index]; outAr[i] = tmp3; outAr[index] = tmp4;

//index for outer loop i = i+1; i = i&(i<inOuts);

//Outputs out1 = outAr[0]; out2 = outAr[1]; out3 = outAr[2]; out4 = outAr[3]; out5 = outAr[4]; out6 = outAr[5]; out7 = outAr[6]; out8 = outAr[7];

It kind of works, some issues with it though.

Cheers 😉

Exo

TomC · 8 May 2010

exonerate wrote: Well I would try something like this.... //Fill array with inputs inTmp = in1&(i==0) + in2&(i==1) +in3&(i==2) +in4&(i==3); inTmp = inTmp +in5&(i==4) +in6&(i==5) +in7&(i==6) +in8&(i==7); outAr[i] = inTmp;

I don't really understand this, but a outAr[0] = in1; ... outAr[7] = in8; will do the same job.

I don't know where your 'outer loop' is located, but anyway, I've got the idea.

Thanks,

Tom

Tzarls · 8 May 2010

This might work if you can implement it, haven´t tried but doesn´t look to difficult - not too efficient thou.

http://en.wikipedia.org/wiki/Bubble_sort

exonerate · 8 May 2010

TomC wrote: exonerate wrote: Well I would try something like this.... //Fill array with inputs inTmp = in1&(i==0) + in2&(i==1) +in3&(i==2) +in4&(i==3); inTmp = inTmp +in5&(i==4) +in6&(i==5) +in7&(i==6) +in8&(i==7); outAr[i] = inTmp;

I don't really understand this, but a outAr[0] = in1; ... outAr[7] = in8; will do the same job.

I don't know where your 'outer loop' is located, but anyway, I've got the idea.

Thanks,

Tom

Yeah I know the assign to the array was initially done in the inner loop and I just started doing it like that for some reason. 🙂

The outer loop is the actual steam, so using my method would introduce a sample latency of the number of inputs. I obviously didn't work out all the details I just hashed that together but this stood out as a viable solution.

Cheers 😉

Exo

TomC · 9 May 2010

Short update:

Almost all sorting algorithms use nested loops, those ones cannot be easily implemented in SM.

But I discovered one algorithm called Gnome sort which uses only one single loop.

Together with my own Dynamic loop-hack I was able to implement the needed loop in SSE.

To tired to test it right now, but I'll report back next week if I get this thingy running.

Tom

aliasant · 9 May 2010

TomC wrote: Short update:

Almost all sorting algorithms use nested loops, those ones cannot be easily implemented in SM.

But I discovered one algorithm called Gnome sort which uses only one single loop.

Together with my own Dynamic loop-hack I was able to implement the needed loop in SSE.

To tired to test it right now, but I'll report back next week if I get this thingy running.

Tom

Oooo We can test it for you 🙂

TomC · 9 May 2010

aliasant wrote: Oooo We can test it for you 🙂

I won't have much time for tests anyway, so here we go: find attached a file with 2 code components.

1: Gnome-Sort Code template

Here you find the algorithm for Gnome-sort as comment, followed by the implementation in SM-code. Keep in mind that this one will never work, because SM-code can only use fixed length loops, and Gnome sort computes this dynamically. But I would appreciate if someone double checks that my implementation is correct.

2: Gnome Sort: this is the full featured sorting algorithm, the whole shebang.

Connect the output selector to some switch to select one of its 24 outputs, connect the output to a wave display (Max should be 3), change the selector and see what values each output has.

Works great, but: output00 is wrong, and output14 also not sorted into the rest. Could be probably a simple copy&paste error.

I won't have time to investigate further for the next couple of days, but maybe one of you guys likes the challenge.

The sort algorithm in the code is fully documented, and the lengthy initialization code has some markers to ease orientation.

Oh, and use an external editor to edit the code, because...well, you'll find out 🙂

Enjoy,

Tom

PS: I'm pretty sure that, with what I know NOW, I could implement sorting algorithms with nested loops as well, but I guess nobody, including myself, would actually LOVE to do that.