Timeline for duplicate detection problem
Current License: CC BY-SA 2.5
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 1, 2010 at 16:36 | vote | accept | Jason S | ||
| May 23, 2010 at 0:01 | comment | added | David Eppstein | One hash function that takes $O(1)$ storage and obviously works is $h(x)=2^x\bmod p$ where $p$ is a large random prime. But that leads to an $O(n\log n)$ time algorithm because it takes $O(\log n)$ time to evaluate $h(x)$ (for integer arguments in the range 1..n) in any reasonable model of machine arithmetic. I'm pretty sure that taking polynomials modulo a prime doesn't work (there are specific inputs that will trick all low-degree polynomials), but that doesn't exhaust the possibilities. | |
| May 21, 2010 at 12:28 | comment | added | Kaveh Khodjasteh | I am not sure finding/constructing the hash function of the right size is O(1). It will certainly get harder with increasing n and might need some storage. There is a solution based on cycle detection that treats the list as a graph where the vertex corresponding to the array index points to the number stored in the vertex and the problem is reduced to finding whether the graph is cyclic. This is apparently O(1) for storage as you need and is deterministic and cycle detection is easy [O(n) I guess]. It is too early in the day for me so respectfully I leave this as a comment. | |
| May 20, 2010 at 21:01 | comment | added | David Eppstein | Yes, or just use a hash function with a bigger range. | |
| May 20, 2010 at 20:52 | comment | added | Jason S | David: +1. I assume this is like primality testing where you can use multiple passes to increase probability? | |
| May 20, 2010 at 18:19 | comment | added | Jason S | @Dror: Because sum and compare with n(n+1)/2 does not correctly check for duplicates, e.g. a valid permutation 1,2,3,4,5,6...N vs. 2,2,2,4,5,6,...,N | |
| May 20, 2010 at 18:12 | comment | added | Dror Speiser | Why use a hash function when you can use the identity and have correct output every time? Just compute $\sum a[i]$ and compare with $n(n+1)/2$. | |
| May 20, 2010 at 17:43 | history | edited | David Eppstein | CC BY-SA 2.5 |
invertible bloom filter pointer
|
| May 20, 2010 at 17:33 | history | undeleted | David Eppstein | ||
| May 20, 2010 at 17:33 | history | edited | David Eppstein | CC BY-SA 2.5 |
+$; added 61 characters in body; added 172 characters in body
|
| May 20, 2010 at 16:06 | history | deleted | David Eppstein | ||
| May 20, 2010 at 16:05 | history | answered | David Eppstein | CC BY-SA 2.5 |