[mythtv] MythMusic playlists still not intelligent enough IMHO
Lasse Nisted
zartzartzart+mythtv-dev at gmail.com
Thu Apr 19 07:56:46 UTC 2007
On 4/19/07, Eskil Heyn Olsen <myth at eskil.org> wrote:
> On Wed, 2007-04-18 at 10:50 -0400, Dan Wilga wrote:
>
> > - choose the index of the first song, S, randomly: S = rand() % N
> > - afterward, each new song, S' is calculated like so: S' = (S + P) % N
> >
> > A mathematics guru friend of mine sent me the proof that this
> > sequence is guaranteed to visit each song exactly once, in a
> > pseudorandom order. It also has the advantage that the sequence is
>
> After looking at this, it seems that the pseudorandom order is just
> continuously adding P % N to S and wrapping at N. So essentially, let N
> be 50, P be 15485863 (big prime) and S0 be 20.
>
> S1 = (20 + 15485863) % 50 = 33
> S2 = (33 + 15485863) % 50 = 46
> S3 = (46 + 15485863) % 50 = 9
> S4 = (9 + 15485863) % 50 = 22
>
> essentially you just add 13 (15485863 % 50) every time. That seems sub
> pseudorandom to me. It even seems that the only reason you need a prime
> is to ensure that P % N isn't 0.
>
> Or did I (again) brainfart on something ?
>
> eskil
You are correct, eskil. a+b (mod n) = (a (mod n) + b (mod n)) (mod n).
Each song will be chosen exactly once, but not in a very random way.
Furthermore if P is chosen at compile time then the same order is used
if N does not change. The rand() only changes the starting point in
the sequence.
I have not followed the discussion, but why not simply create an array
[0,1,2,...,N-1] and shuffle this using STL's random_shuffle?
A playlist containing 32,000 songs results in a 1MB array, is that
really too large?
If it is, then the algorithm used in random_sample could be used to
select e.g. 1000 unique songs at random. When this list has been
played, select 1000 new unique songs (possibly some of those from the
first sample, but after 1000 songs one should not care?)
- Lasse Nisted
More information about the mythtv-dev
mailing list