On Mon, 2008-07-07 at 08:28 -0700, mrts wrote: > > > Due to the birthday paradox, sqrt(n) is roughly the number you need to > > > have a 50% collision chance when picking items at random from an > > > inexhaustible set of n items. (0, sys.maxint - 1) is currently the > > > random range. On 32-bit platforms the collision bound is thus quite > > > low as sqrt(2^31) is about 46 000 keys. > > > > This isn't correct. The birthday paradox models a situation of choices > > *with replacement* from a set. That is, when multiple entities can have > > the same value. We don't have replacement. You have a set of X active > > sessions, all unique (since that's a database constraint) and somebody > > is trying to guess one of them at random. So the probability is X/N, not > > something approaching sqrt(N)/N. > > random.randint(0, n) *is* a set with choices with replacements. > Multiple picks can, should and, as demonstrated at > http://code.djangoproject.com/ticket/1180#comment:26 , do create > collisions at around sqrt(n) picks and less.
That comment has no bearing. (1) We pick a random session key. (2) We save it to the database, where it should be unique, otherwise an error is raised. (3) We use that session key to pass back to the user. At this point, the birthday paradox no longer applies. (3) should not happen before (2). If it does, it's a bug that should be fixed, but the database should be being used to guarantee uniqueness here. It's the same database across all threads/processes/machines. Your comment in that ticket avoids step (2), which is a necessary uniqueness constraint. Malcolm --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Django developers" group. To post to this group, send email to django-developers@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/django-developers?hl=en -~----------~----~----~----~------~----~------~--~---
