Re: random numbers
Derek Parnell wrote:
>
> jiri babor wrote:
>
> Hey jiri! I knew I should have left it to the master. Your routine is about
> 385% faster than my first try. It is the same as mine but very sensibly reuses
> the very sequence that is being shuffled for the result storage. That really
> eliminates all the excess memory allocation and moving stuff about.
>
> ... if only there was a built-in swap operation for even faster run times.
>
> function shuffle(sequence s) -- random shuffle of sequence
> integer r
> for i = length(s) to 2 by -1 do
> r = rand(i)
> swap s[r] with s[i] !!!
> end for
> return s
> end function
>
> --
> Derek Parnell
> Melbourne, Australia
> Skype name: derek.j.parnell
Shuffling algorithm: nothing to add, solved optimally while I was sleeping.
Swap operation: I am not sure swap(sequence s,integer index1,integer index2)
would be much faster than current
temp=s[index1]
implicit_temp=s[index2]
s[index1]=implicit_temp
s[index2]=temp
because of the overhead of routine calls. At the machine level, you can of
course shave implicit_temp using the three XCHG trick:
<asm>
xchg eax,[ebx+esi]
wchg eax,[ebx+edi]
xchg eax,[ebx+esi]
</asm>
with obvious register usage. I don't know if supported C compilers can apply it,
and it wouldn't work on non Intel CPUs (ARM processor standard architecture
doesn't have an XCHG instruction).
What would speed up some tasks is a builtin move_right(sequence s,integer
start_slice,integer end_slice,integer how_much). Currently you have to do this by
creating temporary slices:
temp=s[end_slice+1..end_slice+how_much]
s[start_slice+how_much..end_slice+how_much]=s[start_slice..end_slice]
s[start_slice..start_slice+how_much-1]=temp
In the backend you just need EMalloc()ing some memory for the end portion, three
memcpy() and an EFree(). Wraparounds should probably trigger a runtime error, but
could be handled with a couple more memcpy() calls. Of course negative values for
how_much would be allowed.
CChris
|
Not Categorized, Please Help
|
|
