(tye)Re2: Creating an array of unique numbers (Benchmarks!)

Replies are listed 'Best First'.
Re: (tye)Re2: Creating an array of unique numbers (Benchmarks!) by archon (Monk) on Mar 28, 2001 at 03:38 UTC
I expected much worse results, but here are the results of grabbing 900 unique numbers from a list of 1000: `Benchmark: timing 5000 iterations of test_archon, test_jcwren, test_lu +cs, test_lucsjcwren, test_lucsjcwren2... test_archon: 259 wallclock secs (242.45 usr + 0.14 sys = 242.59 CPU) test_jcwren: 213 wallclock secs (202.54 usr + 0.16 sys = 202.70 CPU) test_lucs: 285 wallclock secs (267.02 usr + 0.27 sys = 267.28 CPU) test_lucsjcwren: 268 wallclock secs (248.88 usr + 0.24 sys = 249.12 C +PU) test_lucsjcwren2: 255 wallclock secs (231.91 usr + 0.21 sys = 232.12 +CPU)` [download] This is where jcwren's algorithm begins to outperform lucs and mine. I'm surprised mine is still about as fast as lucs', though.	[reply] [d/l]
Re (tilly) 5: Creating an array of unique numbers (Benchmarks!) by tilly (Archbishop) on Mar 28, 2001 at 09:30 UTC
If you are doing a fixed portion k of an array of size n, your algorithm is O(n). The constant gets worse the closer that k is to 1. Unless my back of the envelope calculation is wrong your constant is proportional to `k-log(1-k)` where that logarithm is the natural log. Throw in the fact that you are only selecting k*n elements that works out to your selecting things `1-(log(1-k)/k)` times for every output (on average). If I put in k = 0.9 that works out to be a factor of about 3.56. So while if you are selecting all but a few elements, your approach is slow, if you are selecting up to a fixed proportion, it should be just fine.	[reply]