Postbox sort

[Yamaeda]

Hi guys!

I read an article quite some time ago about a new search routine. It supposedly worked by coarse sorting items into separate boxes/lists, like a hash table or postal office and then sorting these lists. Adding the sublists together and you'll have a sorted list.

So it's basically a hash table/divide and conquer routine with quick sort on each list.


Now, how can we make this go faster? One big thing i've already done is rebuilding the output in the input array by replacing, at first i build a new array which took noticably longer time.

I have a feeling the memory handler costs alot of time as i in a has(c)h ruse (j/k) decided to make a pretty hash table implementation and thus building an array of clusters of arrays. I would probably gain time by allocating the hash arrays 100 at a time, replace elements instead and use a tracker in the cluster.

Any thoughts?

/Y

Message Edited by Support on 02-28-2010 09:53 AM

[GerdW]

Hi Yamaeda,

I made it twice as fast - just by correctly measuring the time

Hint: use more sequence frames then you would even think of...

[GerdW]

Hi Yamaeda,

another speed up of factor 2 by eliminating unneeded wires...

Nothing (substantial) changed and a speedup of factor 4 - quite good, eh?

[Yamaeda]

Lol, well still 10:1 speeds, not quite what i wished for. 😉

/Y

[GerdW]

Hi Yamaeda,

for me the speed differences vary between 4:1 and 10:1.

There's a big problem (in terms of speed measurement) in your algorithm:

The speed varies very substantial due to different memory allocation needs. You constantly grow a lot of arrays (each bucket may grow in a different manner), making it hard to give a "correct" time for this type of sorting algorithm. It strongly depends on LV-internal memory allocation scheme (and of course of the data to be sorted). An advantage (???) may be that you need (a lot of) smaller chunks of memory for the sorting - but other algorithm do the sorting in place, needing no addtional memory.

Due to the (rather) complex additional layer of intermediate buffers this type of sorting will always suffer from "not perfect" memory allocation schemes. You may pre-allocate the buffers with a reasonable sized array (right now you use an initial empty array) - but then you add the overhead of keeping track of buffer usage...

[GerdW]

Hi Yamaeda,

some more testing:

For already sorted data your code is ~20 times slower, for reverse sorted data it's ~7 times slower than LV-internal sorting. For random data I "measured" ratios between 4 and 220 - and it has a tendency to produce even more bad numbers then getting better...

Message Edited by GerdW on 02-27-2010 07:13 PM

[Yamaeda]

Try it again Gerd, it seems to be quite irregular in speed in my tries, probably due to memory management. For me it's been from 1,5 sec to 17 secs with 1m numbers, with most being about 2,5 sec with the corrected measurement. The removal of these wires didn't do alot of difference. (my previous post landed after your 1st)

[Yamaeda]

Heh, darn you post fast. 😄

Yeah i've figured the lack of in-placeness is a big letdown with this algorithm, i dont know if it'd worked better in e.g. C.
I guess we're proving what we already knew - It's hard to beat quick sort. It's an interesting idea though.
I'll make a version 2 with some preallocation.

/Y

Message Edited by Yamaeda on 02-27-2010 07:25 PM

[Yamaeda]

So, preallocated arrays. It's not faster, but alot more consistent in speed.

/Y

Message Edited by Support on 02-28-2010 09:54 AM