February 13, 2009 Re: random cover of a range | ||||
---|---|---|---|---|
| ||||
Andrei Alexandrescu>The quest for finding a random cover of an array with as little extra memory consumed and with good complexity is on!< This thread is very long and complex, I am unable to understand where to start reading, etc. So can someone explain the problem to me, so I may be able to suggest some idea/code? Bye and thank you, bearophile |
February 13, 2009 Re: random cover of a range | ||||
---|---|---|---|---|
| ||||
Posted in reply to bearophile | bearophile wrote:
> Andrei Alexandrescu>The quest for finding a random cover of an array
> with as little extra memory consumed and with good complexity is on!<
>
>
> This thread is very long and complex, I am unable to understand where
> to start reading, etc. So can someone explain the problem to me, so I
> may be able to suggest some idea/code?
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.
Andrei
|
February 13, 2009 Re: random cover of a range | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | == Quote from Andrei Alexandrescu (SeeWebsiteForEmail@erdani.org)'s article > bearophile wrote: > > Andrei Alexandrescu>The quest for finding a random cover of an array with as little extra memory consumed and with good complexity is on!< > > > > > > This thread is very long and complex, I am unable to understand where to start reading, etc. So can someone explain the problem to me, so I may be able to suggest some idea/code? > 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. > Andrei One important thing to add, since we already have a solution that would be good except for this requirement: The frequency with which each of the N! permutations of each array occur must be uniform. |
February 13, 2009 Re: random cover of a range | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | 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.
Andrei
|
February 13, 2009 Re: random cover of a range | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | 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.
>
>
> Andrei
This seems to work for forward ranges as well. I'll be darned.
Andrei
|
February 13, 2009 Re: random cover of a range | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | 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.
>>
>>
>> Andrei
>
> This seems to work for forward ranges as well. I'll be darned.
>
> Andrei
what do you mean by "If the dice chooses a specific face"?
I don't understand this wording..
|
February 13, 2009 Re: random cover of a range | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | "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).
-Steve
|
February 13, 2009 Re: random cover of a range | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | Andrei Alexandrescu:
> 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.
I have faced such problem more than once, and I have tried to solve it in various ways. The faster solution was:
- create an array of m bits, set to zero
- Use a random generator to generate integer numbers in [0, m-1], if the corresponding big is set, extract another random number, if it's not set then set it, increment a counter, and return the array item that corresponds to the bit.
- When about 90% of the bits is set, create an array with the remaining 10% items of the array, shuffle them in place with the usual algorithm by Knuth, and return them.
This is faster than more complex alternatives, and doesn't use much memory.
(In the recent past I have tried more complex alternatives, like creating a second bitarray, etc, but they are a waste of time).
Bye,
bearophile
|
February 13, 2009 Re: random cover of a range | ||||
---|---|---|---|---|
| ||||
Posted in reply to Steven Schveighoffer | "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
|
February 13, 2009 Re: random cover of a range | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | 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. Roll die to get x in 0..k. If x==0, select this element, otherwise decrement x. > 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. If x==0, return element, otherwise decrement x. This trick saves a lot of random number generation. > This has O(n log n) complexity. O(n^2). > 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. > > Andrei |
Copyright © 1999-2021 by the D Language Foundation