Timeline for Chance of collisions between random numbers when inserting into set
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 10, 2013 at 19:04 | comment | added | Lasse V. Karlsen | So unfortunately it isn't exactly a set, but each day the last 5 digits of that key slowly fills up the available space of keys, for that date, increasing the chance of a failure towards the end of the day. | |
| Sep 10, 2013 at 19:04 | comment | added | Lasse V. Karlsen | The actual problem is a database application that for old reasons calculates a primary key range for a table, and randomizes the last part. Basically it calculates the number of days since a particular date, multiplies that with 100.000, and adds a random number, then attempts to insert a new row into the database. If it fails due to a duplicate key error, it retries with another random value, 250 times max. Main reason for this "approach" is legacy code and cross-database engine support. | |
| Sep 10, 2013 at 18:42 | comment | added | ely | This is somewhat reminiscent of hash function homework questions. | |
| Sep 10, 2013 at 18:21 | vote | accept | Lasse V. Karlsen | ||
| Sep 10, 2013 at 18:19 | comment | added | Lasse V. Karlsen | I reworded the problem because this is a legacy application with some limitations as to what can be done, unfortunately the approach to guarantee the uniqueness cannot be used here as the code cannot be changed. Instead I'm trying to get some statistical properties for it so that I can argue that it should be replaced. | |
| Sep 10, 2013 at 18:15 | answer | added | Henry | timeline score: 1 | |
| Sep 10, 2013 at 17:57 | answer | added | KalEl | timeline score: 2 | |
| Sep 10, 2013 at 17:43 | comment | added | whuber♦ | Why don't you just consider an algorithm that guarantees newly generated random values are not in the set? There are plenty of efficient ways to do this. For instance, since you're worried about the set filling, you have enough storage for all $n=10^5$ elements. Why not represent the set as an array of indexes $1$..$n$ along with the current set size $k$? The last $k$ entries in the array hold the set's indexes and the remaining entries hold their complement. To insert a new element, swap a randomly chosen element from the first $k$ with the entry in position $k$ and decrement $k$. | |
| Sep 10, 2013 at 17:38 | answer | added | Budhapest | timeline score: 3 | |
| Sep 10, 2013 at 17:09 | review | First posts | |||
| Sep 10, 2013 at 18:00 | |||||
| Sep 10, 2013 at 16:49 | history | asked | Lasse V. Karlsen | CC BY-SA 3.0 |