"Steven Schveighoffer" wrote > "Andrei Alexandrescu" wrote >> Andrei Alexandrescu wrote: >>> Andrei Alexandrescu wrote: >>>> Given an array of length m, return a range that iterates the array in >>>> random order such that the entire array is visited without going >>>> through the same element more than once. Consume minimal amounts of >>>> memory and time. Baseline solution: allocate an array of indices, >>>> shuffle it, then follow indices stored in the array. >>> >>> Ok, here's something that should work. >>> >>> Start with array a of length a.length, allocate a bitmap with one bit >>> per element in the map. Also the number of unselected elements left in >>> the array is kept, call it k. >>> >>> To implement next(): >>> >>> 1. Walk from the beginning of the array to the first unselected element. >>> >>> 2. Roll a fair dice with k faces. If the dice chooses a specific face, >>> choose that first unselected element. Otherwise continue. >>> >>> 3. Continue walking until the next unselected element. >>> >>> 4. Roll a fair dice with k-1 faces. If the dice chooses a specific face, >>> choose that unselected element. Otherwise continue from step 3 using >>> dices with k-1, k-2, ..., 1 faces. >>> >>> This has O(n log n) complexity. There is one obvious optimization: >>> eliminate the first selected elements so we don't need to walk over them >>> at each iteration. It's unclear to me how this affects complexity. > > > This significantly increases the runtime by executing the random number > algorithm up to k-1 times per element. > > How is this different than just a linear search through the sparse array > for the random(0..k)th unused element? > > But I do concur that it provides a uniform map. However, wouldn't the > worst runtime be O(n^2)? i.e. k + k-1 + k-2 + k-3... + 1 iterations == k > *(k+1) / 2? I'm not sure if average runtime is going to be O(nlgn).
Average runtime is still going to be O(n^2), because the average element chosen should be k / 2 elements into the range. -Steve
