[pycrypto] Issue with the new random.choice() unit test

Lorenz Quack don at amberfisharts.com
Wed Jan 5 13:14:50 CST 2011


I just took a look at random.sample.
The problem is that it uses a dict to simulate a set (introduced in py2.3).
This is probably done because IIRC dict can do membership test in O(1).
Lists on the other hand do membership test in O(n) so using sets/dict should
provide a speedup if sample size k becomes large.
So what's the problem? Membership testing for dicts was only added in py2.2.

As a fix I simply do O(n) membership testing with the result list.
The patch is again small and attached to this mail.

I didn't take a look at AllOrNothing yet.


On 01/05/2011 02:01 PM, Thorsten Behrens wrote:
> Do you have any ideas on the ailing AllOrNothing.py and random.sample on
> Python 2.1? I haven't dug into those yet beyond
> noting that they have issues, exposed by the new unit tests.
> Yours
> Thorsten

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: random_sample.patch
Url: http://lists.dlitz.net/pipermail/pycrypto/attachments/20110105/e35dfe76/attachment.txt 

More information about the pycrypto mailing list