[erlang-questions] Speedy unsort:shuffle/1,2 ?

[Allan Wegan]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

> However, there are some constraints on this function. It needs to be
> generic enough, it needs to be fast enough and consume as little memory
> as possible. Three constraints that seldom spell success when combined.
> 
> My suggestion is included in this mail, but my question is: does anyone
> have a faster, more generic and less memory consuming shuffle function?

In an ideal world the following function would be realy fast (because of
O(length(List) of the compiler optimized list_rearrange/4:


% Call example: list_rearrange(fun randomizer/1, List)

- -export([
  list_rearrange/2,
  randomizer/1
]).

list_rearrange(_F, []  = L) -> L;
list_rearrange(_F, [_] = L) -> L;
list_rearrange(F, List) ->
  Input  = list_to_tuple(List),
  Length = tuple_size(Input),
  Output = erlang:make_tuple(Length, 'undefined'),
  list_rearrange(F, Input, Length, Output)
.

list_rearrange(_F, _Input, 0 = _Length, Output) -> tuple_to_list(Output);
list_rearrange( F,  Input,      Length, Output) ->
  {F_2, Chosen_pos} = F(Length),
  Chosen_element    = element(Chosen_pos, Input),
  Last_element      = element(Length,     Input),
  Input_2           = setelement(Chosen_pos, Input,  Last_element),
  Output_2          = setelement(Length,     Output, Chosen_element),
  list_rearrange(F_2, Input, Length - 1, Output_2)
.

randomizer(1) -> {fun randomizer/1, 1};
randomizer(N) -> {fun randomizer/1, crypto:rand_uniform(1, N)}.


But in the real world, the compiler does not realize, that we never
_can_ touch the original tuples given to list_rearrange/4 after the
setelement calls. list_rearrange/4 is not exported, tail recursive, and
in the same module only used as the _last_ statement in the function
that creates the tuples in its body.
The compiler produces code to copy the tuples in each call making
list_rearrange/4 O(length(List)^2)...


- -- 
Allan Wegan
Jabber: allanwegan@REDACTED
ICQ:    209459114
Phone:  +49 40 6732962 (Hansenet)
Schöneberger Strasse 60, 22149 Hamburg
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.12 (MingW32)

iQEcBAEBAgAGBQJMAKPzAAoJENm5axHh7AcxrCwH/RKjyRJ1JacHZ4e5kZ1pPAMK
/oFsaYTfjpBbQLsJhRCQuaHkSPDkA1k2YHqbNRiuXuPCPW5eazcE5kmUM2c2IJW8
EeSThk3jWEVmnGmTZVOEdjOGqmp74izuhWiRlBxs9TceT9Ejnzth5Dhe9zcsqGdi
CDvj5A0oZHOv6EjKR/8FShGI1AxYQcIXgBvzKdomHeaXPPDzj3AKoDixSIWQgQoH
1joia4xXEmMz0ygsOhoMgXw2/plrAZWlr/WRLA7P97nG9Gp8WQ7dyPFcrWNu9KVY
yx7ak/hrPJLAlx6j+foo7QoFC8CFL8ljUelmca0gw2/msmGb7aOwrT9OlcWlXzo=
=qbql
-----END PGP SIGNATURE-----