Jump to page: 1 222  
Page
Thread overview
Re: random cover of a range
Feb 13, 2009
bearophile
Feb 13, 2009
dsimcha
Feb 13, 2009
Jason House
Feb 13, 2009
Denis Koroskin
Feb 13, 2009
bearophile
Feb 14, 2009
Don
Feb 13, 2009
Yigal Chripun
Feb 14, 2009
Yigal Chripun
Feb 13, 2009
Jason House
Feb 13, 2009
Jason House
Feb 13, 2009
bearophile
Feb 14, 2009
bearophile
Feb 14, 2009
bearophile
Feb 14, 2009
bearophile
Feb 14, 2009
bearophile
Feb 14, 2009
Bill Baxter
Feb 14, 2009
Bill Baxter
Feb 14, 2009
bearophile
Feb 14, 2009
Bill Baxter
Feb 14, 2009
bearophile
Feb 14, 2009
Christopher Wright
Feb 14, 2009
bearophile
Feb 14, 2009
Bill Baxter
OT -- Re: random cover of a range
Feb 14, 2009
John Reimer
Feb 14, 2009
grauzone
Feb 14, 2009
Yigal Chripun
Feb 15, 2009
BCS
Feb 14, 2009
Christopher Wright
Feb 15, 2009
John Reimer
Feb 15, 2009
John Reimer
Feb 15, 2009
John Reimer
Feb 15, 2009
John Reimer
Feb 15, 2009
BCS
Feb 15, 2009
Christopher Wright
Feb 15, 2009
Yigal Chripun
Feb 15, 2009
Nick Sabalausky
Feb 15, 2009
Yigal Chripun
Feb 16, 2009
Don
Feb 16, 2009
Christopher Wright
Feb 16, 2009
Denis Koroskin
Feb 16, 2009
Yigal Chripun
Feb 16, 2009
Jussi Jumppanen
Feb 16, 2009
Yigal Chripun
Feb 16, 2009
Denis Koroskin
Feb 17, 2009
Yigal Chripun
Feb 17, 2009
Denis Koroskin
Feb 17, 2009
Yigal Chripun
Feb 16, 2009
Christopher Wright
Feb 16, 2009
Denis Koroskin
Feb 17, 2009
Christopher Wright
Feb 16, 2009
Yigal Chripun
Feb 16, 2009
Yigal Chripun
Feb 17, 2009
Joel C. Salomon
Feb 15, 2009
Yigal Chripun
Feb 15, 2009
Christopher Wright
Feb 15, 2009
John Reimer
Feb 15, 2009
grauzone
Feb 15, 2009
John Reimer
Feb 15, 2009
grauzone
Feb 15, 2009
John Reimer
Feb 15, 2009
grauzone
Feb 15, 2009
John Reimer
Feb 15, 2009
Derek Parnell
Feb 15, 2009
John Reimer
Feb 15, 2009
Christopher Wright
Feb 15, 2009
John Reimer
Feb 15, 2009
Bill Baxter
Feb 15, 2009
John Reimer
Feb 15, 2009
Bill Baxter
Feb 15, 2009
John Reimer
Feb 15, 2009
Nick Sabalausky
Feb 15, 2009
Nick Sabalausky
Feb 15, 2009
superdan
Feb 15, 2009
Don
Feb 16, 2009
Walter Bright
Feb 16, 2009
John Reimer
Feb 16, 2009
Walter Bright
Feb 17, 2009
John Reimer
Feb 17, 2009
Bill Baxter
Feb 17, 2009
John Reimer
Feb 17, 2009
Bill Baxter
Feb 17, 2009
John Reimer
Feb 17, 2009
John Reimer
Feb 17, 2009
Walter Bright
Feb 17, 2009
John Reimer
Feb 17, 2009
Nick Sabalausky
Feb 17, 2009
John Reimer
Feb 17, 2009
Nick Sabalausky
Feb 17, 2009
Nick Sabalausky
Feb 17, 2009
Christopher Wright
Feb 17, 2009
Alexander Pánek
Feb 17, 2009
Walter Bright
Feb 17, 2009
Derek Parnell
Feb 17, 2009
John Reimer
Feb 17, 2009
John Reimer
Feb 17, 2009
Bill Baxter
Feb 17, 2009
Nick Sabalausky
Feb 17, 2009
Bill Baxter
Feb 17, 2009
Walter Bright
Feb 17, 2009
Daniel Keep
Feb 17, 2009
Nick Sabalausky
Feb 17, 2009
Nick Sabalausky
Feb 17, 2009
Nick Sabalausky
Feb 17, 2009
Yigal Chripun
Feb 17, 2009
Daniel de Kok
Feb 17, 2009
Yigal Chripun
Feb 17, 2009
Daniel de Kok
Feb 17, 2009
Bill Baxter
Feb 17, 2009
Mike Parker
Feb 18, 2009
Bill Baxter
Feb 18, 2009
Nick Sabalausky
Feb 18, 2009
Bill Baxter
Feb 18, 2009
Mike Parker
Feb 18, 2009
Mike Parker
Feb 18, 2009
John Reimer
Feb 18, 2009
Nick Sabalausky
Feb 19, 2009
John Reimer
Feb 19, 2009
Bill Baxter
Feb 17, 2009
Don
Feb 17, 2009
Anonymous Coward
Feb 17, 2009
Nick Sabalausky
Feb 17, 2009
Alexander Pánek
Feb 18, 2009
John Reimer
Feb 17, 2009
Daniel de Kok
Feb 18, 2009
John Reimer
Feb 17, 2009
Alexander Pánek
Feb 17, 2009
Daniel de Kok
Feb 17, 2009
Alexander Pánek
Feb 18, 2009
Alexander Pánek
Feb 17, 2009
Christopher Wright
Feb 16, 2009
Don
Feb 16, 2009
superdan
Feb 16, 2009
Nick Sabalausky
Feb 16, 2009
Walter Bright
Feb 16, 2009
Sean Kelly
Feb 16, 2009
Yigal Chripun
Feb 16, 2009
Ary Borenszweig
Feb 17, 2009
Joel C. Salomon
Feb 17, 2009
Yigal Chripun
Feb 17, 2009
Nick Sabalausky
Feb 17, 2009
Bill Baxter
Feb 17, 2009
Nick Sabalausky
Feb 17, 2009
Nick Sabalausky
Feb 17, 2009
Walter Bright
Feb 17, 2009
Nick Sabalausky
Feb 17, 2009
Derek Parnell
Feb 15, 2009
John Reimer
Feb 15, 2009
Nick Sabalausky
Re: way OT -- Re: random cover of a range
Feb 15, 2009
BCS
Feb 15, 2009
John Reimer
Feb 15, 2009
Nick Sabalausky
Feb 15, 2009
Nick Sabalausky
Feb 15, 2009
John Reimer
Feb 15, 2009
BCS
Feb 15, 2009
John Reimer
Feb 15, 2009
Mike Parker
Feb 15, 2009
John Reimer
Feb 15, 2009
Nick Sabalausky
Feb 15, 2009
BCS
Feb 15, 2009
BCS
Feb 15, 2009
John Reimer
Feb 16, 2009
Alexander Pánek
Feb 15, 2009
BCS
Feb 15, 2009
Nick Sabalausky
Feb 16, 2009
Daniel Keep
Feb 15, 2009
John Reimer
Feb 15, 2009
Nick Sabalausky
Feb 15, 2009
John Reimer
Feb 15, 2009
Nick Sabalausky
Feb 15, 2009
Nick Sabalausky
Feb 15, 2009
John Reimer
Feb 15, 2009
Walter Bright
Feb 16, 2009
BCS
Feb 16, 2009
John Reimer
Feb 16, 2009
Bill Baxter
Feb 16, 2009
Walter Bright
Feb 16, 2009
Bill Baxter
Feb 16, 2009
Nick Sabalausky
Feb 16, 2009
Alexander Pánek
Feb 18, 2009
John Reimer
Feb 15, 2009
Don
Feb 15, 2009
John Reimer
Feb 14, 2009
Denis Koroskin
Feb 14, 2009
bearophile
February 13, 2009
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
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
== 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
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
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
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
"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
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
"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
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

« First   ‹ Prev
1 2 3 4 5 6 7 8 9 10 11