473,554 Members | 2,835 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

random iteration of a sequence using generators

2 New Member
Hello everybody. Anybody has any ideas with the following problem?

We start with a list, and we wish to construct a generator that yields each element of the list exactly once, but in random order.

In other words, an iterator version of random.shuffle( list)

The motivation is the following: suppose you have a huge list and wish to extract one random element that satisfies a certain property. Typically, you expect many elements to have the property, so this approach:

-Select a random element, check if it has the property. If that is the case, yield the element, otherwise, loop

is more efficient that this other one:

-Filter the list and select one element.

However the first approach will have find trouble if none, or few elements have the property if your iteration of the list does not guarantee that every element is yielded at least once, and will not be efficient if the iteration does not guarantee that every element is yielded at most once.

Thanks everybody
Aug 18 '07 #1
2 1757
bartonc
6,596 Recognized Expert Expert
Not sure if this satisfies all your requirements, but distribution looks good:
Expand|Select|Wrap|Line Numbers
  1. >>> from random import randint
  2. >>> def YieldRandomItem(aList):
  3. ...     beenYielded = []
  4. ...     size = len(aList) - 1
  5. ...     for item in aList:
  6. ...         i = randint(0, size)
  7. ...         while i in beenYielded:
  8. ...             i = randint(0, size)
  9. ...         beenYielded.append(i)
  10. ...         yield aList[i]
  11. ...         
  12. >>> myList = range(20)
  13. >>> for item in YieldRandomItem(myList):
  14. ...     print item
  15. ...     
  16. 9
  17. 10
  18. 19
  19. 11
  20. 12
  21. 1
  22. 14
  23. 18
  24. 16
  25. 7
  26. 5
  27. 2
  28. 3
  29. 6
  30. 8
  31. 17
  32. 13
  33. 4
  34. 15
  35.  
  36. >>> for item in YieldRandomItem(myList):
  37. ...     print item
  38. ...     
  39. 5
  40. 15
  41. 7
  42. 19
  43. 2
  44. 12
  45. 4
  46. 14
  47. 6
  48. 11
  49. 13
  50.  
  51. 10
  52. 1
  53. 17
  54. 9
  55. 3
  56. 8
  57. 18
  58. 16
  59. >>> 
Aug 18 '07 #2
srpiton
2 New Member
Thanks for your answer, bartonc.
Well, this certainly works as a general method, though for the particular problem that motivated my question I would rather generate random numbers and check if they have the required property:

Expand|Select|Wrap|Line Numbers
  1. x=choice(aList)
  2. while not property(x):
  3.      x=choice(aList)
  4. return x
  5.  
However, I'd bet this can be done even better. I would like to do without having to check the property several times on the same item. Your proposal does this, but at the cost of having to make the check 'i in beenYielded' several times on the same item.

------

As a solution to the general problem, your solution won't do bad, specially if 'YieldRandomIte m' is called for only a few items of the list (which was the motivation), but I believe it's possible to do even better, may be at the cost of having random numbers of poorer quality.

One comment about your solution: the number of iterations of the 'while' loop required to yield the i'th element follows a geometric distribution, with expected time: n/(n-i)
The total expected time if 'YieldRandomIte m' has to run through the whole list is thus:
n/n+n/(n-1)+n/(n-2)+...+n
which is aproximately
n log(n)

So it takes generation of n log(n) random numbers and performing the check 'i in beenYielded' n log(n) times.

This last part takes 'n' operations for each check, which increases the total cost greatly, but the cost of a search operation 'x in aList' can be reduced to 'log(n)' if the list is replaced by a set.

-------

May be a method in the random module that pops a random element from a set would be helpful....
Aug 19 '07 #3

Sign in to post your reply or Sign up for a free account.

Similar topics

1
3691
by: Brandon Michael Moore | last post by:
I'm trying to test a web application using a tool written in python. I would like to be able to generate random values to put in fields. I would like to be able to generate random dates (in a specified range), random strings (specifying allowed characters and a distribution of lengths), or choose randomly between several generators (for better...
59
4251
by: Raymond Hettinger | last post by:
Please comment on the new PEP for reverse iteration methods. Basically, the idea looks like this: for i in xrange(10).iter_backwards(): # 9,8,7,6,5,4,3,2,1,0 <do something with i> The HTML version is much more readable than the ReST version. See: http://www.python.org/peps/pep-0322.html
3
7362
by: Joe | last post by:
Hi, I have been working on some code that requires a high use of random numbers within. Mostly I either have to either: 1) flip a coin i.e. 0 or 1, or 2) generate a double between 0 and 1. I have utilised the following random number source code http://www.agner.org/random/ What I have found is that there is a problem with seeding. The...
23
1754
by: MConly | last post by:
Can you tell me what happens inside CPU when I rand() ? Where can I find the true rand function implemented ? I have heard that rand() in C/C++ is n't a good one but why it isn't a good one, are they lying to me ? Why do they have to do that ? Thank you MnConly
5
3333
by: Peteroid | last post by:
I know how to use rand() to generate random POSITIVE-INTEGER numbers. But, I'd like to generate a random DOUBLE number in the range of 0.0 to 1.0 with resolution of a double (i.e., every possible double value in the range could come up with equal probability). I'd also like to be able to seed this generator (e.g., via the clock) so that the...
104
5078
by: fieldfallow | last post by:
Hello all, Is there a function in the standard C library which returns a prime number which is also pseudo-random? Assuming there isn't, as it appears from the docs that I have, is there a better way than to fill an array of range 0... RAND_MAX with pre-computed primes and using the output of rand() to index into it to extract a random...
40
2779
by: RadiationX | last post by:
I have a problem that I really don't understand at all. In my previous post I could get started on my projects I just had a few problems with syntax errors. This problem is something that I don't conceptually understand very well. Here it is: Π – the ratio of the circumference of a circle to its diameter – is one of the most common...
10
4148
by: rplobue | last post by:
im trying to get urllib2 to work on my server which runs python 2.2.1. When i run the following code: import urllib2 for line in urllib2.urlopen('www.google.com'): print line i will always get the error:
16
539
by: jason.cipriani | last post by:
I am looking for a random number generator implementation with the following requirements: - Thread-safe, re-entrant. - Produces consistently reproducible sequences of psuedo-random numbers given a seed. - Relatively uniform, does not have to be perfect. The application is not a security or statistics application, the quality of numbers...
0
7573
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, well explore What is ONU, What Is Router, ONU & Routers main...
0
7496
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language...
0
7778
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. ...
0
6114
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development projectplanning, coding, testing, and deploymentwithout human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
1
5412
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupr who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
0
5135
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert...
1
1992
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
1
1109
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
0
810
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.