[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kde-devel
Subject:    Noatun Playlists - Better random song selection
From:       Brendon Higgins <bh_doc () users ! sourceforge ! net>
Date:       2003-04-26 4:47:36
[Download RAW message or body]

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

Noatun kicks arse. I usually just turn it on, stick it on random over my whole 
collection, and let it rock away. Though I've noticed that the way songs are 
selected at random during play is a little, well, too random. I, and I assume 
most people, would like it to work similarly to the shuffle op in the 
playlist, but without actually shuffling anything, and still being random 
with songs that have been played a while ago - like repeatedly shuffling the 
tail-end of the list, so to speak.

Currently, the way the next song is selected is completely random with every 
song having the same probability of being selected, thought this is not a 
very "natural" way of doing this. The natural way would be for a song to be 
selected based on things like how long it's been since it was played before, 
relative to the other songs. It should be the case that after a while the 
number of times each song has been played should all be roughly the same.

It came to me the way to do this would be to have weightings associated with 
each song, and have those weightings proportional to how recently the song 
was played previously, or how many times the song has been played relative to 
the average of all songs. So I wrote a program to analyse some statistics of 
such methods (code attached; there is minimal commenting - if something isn't 
obvious just mail me), the most important statistic being the number of steps 
between each play of each individual song. This should be reasonably 
constant, ie. have a low standard deviation for each song, and thus a low 
average of all SDs for each song.

The best way I've found is the method in SimpleWeightedShuffler (the third 
complete Shuffler type) which at first spreads weightings evenly over all the 
songs, and for each song that gets picked its individual weighting is added 
evenly to all the others, and then is set to 0. This way a song will never be 
picked twice in a row, and if a song hasn't been played in a while it becomes 
more and more likely that it will be played. The current method does not 
guarantee this, and I'm always feeling that there are a few songs I haven't 
heard in ages while there are others that Noatun seems to want to play 
ad-nauseum.

I'm not sure if this is an area that anyone is interested in. It may be that 
this method is too bulky for some people, though it'd be fine for my 
purposes. I've had a short look at the split playlist source, but I decided 
I'd better let the pros handle it, first. I'm not likely to make a playlist 
plugin from this, but if anyone else would like to, great!

BTW, I'm not subscribed to the list, so CCs would be appreciated.

Peace,
Brendon Higgins

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)

iD8DBQE+qg9uCTfPD0Uw3q8RAo71AKCmx+Id8/j3sg16hLN4R3jes6Vu5wCgwhk4
NvCJOq84wQwCPzNfXWyGhxA=
=8DWI
-----END PGP SIGNATURE-----

["plshuffler.cpp" (text/x-c++src)]

#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>


template<typename T> double mean(std::vector<T>& v) {
    double ret = 0.0;
    for (int i = 0; i < v.size(); ++i) {
        ret += v[i];
    }
    return ret / v.size();
}

template<typename T> double stdDeviation(std::vector<T>& v, double mean) {
    double diff;
    double ret = 0.0;
    for (int i = 0; i < v.size(); ++i) {
        diff = v[i] - mean;
        ret += diff * diff;
    }
    return std::sqrt(ret / (v.size() - 1));
}

class BaseShuffler {
protected:
    std::vector<int> hist;
    std::vector< std::vector<int> > steps;
    std::vector<int> lastSteps;
    // the first steps number for each index should not be counted
    // as it is not representative of continuous operation.
    std::vector<bool> counting;

public:
    BaseShuffler(int m) {
        for (int i = 0; i < m; ++i) {
            hist.push_back(0);
            lastSteps.push_back(0);
            steps.push_back(std::vector<int>());
            counting.push_back(false);
        }
    }

    virtual ~BaseShuffler() {
    }

    virtual void debug() {
    }

    virtual int pick() = 0;

    // to be called after pick
    virtual void picked(int n) {
        ++hist[n];
        if (counting[n]) {
            steps[n].push_back(lastSteps[n]);
        } else {
            counting[n] = true;
        }
        for (int i = 0; i < lastSteps.size(); ++i) {
            ++lastSteps[i];
        }
        lastSteps[n] = 0;
    }

    std::vector<int>& getHist() {
        return hist;
    }

    void printStepStats() {
        std::vector<double> sdStats;
        for (int i = 0; i < steps.size(); ++i) {
            std::cout << "#Picks: " << steps[i].size();
            std::cout << "  Steps: ";
            for (int j = 0; j < steps[i].size(); ++j) {
                std::cout << steps[i][j] << ",";
            }
            double m = mean(steps[i]);
            double sd = stdDeviation(steps[i], m);
            sdStats.push_back(sd);
            std::cout << "  Avg: " << m << "  SD: " << sd << "\n";
        }
        double m = mean(sdStats);
        std::cout << "AvgSD: " << m << "  SDSD: "
            << stdDeviation(sdStats, m) << std::endl;
    }
};

class RandomShuffler: public BaseShuffler {
public:
    RandomShuffler(int m): BaseShuffler(m) {
    }

    virtual ~RandomShuffler() {
    }

    virtual int pick() {
        int p = std::rand() % hist.size();
        picked(p);
        return p;
    }
};

class WeightedShuffler: public BaseShuffler {
protected:
    std::vector<double> weights;

public:
    WeightedShuffler(int m): BaseShuffler(m) {
        // setup weights - all equal
        double p = 1.0 / m;
        for (int i = 0; i < m; ++i) {
            weights.push_back(p);
        }
    }

    virtual ~WeightedShuffler() {
    }

    virtual void debug() {
        double total = 0.0;
        for (int i = 0; i < weights.size(); ++i) {
            total += weights[i];
            std::cout << "  " << weights[i];
        }
        std::cout << "  T: " << total << "\n";
    }
};

class ComplexWeightedShuffler: public WeightedShuffler {
private:
    void histInspect(int* maxPos, int* minPos) {
        *maxPos = 0;
        *minPos = 0;
        for (int i = 1; i < hist.size(); ++i) {
            if (hist[i] < hist[*minPos]) {
                *minPos = i;
            }
            if (hist[i] > hist[*maxPos]) {
                *maxPos = i;
            }
        }
    }

    void calcWeights() {
        // Weights are spread linearly based on how far from the max
        // a given pos is.
        int maxPos, minPos;
        histInspect(&maxPos, &minPos);
        int maxDist = hist[maxPos] - hist[minPos];
        if (maxDist > 0) {
            double totalWeight = 0.0;
            for (int i = 0; i < hist.size(); ++i) {
                weights[i] = hist[maxPos] - hist[i]
                    // Plus some arbitrary enhancement to make it
                    // slightly more random than just "play only
                    // what's not already been played"
                    + double(maxDist) / hist.size();
                totalWeight += weights[i];
            }
            for (int i = 0; i < hist.size(); ++i) {
                weights[i] /= totalWeight;
            }
        } else {
            // There is no difference! Yippie!
            for (int i = 0; i < hist.size(); ++i) {
                weights[i] = 1.0 / hist.size();
            }
        }
    }

public:
    ComplexWeightedShuffler(int m): WeightedShuffler(m) {
    }

    virtual ~ComplexWeightedShuffler() {
    }

    virtual int pick() {
        calcWeights();
        double r = double(std::rand()) / RAND_MAX;
        int pos = -1;
        while (r > 0.0) {
            r -= weights[++pos];
        }
        picked(pos);
        return pos;
    }
};

class SimpleWeightedShuffler: public WeightedShuffler {
public:
    SimpleWeightedShuffler(int m): WeightedShuffler(m) {
    }

    virtual ~SimpleWeightedShuffler() {
    }

    virtual void picked(int n) {
        WeightedShuffler::picked(n);
        double x = weights[n] / (weights.size() - 1);
        for (int i = 0; i < weights.size(); ++i) {
            weights[i] += x;
        }
        weights[n] = 0.0;
    }

    virtual int pick() {
        double r = double(std::rand()) / RAND_MAX;
        int pos = -1;
        while (r > 0.0) {
            r -= weights[++pos];
        }
        picked(pos);
        return pos;
    }
};

void printHist(std::vector<int>& hist, int current) {
    for (int i = 0; i < hist.size(); ++i) {
        std::cout << " ";
        if (i == current) {
            std::cout << "+";
        } else {
            std::cout << " ";
        }
        std::cout << hist[i];
    }
}

void printStats(std::vector<int>& hist) {
    double m = mean(hist);
    std::cout << "  Mean: " << m << "  StdDev: " << stdDeviation(hist, m) << "\n";
}

int main() {
    std::srand(std::time(0));

    int max;
    std::cout << "Max: ";
    std::cin >> max;

    int num;
    std::cout << "Num shuffles: ";
    std::cin >> num;

    int type;
    std::cout << "(1) Random, (2) ComplexWeighted, (3) SimpleWeighted: ";
    std::cin >> type;

    int debug;
    std::cout << "Debug (1/0): ";
    std::cin >> debug;

    BaseShuffler* shuffler;

    if (type == 1) {
        shuffler = new RandomShuffler(max);
    } else if (type == 2) {
        shuffler = new ComplexWeightedShuffler(max);
    } else {
        shuffler = new SimpleWeightedShuffler(max);
    }

    int cur;

    for (int i = 0; i < num; ++i) {
        cur = shuffler->pick();
        //printHist(shuffler->getHist(), cur);
        //printStats(shuffler->getHist());
        if (debug == 1) {
            shuffler->debug();
        }
    }

    shuffler->printStepStats();

    delete shuffler;

    return 0;
}


>> Visit http://mail.kde.org/mailman/listinfo/kde-devel#unsub to unsubscribe <<


[prev in list] [next in list] [prev in thread] [next in thread]