Bug 44807 - Hayes randomize mode unusable
Summary: Hayes randomize mode unusable
Status: RESOLVED FIXED
Alias: None
Product: noatun
Classification: Miscellaneous
Component: hayes (show other bugs)
Version: unspecified
Platform: Compiled Sources Linux
: NOR normal
Target Milestone: ---
Assignee: Neil Stevens
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2002-07-06 15:18 UTC by Carsten Pfeiffer
Modified: 2003-01-16 15:56 UTC (History)
0 users

See Also:
Latest Commit:
Version Fixed In:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Carsten Pfeiffer 2002-07-06 15:17:03 UTC
(*** This bug was imported into bugs.kde.org ***)

Package:           noatun
Version:           KDE 3.0.2 
Severity:          normal
Installed from:    Compiled From Sources
Compiler:          Not Specified
OS:                Linux
OS/Compiler notes: Not Specified

I love the Hayes playlist because it is always synchronized to the contents of the harddisk -- no adding of new files/directories necessary.

But I have one big gripe with it: the randomize mode doesn't play the entire list of files before repeating songs. It even happened to me that it played the same song again after it had just finished.

It's really hard to keep on listening to the collection of soungs when songs are repeated again and again while others are never played.

(Submitted via bugs.kde.org)
Comment 1 Neil Stevens 2002-07-06 20:16:27 UTC
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

- -----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Saturday July 06 2002 08:17 pfeiffer@kde.org wrote:
> It's really hard to keep on listening to the collection of soungs when
> songs are repeated again and again while others are never played.

Well as it turns out it's hard to get a well-distributed shuffle mode 
when you have a policy of not opening directories in the KFileTreeView 
unless absolutely necessary.

Working on it though. :-)

- - -- 
Neil Stevens - neil@qualityassistant.com
"I always cheer up immensely if an attack is particularly wounding
because I think well if they attack one personally it means they
have not a single political argument left." - Margaret Thatcher
- -----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE9J0vkf7mnligQOmERAqBnAJsEZPmLsGMngCsH4fpmWUVIj50xmwCgkPqv
Qc6drT+FebTDLzlB/yeT/E8=
=jXL9
- -----END PGP SIGNATURE-----
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE9J1Abf7mnligQOmERAloKAJ90lx2RXViZgj2bjf12yV8NrfIg/wCfZCK4
b05KyYB6F0w5fE8cgOVi7Ro=
=Uo4x
-----END PGP SIGNATURE-----
Comment 2 Carsten Pfeiffer 2002-07-06 22:47:28 UTC
-----BEGIN PGP SIGNED MESSAGE-----

On Saturday 06 July 2002 22:16 Neil Stevens wrote:

> Well as it turns out it's hard to get a well-distributed shuffle mode
> when you have a policy of not opening directories in the KFileTreeView
> unless absolutely necessary.

I see -- you don't know the entire domain before.=20

What do you think of this idea:

You start with reading the toplevel directory so you know its contents (fi=
les=20
and directories). Every file gets a weight of 1 every directory a weight o=
f=20
say 50 (just a guessed number).=20

Now you choose a random file in the toplevel hierarchy. Directories will ha=
ve=20
a higher probability to get hit due to their bigger weight. As soon as a=
=20
directory is chosen you read its contents and adjust its weight according=
ly=20
(sum of the weight of all its files + its directories).

Repeat this until you have chosen a file.

Additionally you could keep a list of filenames that have been played alre=
ady=20
and continue choosing if necessary. You will know when you have played all=
=20
files (number of files =3D=3D number of played files && no unread directori=
es).

> Working on it though. :-)

Looking forward :)

Cheers
Carsten Pfeiffer
-----BEGIN PGP SIGNATURE-----

iQEVAwUBPSdzgaWgYMJuwmZtAQGMeQf/XmgaP8+MFpsGTpe8o7PC1KI2XbLm/LL8
qW5gyWYt6aazVyZYtKqOYVbSLsSPQ+hvmG8wTxck8c+2JSo567jaH3bhxs5ocLhH
vDEBXTtF6sayuAp6YAT7KHXxWMwMBWMmUTxLqay4HNQueppGF6x7rpIHEzNeJTuS
oMFxoWjC4Wkwyaw20jrUJwy/CPVifc8fj1+Vol1EW+m0c5MwLx3gDL4NrCVtyVZB
Q7N+M9oGsmRvPjvtbaTE51INsKAWJqfnkFN/zvHlyGOZq7EyjwZIkkN67THZqpRh
vHLvwJzLPFwFjwJL40E/zqIuBSOQoWDeiI/a0iyiNTI1UdcUbXHaCg=3D=3D
=3DR2RZ
-----END PGP SIGNATURE-----
Comment 3 Neil Stevens 2002-07-07 00:51:56 UTC
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Saturday July 06 2002 03:47 Carsten Pfeiffer wrote:
> On Saturday 06 July 2002 22:16 Neil Stevens wrote:
> > Well as it turns out it's hard to get a well-distributed shuffle
> > mode when you have a policy of not opening directories in the
> > KFileTreeView unless absolutely necessary.
>
> I see -- you don't know the entire domain before.
>
> What do you think of this idea:
>
> You start with reading the toplevel directory so you know its contents
> (files and directories). Every file gets a weight of 1 every directory
> a weight of say 50 (just a guessed number).
>
> Now you choose a random file in the toplevel hierarchy. Directories will
> have a higher probability to get hit due to their bigger weight. As
> soon as a directory is chosen you read its contents and adjust its
> weight accordingly (sum of the weight of all its files + its
> directories).
>
> Repeat this until you have chosen a file.

Heh.. you just rewrote exactly my idea that I plan to implement almost 
word for word how I described it. :-)

The biggest reason Hayes hasn't had it done already is that Hayes' position 
in the release was uncertain.. I was waiting on it moving to nonbeta or 
extragear or addons or something.

thanks!

- -- 
Neil Stevens - neil@qualityassistant.com
"I always cheer up immensely if an attack is particularly wounding
because I think well if they attack one personally it means they
have not a single political argument left." - Margaret Thatcher
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE9J5Csf7mnligQOmERAnleAKCYclwnCzyZ9MSS5s/Sg0nHS06VQwCcCZGW
SKM827PEXYvM9gN3PNOhYWQ=
=VnuO
-----END PGP SIGNATURE-----
Comment 4 erayo 2002-07-07 10:50:14 UTC
On Sunday 07 July 2002 03:51 Neil Stevens wrote:
>
> Heh.. you just rewrote exactly my idea that I plan to implement almost
> word for word how I described it. :-)
>
> The biggest reason Hayes hasn't had it done already is that Hayes' position
> in the release was uncertain.. I was waiting on it moving to nonbeta or
> extragear or addons or something.

Carsten's solution sounds similar to the one I thought for dub but we still 
can't get uniform distribution :) Some songs aren't gonna be played. 

There are usually two problems with shuffle functions in playlist codes:

1) Some songs are repeatedly played some aren't played
2) Songs are played in the same order like a crappy radio station

The mp3 directory is a tree with a number of songs at each node. Knowing that 
we can make a perfect shuffling of all songs without any of these problems 
since we can give each song a number. This might be a better sol'n *and* to 
construct the shuffle table you don't need to read the file info for each 
song. You could simply assume every file is a media file and then those 
unplayable files will be skipped anyway. This does away with 1. To address 2 
you can give the user a choice to re-shuffle his index since we can handle 
shuffling by creating an array [1..n] and then running a random shuffle 
algorithm on it. There will be a model of the directory hierarchy in memory 
that maps index -> file.

I'll try to implement this for dub and you can take a peek ;)

See ya

-- 
Eray Ozkural <erayo@bilkent.edu.tr>
Comp. Sci. Dept. Bilkent University Ankara
www: http://www.cs.bilkent.edu.tr/~erayo
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C
Comment 5 Neil Stevens 2002-07-07 12:25:50 UTC
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Sunday July 07 2002 03:50 Eray Ozkural wrote:
> The mp3 directory is a tree with a number of songs at each node. Knowing
> that we can make a perfect shuffling of all songs without any of these
> problems since we can give each song a number.

No we can't. at least in Hayes.  We can't enumerate files we can't see!  
That's the problem here.  There's a list of directories whose contents are 
unknown to us.  Hayes does not scan directories until absolutely 
necessary.

To go an open an entire Hayes list can be very expensive especially if the 
directory is on another computer.  So an essential tradeoff of Hayes is 
that the shuffle cannot be a perfect uniform distribution.  The best we 
can do is get progressively better estimations until the entire tree is 
opened.

> This might be a better
> sol'n *and* to construct the shuffle table you don't need to read the
> file info for each song.

Well that would be possible but I don't think getting a *perfect* uniform 
distribution is needed.  We just need to avoid 1) the same ordering and 2) 
high repeats as you point out.

Hayes will solve 1) by using decent pseudo-random numbers from KApp.  Hayes 
won't have the problem of some files being played over and over a lot if 
we give a high initial weight for directories like 1000 or something.  
That would make unopened directories will always be preferred to opened 
directories and to files.  And as an added bonus it would make unopened 
directories get opened frequently bringing the distribution close to 
uniform more quickly.

Hm... Maybe the weighting for unopenend dirs should be scaled depending on 
the total known weights.

On real uniform distribution:  Once every directory is openend and the 
weights are accurate then it *is* a uniform distribution.  Consider a 
directory that contains a file and a subdirectory and that subdirectory 
contains two files.  The subdirectory would get a weight of 2 and the 
file gets a weight of 1:

      -- 1/3 --  file
     |                        --- 1/2 -- file
- -----                         |
     |-- 2/3 --  directory -- |-- 1/2 -- file


There are three files and each has a 1/3 chance of being played.  This is 
basic probability here but if you can find a counterexample to the 
weightings working please let me know.

> You could simply assume every file is a media
> file and then those unplayable files will be skipped anyway. This does
> away with 1. To address 2 you can give the user a choice to re-shuffle
> his index since we can handle shuffling by creating an array [1..n] and
> then running a random shuffle algorithm on it. There will be a model of
> the directory hierarchy in memory that maps index -> file.

I agree that if you know the entire tree in advance then your method 
works.   It might even be best for Dub for all I know. :-)

- -- 
Neil Stevens - neil@qualityassistant.com
"I always cheer up immensely if an attack is particularly wounding
because I think well if they attack one personally it means they
have not a single political argument left." - Margaret Thatcher
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE9KDNOf7mnligQOmERAqEAAKCTrg7xEStNmi8Uyrz+pIDkSbKDOQCeLSKj
uG763KtH6xdtCXZS7Pv+vVI=
=ZF+M
-----END PGP SIGNATURE-----
Comment 6 Neil Stevens 2003-01-16 15:40:29 UTC
Implemented in Hayes 1.2. 
Comment 7 Carsten Pfeiffer 2003-01-16 15:50:40 UTC
Subject: Re:  Hayes randomize mode unusable

On Thursday 16 January 2003 15:40, you wrote:

> 15:40 ------- Implemented in Hayes 1.2.

So are you going to put it into kdeaddons again?

Cheers
Carsten Pfeiffer
-----BEGIN PGP SIGNATURE-----

iQEVAwUBPibGg6WgYMJuwmZtAQGVcwf7B3GW81hITeHfd0G4pK/ieM2S5y96RI9x
lTbbaHH5sj3SfDkr7OQtUFlU4q+dMSgPG8dB+4271EVW5JoUa0IJUpZck+HZtgjL
+o9ryXsLLG2em75fFIA1X66m//Wmf4OWwJE3eN938H/dGfIqW2km8gFoc/DpaNyg
hYnZO4pKpQB2KPv/PJD/MS5Aiz92eTrIPkxSL5b+6gdEGxnPac2c6tbU0yLNSUS4
KYX2dMg9jlwt7Sty/qJRkTnvmCkQFJBIOQq0QsUiGnqXOI25IsmsrLQ56N/7PwRh
OWqGNBVmhBQqOMfu8L9AgcHWPf/eVc4wBWkn3iGLVqcVWWyCRMWQOw==
=iZeu
-----END PGP SIGNATURE-----

Comment 8 Neil Stevens 2003-01-16 15:56:39 UTC
I would be willing to return it to addons if it were going to be in the release. 
 
However Charles has shown no willingness to have it in the release, as he disables it 
whenever anyone enables it. 
Comment 9 Carsten Pfeiffer 2003-01-16 16:07:17 UTC
Subject: Re:  Hayes randomize mode unusable

On Thursday 16 January 2003 15:56, you wrote:

> 15:56 ------- I would be willing to return it to addons if it were going to
> be in the release.
>
> However Charles has shown no willingness to have it in the release, as he
> disables it whenever anyone enables it.

I don't think Charles has the authority to disable other people's code.

Cheers
Carsten Pfeiffer
-----BEGIN PGP SIGNATURE-----

iQEVAwUBPibJv6WgYMJuwmZtAQF4DQf/ftQ4QXxM8DHJkgKAYHsvm9wetEwPDexe
/PbNTngLs5y6FK5NlTS1xYDTqlP4gRp5f+W+xLOhawcgyyhRFVmlGk2sTT6cXpuh
4aXEAWKPUW9d1xbf6AOp4Man2B1htfoRQbcyTfJMw8/nphL2J96B2sIwaW9v+3LK
tO1jTph1SSOSGl/mCCn2BvG+Pmep6ltHaDtJdz3K/o2zBC6p9UjAmURAfIH62jEG
iWyy06tvY4gXJElpcmpyxDTECpjdCyVcK/q45SNjp5WyZNmgFywHmco7rCVdezVw
Ec9z7ECxJtyhPIMSDvKwncYhA+p7ujVi4wi1ot/2g6gr5RnWUZN+lg==
=oCgo
-----END PGP SIGNATURE-----

Comment 10 Neil Stevens 2003-01-20 03:06:10 UTC
Subject: Noatun Hayes in KDE 3.2?

What would people say to Noatun Hayes in kdeaddons for KDE 3.2?

On one hand, I have a Noatun maintainer who insists he has the say on 
whether Hayes belongs in there, and in fact has disabled that plugin 
several times as different people have enabled it.  I got tired of that, 
so I removed Hayes from CVS.

On the other hand, now that I've removed Hayes from CVS, I'm being told by 
users, like the one in Bug 44087, to ignore that Noatun maintainer, and 
get Hayes into kdeaddons.

Who's right?  I'm perfectly happy to make separate releases, but it looks 
like many of my best testers and contributors want the thing in kdeaddons, 
and that'd be fine by me, too.