escaper
asked on
help, a custom random function
type
TIntArray: Array Of Integer;
function myRandom(Range:integer;AIn
begin
end;
i want to produce a random value , but the result can't
be a value in the AIntArray
ASKER
hi , Kretzschmar,thank you ,
but i think maybe your code is not high efficiency.
but i think maybe your code is not high efficiency.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
hi,
maybe this one is faster.
function myRandom2(Range : integer; AIntArray : TIntArray) : integer;
Const
MaxInt = 32768; //for smallInt
var
i : integer;
CheckArray : array of boolean;
begin
//init CheckArray
SetLength(CheckArray, MaxInt);
FillChar(CheckArray[0], MaxInt, 0);
for i := 0 to High(AIntArray) do
CheckArray[AIntArray[i]] := TRUE;
repeat
result := Random(Range +1); // 0 <= X <= Range
if (not CheckArray[Result]) then // not in AIntArray
Break; // then break
until False;
SetLength(CheckArray, 0);
end;
GL
bug
maybe this one is faster.
function myRandom2(Range : integer; AIntArray : TIntArray) : integer;
Const
MaxInt = 32768; //for smallInt
var
i : integer;
CheckArray : array of boolean;
begin
//init CheckArray
SetLength(CheckArray, MaxInt);
FillChar(CheckArray[0], MaxInt, 0);
for i := 0 to High(AIntArray) do
CheckArray[AIntArray[i]] := TRUE;
repeat
result := Random(Range +1); // 0 <= X <= Range
if (not CheckArray[Result]) then // not in AIntArray
Break; // then break
until False;
SetLength(CheckArray, 0);
end;
GL
bug
If it is possible for you to make sure AIntArray is sorted, you can do it much faster. Either with binary search (if the array if large) or just skipping when you know you are too far.
Or (again depending on the situation) make an array like BugRoger did, but pass this array to the function instead of a TIntArray.
Or (again depending on the situation) make an array like BugRoger did, but pass this array to the function instead of a TIntArray.
escaper now asks for the impossible! he should accept the first answer!
escaper--
kretz's answer is not bad, but it has a number of difficulties. First, you can't use low() and high() on an array, only on a range like [1..100]. The function myrandom has no way to know the size of the array from inspecting the array alone.
there are a couple of ways to deal with this, the best I think is to pass a 3rd argument, the array size.
then, I'd break out of the loop as soon as I found the newly generated random # (if found).
function myRandom( Range:integer;AIntArray:TI ntArray; const size :integer):integer;
var
isOK : Boolean;
i : integer;
begin
repeat
Result := Trunc(Random(Range))+1;
i := 1
while (i <= size)
AND (AIntArray[i] <> Result)
do
inc(i);
until i > size;
end;
kretz's answer is not bad, but it has a number of difficulties. First, you can't use low() and high() on an array, only on a range like [1..100]. The function myrandom has no way to know the size of the array from inspecting the array alone.
there are a couple of ways to deal with this, the best I think is to pass a 3rd argument, the array size.
then, I'd break out of the loop as soon as I found the newly generated random # (if found).
function myRandom( Range:integer;AIntArray:TI
var
isOK : Boolean;
i : integer;
begin
repeat
Result := Trunc(Random(Range))+1;
i := 1
while (i <= size)
AND (AIntArray[i] <> Result)
do
inc(i);
until i > size;
end;
>First, you can't use low() and high() on an array
are you sure, OryxConLara?
i used it often on arrays (i.e low() results in 0)
meikl ;-)
are you sure, OryxConLara?
i used it often on arrays (i.e low() results in 0)
meikl ;-)
Actually, if AIntArray can contain a lot of numbers (like 10.000 or more) you could do like this (pseudo code):
Make an array with all the values NOT present in AIntArray (can be done with a linear approach).
Rnd := Random( Length(TheArrayWithValuesN otPresentI nAIntArray ) )
Result := TheArrayWithValuesNotPrese ntInAIntAr ray[ Rnd ];
If you want speed in all situations, then make a function that does either this, or one of the other suggestions, dynamically depending on the length of AIntArray
Make an array with all the values NOT present in AIntArray (can be done with a linear approach).
Rnd := Random( Length(TheArrayWithValuesN
Result := TheArrayWithValuesNotPrese
If you want speed in all situations, then make a function that does either this, or one of the other suggestions, dynamically depending on the length of AIntArray
Actually, if AIntArray can contain a lot of numbers (like 10.000 or more) you could do like this (pseudo code):
Make an array with all the values NOT present in AIntArray (can be done with a linear approach).
Rnd := Random( Length(TheArrayWithValuesN otPresentI nAIntArray ) )
Result := TheArrayWithValuesNotPrese ntInAIntAr ray[ Rnd ];
If you want speed in all situations, then make a function that does either this, or one of the other suggestions, dynamically depending on the length of AIntArray
Make an array with all the values NOT present in AIntArray (can be done with a linear approach).
Rnd := Random( Length(TheArrayWithValuesN
Result := TheArrayWithValuesNotPrese
If you want speed in all situations, then make a function that does either this, or one of the other suggestions, dynamically depending on the length of AIntArray
I think you might be able to get acceptable performance if you do one of the following:
1. replace the array with a TintList and use its built-in searching (and sorting) methods.
2. Order the items in the array and do an interpolation search for the value. It is even faster than binary search.
3. Use some direct addressing or hashing of the values to start your search. If you have a good algorithm, your multi-item hash sub-lists should be quite short.
4a. replace the array with a database table with a unique index. Try to insert your new value into the table. If the insert succeeds, then you know it isn't in the table.
4b. replace the array with a database table with a unique index. Search the table for your value.
1. replace the array with a TintList and use its built-in searching (and sorting) methods.
2. Order the items in the array and do an interpolation search for the value. It is even faster than binary search.
3. Use some direct addressing or hashing of the values to start your search. If you have a good algorithm, your multi-item hash sub-lists should be quite short.
4a. replace the array with a database table with a unique index. Try to insert your new value into the table. If the insert succeeds, then you know it isn't in the table.
4b. replace the array with a database table with a unique index. Search the table for your value.
ASKER
hi ,everyone , i do think pede is a genius;
but i am still not very clear aikimark's suggests,
1.why i need sort?
your mean i need sort the AIntArray ?
if i sort it by A TintList(build it by myself? how?),
then how shoud i do ?
2. "interpolation search " ? what is it? how to realize it?
3. direct addressing? sorry , i still don't know it,
infact , i want to random a data , and every time a random
it , it is marked as used, so next time , the result can't
be it.
pede : can you give me some code ?
but i am still not very clear aikimark's suggests,
1.why i need sort?
your mean i need sort the AIntArray ?
if i sort it by A TintList(build it by myself? how?),
then how shoud i do ?
2. "interpolation search " ? what is it? how to realize it?
3. direct addressing? sorry , i still don't know it,
infact , i want to random a data , and every time a random
it , it is marked as used, so next time , the result can't
be it.
pede : can you give me some code ?
all may have a fallback,
a optimal method depends on
the size of your array
this q is still answered
meikl ;-)
a optimal method depends on
the size of your array
this q is still answered
meikl ;-)
I dont want the points, Meilk answered your original question. I just commented becuse I found it interesting.
Maybe you can use this:
var
Numbers : TList;
procedure TForm1.InitNumbers(StartNu mber, EndNumber: integer);
var i : integer;
begin
if (Numbers <> nil) then FreeAndNil(Numbers);
Numbers := TList.Create;
Numbers.Capacity := (EndNumber-StartNumber)+1;
for i:=StartNumber to EndNumber do
Numbers.Add(pointer(i));
Randomize;
end;
function TForm1.GetNumber(var Number: integer): boolean;
var Rnd : integer;
begin
if (Numbers.Count = 0) then begin
Result := FALSE;
end else begin
Rnd := Random(Numbers.Count);
Number := integer(Numbers[Rnd]);
Numbers.Delete(Rnd);
Result := TRUE;
end;
end;
EXAMPLE USE:
procedure TForm1.Button1Click(Sender : TObject);
var
Num : integer;
begin
InitNumbers(-10, 10);
while (GetNumber(Num)) do
Memo1.Lines.Add(inttostr(N um));
end;
TList uses a bit of memory so making your own simple TList would save some ram, if thats a concern. Then you could also fill in the values directly instead of having to call Add() every time.
Maybe you can use this:
var
Numbers : TList;
procedure TForm1.InitNumbers(StartNu
var i : integer;
begin
if (Numbers <> nil) then FreeAndNil(Numbers);
Numbers := TList.Create;
Numbers.Capacity := (EndNumber-StartNumber)+1;
for i:=StartNumber to EndNumber do
Numbers.Add(pointer(i));
Randomize;
end;
function TForm1.GetNumber(var Number: integer): boolean;
var Rnd : integer;
begin
if (Numbers.Count = 0) then begin
Result := FALSE;
end else begin
Rnd := Random(Numbers.Count);
Number := integer(Numbers[Rnd]);
Numbers.Delete(Rnd);
Result := TRUE;
end;
end;
EXAMPLE USE:
procedure TForm1.Button1Click(Sender
var
Num : integer;
begin
InitNumbers(-10, 10);
while (GetNumber(Num)) do
Memo1.Lines.Add(inttostr(N
end;
TList uses a bit of memory so making your own simple TList would save some ram, if thats a concern. Then you could also fill in the values directly instead of having to call Add() every time.
escaper,
You really need to rethink what you intend to do with this. Random numbers and pseudo-random numbers CAN (and often do) repeat. Preventing duplicated numbers removes the randomness from your numbers.
If you are going to add each number to the array, be aware that your performance will degrade as the size of the array increases.
Ordering the array allows the searching code to perform MUCH faster. For example:
a) If using a binary search, the search only requires Log2(N) steps, where Log2 is the base2 log function and N is the number of items in your array.
b) If using an interpolation search (see "Delphi 3.0 Algorithms" or Delphi Informant articles by Rod Stephens for Delphi coding example) you use fewer steps than the binary search. Since you have integer data you can apply a variation on numeric interpolation
((searchvalue - minvalue) / (maxvalue - minvalue)) * N
to look for your item. If the array item found at that location is not equal to what you are searching for adjust either the minvalue or maxvalue, depending on whether the item is higher or lower, and repeat the search.
If your array values are limited to a specific range (0 to 10000 for example), then you can use your array to indicate that that number has been generated. You could even use a huge bit structure or a large bit array to indicate that a number has been generated. When a new number is generated, inspect the associated position in the array. This is one example of a direct-access lookup.
Another example of direct lookup uses some hash algorithm to generate an address number for the item. If your hash algorithm is good for your data, each list at the hash-address will be short and you can quickly determine if the number already exists.
If you want to minimize duplicated numbers, you should increase the range of generated numbers as much as possible.
You really need to rethink what you intend to do with this. Random numbers and pseudo-random numbers CAN (and often do) repeat. Preventing duplicated numbers removes the randomness from your numbers.
If you are going to add each number to the array, be aware that your performance will degrade as the size of the array increases.
Ordering the array allows the searching code to perform MUCH faster. For example:
a) If using a binary search, the search only requires Log2(N) steps, where Log2 is the base2 log function and N is the number of items in your array.
b) If using an interpolation search (see "Delphi 3.0 Algorithms" or Delphi Informant articles by Rod Stephens for Delphi coding example) you use fewer steps than the binary search. Since you have integer data you can apply a variation on numeric interpolation
((searchvalue - minvalue) / (maxvalue - minvalue)) * N
to look for your item. If the array item found at that location is not equal to what you are searching for adjust either the minvalue or maxvalue, depending on whether the item is higher or lower, and repeat the search.
If your array values are limited to a specific range (0 to 10000 for example), then you can use your array to indicate that that number has been generated. You could even use a huge bit structure or a large bit array to indicate that a number has been generated. When a new number is generated, inspect the associated position in the array. This is one example of a direct-access lookup.
Another example of direct lookup uses some hash algorithm to generate an address number for the item. If your hash algorithm is good for your data, each list at the hash-address will be short and you can quickly determine if the number already exists.
If you want to minimize duplicated numbers, you should increase the range of generated numbers as much as possible.
I'll say something... later... But bugroger has a point and aikimark is right of course...
whats going on?
I liked bugroger's idea about logical array that contains data about what elements
are in the given array, because checking become much easier... But maybe you can
use standard SET structures for it, because it gets only 1 bit (!) for every
element ! Unfortunately, SET can get only byte size types as a base type, so you
can not write SET OF INTEGER (?)... But maybe we can use an array of SETs, for
example if your numbers are between 0..999:
function myRandom(Range:integer; AIntArray:TIntArray):integ er;
type Tcent = set of [0..99];
Tarr = array[0..9] of Tcent;
var
tabu: Tarr;
c: Tcent;
i: integer;
begin
// Fill tabu array
for i := 0 to 9 do tabu[i] := [];
// Maybe FillChar(tabu, SizeOf(tabu), 0);
for i := 0 to High(AIntArray) do
tabu[AIntArray[i] div 100] :=
tabu[AIntArray[i] div 100] + [AIntArray[i] mod 100];
// Now find a random number no from tabu
repeat
i := Trunc(Random(Range))+1;
until not((i mod 100)in tabu[i div 100]);
Result := i;
end;
are in the given array, because checking become much easier... But maybe you can
use standard SET structures for it, because it gets only 1 bit (!) for every
element ! Unfortunately, SET can get only byte size types as a base type, so you
can not write SET OF INTEGER (?)... But maybe we can use an array of SETs, for
example if your numbers are between 0..999:
function myRandom(Range:integer; AIntArray:TIntArray):integ
type Tcent = set of [0..99];
Tarr = array[0..9] of Tcent;
var
tabu: Tarr;
c: Tcent;
i: integer;
begin
// Fill tabu array
for i := 0 to 9 do tabu[i] := [];
// Maybe FillChar(tabu, SizeOf(tabu), 0);
for i := 0 to High(AIntArray) do
tabu[AIntArray[i] div 100] :=
tabu[AIntArray[i] div 100] + [AIntArray[i] mod 100];
// Now find a random number no from tabu
repeat
i := Trunc(Random(Range))+1;
until not((i mod 100)in tabu[i div 100]);
Result := i;
end;
anyway, it depends on the amount of entrys in the intarray
>I liked bugroger's idea about logical array that contains
>data about what elements
yes, would be the fastest on big amounts,
but also very memory-expensive
your code looks interested, LukA_YJK,
but i guess,
by a range up to a million,
it would be more complex
meikl ;-)
>I liked bugroger's idea about logical array that contains
>data about what elements
yes, would be the fastest on big amounts,
but also very memory-expensive
your code looks interested, LukA_YJK,
but i guess,
by a range up to a million,
it would be more complex
meikl ;-)
escaper,
You haven't participated in this discussion since 7/17/2002.
Does this mean
1. one of us has solved or helped you solve your problem?
2. you have lost interest in the problem?
3. the problem was solved by some other means?
4. you are busy testing our code examples?
...or something else?
Your question sounded urgent, but your lack of recent participation indicates otherwise.
You haven't participated in this discussion since 7/17/2002.
Does this mean
1. one of us has solved or helped you solve your problem?
2. you have lost interest in the problem?
3. the problem was solved by some other means?
4. you are busy testing our code examples?
...or something else?
Your question sounded urgent, but your lack of recent participation indicates otherwise.
escaper:
This old question needs to be finalized -- accept an answer, split points, or get a refund. For information on your options, please click here-> http:/help/closing.jsp#1
EXPERTS:
Post your closing recommendations! No comment means you don't care.
This old question needs to be finalized -- accept an answer, split points, or get a refund. For information on your options, please click here-> http:/help/closing.jsp#1
EXPERTS:
Post your closing recommendations! No comment means you don't care.
escaper,
No comment has been added lately (18 days), so it's time to clean up this TA.
I will leave a recommendation in the Cleanup topic area for this question:
RECOMMENDATION: Award points to kretzschmar http:#7156333
Please leave any comments here within 7 days.
-- Please DO NOT accept this comment as an answer ! --
Thanks,
anAKiN
EE Cleanup Volunteer
No comment has been added lately (18 days), so it's time to clean up this TA.
I will leave a recommendation in the Cleanup topic area for this question:
RECOMMENDATION: Award points to kretzschmar http:#7156333
Please leave any comments here within 7 days.
-- Please DO NOT accept this comment as an answer ! --
Thanks,
anAKiN
EE Cleanup Volunteer
function myRandom(Range:integer;AIn
var
isOK : Boolean;
i : integer;
begin
isOK := True;
repeat
Result := Trunc(Random(Range))+1;
for i := low(AIntArray) to high(AIntArray) do
if AIntArray[i]=result then
isOK := False;
until isOK;
end;
meikl ;-)