Re: Adding functions to generic package

Preben Randhol <randhol+valid_for_reply_from_news@xxxxxxx> writes:

> On 2005-05-28, Matthew Heaney <matthewjheaney@xxxxxxxxxxxxx> wrote:
> > What do Randomize and Move do? If you have a tentative implementation,
> > then post it (or just mail it to me) and we can figure what is the best
> > option for you.
>
> It should be called Randomize_Container and be equivelent to the
> Reverse_Container procedure except that it makes the order of the
> elements random. I guess this doesn't seem to make sense for a List,
> but I need it for a program that is asking questions from a list.





> What Move does it to move element number 2 to number 4.

How is that different from Splice?


> If you have a list perhaps the user wants to rearrange the order and
> drags one element to another place in the list (I'm not talking
> GUI-wise). Then I noticed it is a bit cumbersome not to have a move
> routine.

That's what Splice does.


> The procedures are give below:
>
> -----------------------
>
> procedure Move
> (Container : in out Container_Type;
> From : Natural;
> To : Natural)


I see that the positions are integer indexes. That means you'll have to
search for the iterator designating those nodes. But once you have
iterator objects, just pass them to Splice.


> if To = Length (Container) then
> Append (Container, Element (From_Iterator));
> elsif To > From then
> Insert (Container, Succ (To_Iterator),
> Element (From_Iterator));
> elsif To < From then
> Insert (Container, To_Iterator,
> Element (From_Iterator));
> end if;
>
> Delete (Container, From_Iterator);
> end if;


Use Splice for this.


> end Move;
>
> -----------------------
>
> procedure Randomise_Container
> (Container : in out Container_Type;
> Loops : Natural)
> is
> subtype Container_Range is Integer range 1 .. Length (Container);
>
> package Random_Container is new
> Ada.Numerics.Discrete_Random (Container_Range);
> use Random_Container;
>
> Seed : Generator;
> Number : Natural;
> begin
>
> Reset (Seed);
> for I in 1 .. loops loop
> Reset (Seed);
> Reset (Seed);
> for Current in Container_Range loop
> Number := Random (Seed);
> Move (Container, From => Current, To => Number);
> end loop;
> end loop;
>
> end Randomise_Container;


This is going to be way too expensive, since Move is implemented in
terms of integer indexes. You definitely want to implement Randomize in
terms of iterators, not indexes.

I would implement the loop something like:

procedure Randomize (C : in out CT) is
...
I : IT := First (C);
J : IT;
N : Natural := Length (C);

procedure Get_Random_Iterator is ...; -- see below
begin
while I /= Last (C) loop -- or: while N > 1 loop
Get_Random_Iterator; -- get value of J
Splice (C, Before => I, Iterator => J);
I := Succ (J);
end loop;
end Randomize;

Get_Random_Iterator returns an iterator (J) in the range [I, Back):

procedure Get_Random_Iterator is
M : constant Natural := Random (G) mod N;
begin
J := I;
for Index in 1 .. M loop
Succ (J);
end loop;
N := N - 1;
end Get_Random_Iterator;

The expression Random (G) is a call to the Generator function Random,
from an instantiation of Discrete_Random on type Integer.

This should perform much better than the algorithm you posted.

-Matt
.

Relevant Pages

  • Re: ERROR IN AFONSO CODE
    ... So the three PRINT statements do an on-screen update, ... I'm surprised you didn't say anything about the use of "RANDOMIZE ... TIMER" inside the v loop. ...
    (sci.stat.math)
  • Re: question: what does this "fix" thingy here do? r=fix(rnd*6)+1
    ... > You don't want to be using GoTo, especially to jump out of a loop like ... One way to avoid it would be to use another array to store ... > dim i as long ... > randomize ' only do this once in the application ...
    (microsoft.public.vb.general.discussion)
  • Re: how to generate random string?
    ... Randomize Second ... Loop Until Len= 20 ... any good solutions before i start writing something inefficient? ...
    (microsoft.public.scripting.vbscript)
  • Re: VBScript Random Numbers and Letters
    ... >Only call Randomize once, before the For/Next loop. ... That advice is certainly good; but in a brief attempt I failed to make a ... randomize loads the seed with something ...
    (microsoft.public.scripting.vbscript)
  • Re: Adding functions to generic package
    ... >>> What do Randomize and Move do? ... If you have a tentative implementation, ... > How is that different from Splice? ... > terms of integer indexes. ...
    (comp.lang.ada)