Fast Sort Too Hard?

Post by **adum** » Sat Jan 03, 2009 12:00 am

just wondering why nobody has even tried it yet...

efe · Post by **efe** » Sat Jan 03, 2009 12:24 am

No, no, it's not too hard. I'm sure it is solvable.
I'm mulling over which algorithm to use here. I thought about radix sort and quicksort.
My analysis shows that both algorithms would take far below 10000 cycles - without using threading.

m!nus · Post by **m!nus** » Sat Jan 03, 2009 1:13 am

how can you analyze that without really implementing it? just wondering.. (i'm not saying i have any clue of this)

gfoot · Post by **gfoot** » Sat Jan 03, 2009 2:57 am

I already have quicksort in HVM which should convert easily, I haven't had time though (playing with MythTV...)

MerickOWA · Post by **MerickOWA** » Sat Jan 03, 2009 3:01 am

I'm still trying to grasp how super small quine can be done in 20 cells ><

m!nus · Post by **m!nus** » Sat Jan 03, 2009 5:07 am

the shvm examples show a very good method to do this

hope i didn't tell too much

tog · Post by **tog** » Sat Jan 03, 2009 10:33 am

I think it's not too hard. But for me the motivation to start with a king-of-the-hill challenge is relatively low if there is no definite way to go (e.g. the choice of algorithm). You invest quite some time to try and implement some approach, but chances are good that somebody else comes up with a better solution, which renders your solution worthless. Or do I keep the points for setting an old benchmark?

Oh, and I'm still not clear about how to efficiently implement threading (and the proper synchronization of threads) with shvm. That must be the key for fast strrev and will be important for fast sort. It would be really helpful if ShardFire would tell how it's done.

m!nus · Post by **m!nus** » Sat Jan 03, 2009 11:51 am

there are 2 ways of syncing the threads known to me
here's one:

Code: Select all

& & & & & <code>

Executes code 32 times but the code is the same for all 32 threads, so no different stackpointer (they are different but cant differ if they execute the same instructions, getThreadID() might change that

)

The other way I know I won't tell you because it's the better one for this (i'm stuck on my implementation but i'm pretty sure that's the way to go)

good luck on that one