Re: Random Extension

Tech-Archive recommends: Repair Windows Errors & Optimize Windows Performance

"Göran Andersson" <guffa@xxxxxxxxx> wrote in message news:uguXouyZKHA.4932@xxxxxxxxxxxxxxxxxxxxxxx
I just happen to have an extension lying around that does this in a more efficient way:

public static T PickRandomOne<T>(this IEnumerable<T> list, Random rnd) {
T picked = default(T);
int cnt = 0;
foreach (T item in list) {
if (rnd.Next(++cnt) == 0) {
picked = item;
}
}
return picked;
}

It loops through the items and check for each item if it should keep it or not. As it doesn't have to know how many items there are, it only has to loop through the items once.

However, note that your method does not return all the elements in the collection with equal probability. The first element has a 50% chance of being picked, the second one chance in 6, the third a smaller number and so on. And there's no guarantee that any of the members will be chosen at all, so default(T) could be returned even if the collection is not empty.

In order to achieve an equal probability, I think that the only way to do it requires to know the number of elements in advance, and if you only have an IEnumerable interface, this requires looping through the entire collection before being able to choose the "random" item to be returned.

Certainly, the Original Poster's code calls Count() twice, which can be avoided, but we still need one Count() plus one ElementAt(), which requires looping through the entire collection by average one and a half times.

.

Relevant Pages

  • Re: rnd(0)*X in Assembler?
    ... I did an analysis of what would happen if I used a Random Lookup ... rather than using a Random function that loops back if out of range. ... looping if you're out of range means sometimes a lot of what I consider ... plenty of computing time, it makes sense to generate a new Lookup Table, ...
    (comp.sys.cbm)
  • Re: Would like to loop
    ... On Jan 16, 6:43 pm, John W. Vinson ... The code compiles and it loops through it all but only updates the ... Avoid the entire problem by using an Append query rather than looping through ...
    (microsoft.public.access.gettingstarted)
  • Re: how to find union of two arrays
    ... tried using looping functions and that is far too slow. ... To do this I create the following loops. ... The code also assumes that if there are any duplicates in RangeA column1, that you only want to return the first one for the corresponding RangeB entry. ... Dim arB As Variant ...
    (microsoft.public.excel.programming)
  • Re: how to find union of two arrays
    ... tried using looping functions and that is far too slow. ... To do this I create the following loops. ... My CPU has a 2.5 GHz processor, ...
    (microsoft.public.excel.programming)
  • Re: Random Extension
    ... note that your method does not return all the elements in the collection with equal probability. ... the distribution is as close to completely even that you could ever expect. ... It has a 100% chance of being picked. ... Certainly, the Original Poster's code calls Counttwice, which can be avoided, but we still need one Countplus one ElementAt, which requires looping through the entire collection by average one and a half times. ...
    (microsoft.public.dotnet.languages.csharp)