Alternate shuffle code for XBMC
#1
hi,

i was missing some features so i thought i'd try to add them.specifically, i missed a way to edit a playlist (move around some items in it) and playing a shuffled playlist.

i was surprised to see that in playlist.h/.cpp there were in fact functions to shuffle and to move an item in the playlist. did i just not find the control to activate them?

anyway, at work i was bored and decided to try to implement a shuffle for a vector (having seen that the playlist was a vector) and without knowing it was already implemented, came up with another implementation:

instead of:
---------------------------------------------------------
void cplaylist:Confusedhuffle()
{
   srand( timegettime() );

   int nitemcount = size();

   // iterate through each catalogue item performing arbitrary swaps
   for (int nitem=0; nitem<nitemcount; nitem++)
   {
       int narbitrary = rand() % nitemcount;

       cplaylistitem anitem = m_vecitems[narbitrary];
       m_vecitems[narbitrary] = m_vecitems[nitem];
       m_vecitems[nitem] = anitem;
   }
}
---------------------------------------------------------
i did the following:

---------------------------------------------------------
void cplaylist:Confusedhuffle()
{
   srand( timegettime() );

   int nitemcount = size();

   // iterate through each catalogue item selecting a random item for that index
   for (int nitem=0; nitem<nitemcount; nitem++)
   {
       int narbitrary = (rand() % (nitemcount-nitem))+nitem;

       if (narbitrary != nitem)
       {
           cplaylistitem anitem = m_vecitems[narbitrary];
           m_vecitems.erase(&m_vecitems[narbitrary]);
           m_vecitems.insert(&m_vecitems[nitem], anitem);
       }
   }
}
---------------------------------------------------------

to me, it feels like my code gives a better shuffled list, because i only swap items that haven't been swapped before. or do you guys think it makes no difference. maybe i should make a little test program, that displays lists shuffled with both methods.

on a side note, i was also working on a quicksort for vectors, and in the progress of that noticed that if you keep seeding rand() with the time, the random numbers don't differ greatly. (this was under windows and i seeded with srand(time(null))) wouldn't it be better to just call srand( timegettime() ) once for the whole media center?

please keep in mind, this is my first stab at coding for xbmc, i'm not all that familiar with the source yet :p

cheers,

remco
Reply
#2
heh when i first saw that code i thought the same thing you did about it not being a uniform shuffle, and there is certainly a difference.

mathematically there are n! possible permutations but the code produced n^n results. clearly that means permutations are duplicated in those results and since n^n is not a multiple of n! some permutations were more likely than others.

your code is more correct.

.....

actually removing and adding elements to a vector probably isnt as efficient as swapping the items.
Reply
#3
(asteron @ jan. 14 2005,20:36 Wrote:actually removing and adding elements to a vector probably isnt as efficient as swapping the items.
that's what i thought too, but i thought i'd do it this way, instead of creating a whole new vector and then doing a copy. this is more memory efficient.
Reply
#4
there should be a shuffle button in the playlist view. also a reasonable implemention of shuffle for a vector is:
std::random_shuffle(v.begin(), v.end());
i'm not sure why this isn't used. :p
Always read the XBMC online-manual, FAQ and search the forum before posting.
Do not e-mail XBMC-Team members directly asking for support. Read/follow the forum rules.
For troubleshooting and bug reporting please make sure you read this first.


Image
Reply
#5
that's probably because hardly anyone know it exists. Wink at least i didn't know, which is probably because it isn't in the vector documentation, but in some other part of the stl doc's.
i guess that call should be used for it.
i could find the shuffle selection, but how do you move an element in the playlist, using only the xbox controller.

and something else, anytime you shuffle the playlist, shouldn't the currently playing song be set as the first element. so all shuffled songs will be played after it? that also helps when you add a song to the playlist, you just call shuffle again and have a new shuffled playlist.

by the way, i can recommend the stl documentation from sgi instead of the msdn documentation if you want to find out how to do something specific. the sgi doc's give pre and post conditions, what input is accepted etc. etc. etc..

also, to get back to the insert and erase calls on the vector, i'm not completely sure those are that expensive (timewise). at least, i doubt the whole vector is reindexed everytime an element is inserted or removed somewhere in the middle. but this is all moot, if the random_shuffle call is used!

remco
Reply
#6
insert and erase in a vector anywhere but the end is o(n) time. if you're doing that once for each element you have a o(n²) algorithm, which is expensive.
a vector is usually an array - to insert into the middle you have to take all the elements after the insert point and copy them one element further along in the array. erase is similar but the other way.

std::random_shuffle is implemented using swaps so should run in o(n) time.
Always read the XBMC online-manual, FAQ and search the forum before posting.
Do not e-mail XBMC-Team members directly asking for support. Read/follow the forum rules.
For troubleshooting and bug reporting please make sure you read this first.


Image
Reply

Logout Mark Read Team Forum Stats Members Help
Alternate shuffle code for XBMC0