Iterating over the result of a member function

Question

I have code that creates several object instances (each instance having a fitness value, among other things) from which I want to sample N unique objects using weighted selection based on their fitness values. All objects not sampled are then discarded (but they need to be initially created to determine their fitness value).

my current code looks something like this:

vector<Item> getItems(..) {
    std::vector<Item> items
    .. // generate N values for items
    int N = items.size();

    std::vector<double> fitnessVals;
    for(auto it = items.begin(); it != items.end(); ++it)
        fitnessVals.push_back(it->getFitness());

    std::mt19937& rng = getRng();
    for(int i = 0, i < N, ++i) {
        std::discrete_distribution<int> dist(fitnessVals.begin() + i, fitnessVals.end());
        unsigned int pick = dist(rng);
        std::swap(fitnessVals.at(i), fitnessVals.at(pick));
        std::swap(items.at(i), items.at(pick));
    }
    items.erase(items.begin() + N, items.end());
    return items;
}

Typically ~10,000 instances are initially created, with N being ~200. The fitness value is non-negative, usually valued at ~70. It could go as high as ~3000, but higher values are increasingly more unlikely.

Is there an elegant way to get rid of the fitnessVals vector? Or perhaps a better way to do this in general? Efficiency is important, but I'm also wondering about good C++ coding practices.

Answer 1

If you're asking whether you can do this just with the items in your items vector, the answer is yes. The following is a rather hideous but none-the-less effective way to do that: I apologize in advance for the density.

This wraps the unsuspecting container iterator in another iterator of our own devices; one that pairs it with a member function of your choice. You may have to dance with const in this to get it to work correctly with your member function choice. That task i leave to you.

template<typename Iter, typename R>
struct memfn_iterator_s :
    public std::iterator<std::input_iterator_tag, R>
{
    using value_type = typename std::iterator_traits<Iter>::value_type;

    memfn_iterator_s(Iter it, R(value_type::*fn)())
        : m_it(it), mem_fn(fn) {}

    R operator*()
    {
        return ((*m_it).*mem_fn)();
    }

    bool operator ==(const memfn_iterator_s& arg) const
    {
        return m_it == arg.m_it;
    }

    bool operator !=(const memfn_iterator_s& arg) const
    {
        return m_it != arg.m_it;
    }

    memfn_iterator_s& operator ++() { ++m_it; return *this; }

private:
    R (value_type::*mem_fn)();
    Iter m_it;
};

A generator function follows to create the above monstrosity:

template<typename Iter, typename R>
memfn_iterator_s<Iter,R> memfn_iterator(
    Iter it, 
    R (std::iterator_traits<Iter>::value_type::*fn)())
{
    return memfn_iterator_s<Iter,R>(it, fn);
}

What this buys you is the ability to do this:

auto it_end = memfn_iterator(items.end(), &Item::getFitness);
for(unsigned int i = 0; i < N; ++i)
{
    auto it_begin = memfn_iterator(items.begin()+i, &Item::getFitness);
    std::discrete_distribution<unsigned int> dist(it_begin, it_end);
    std::swap(items.at(i), items.at(i+dist(rng)));
}
items.erase(items.begin() + N, items.end());

No temporary array is required. The member function is called for the respective item when required by the discrete distribution (which usually keeps it own vector of weights, and as such replicating that effort would be redundant).

Dunno if you'll get anything helpful or useful out of that, but it was fun to think about.

Answer 2

It's pretty nice that they have a discrete distribution in STL. As far as I know, the most efficient algorithm for sampling from a set of weighted objects (i.e., with probability proportional to weights) is the alias method. There's a Java implementation here: http://www.keithschwarz.com/interesting/code/?dir=alias-method

I suspect that's what the STL discrete_distribution uses anyway. If you're going to be calling your getItems function frequently, you might want to create a "FitnessSet" class or something so that you don't have to build your distribution every time you want to sample from the same set.

EDIT: Another suggestion... If you want to be able to delete items, you could instead store your objects in a binary tree. Each node would contain the sum of the weights in the subtree beneath it, and the objects themselves could be in the leaves. You could select an object through a series of log(N) coin tosses: at a given node, choose a random number between 0 and node.subtreeweight. If it's less than node.left.subtreeweight, go left; otherwise go right. Continue recursively until you reach a leaf.

Answer 3

I would try something like the following (see code comments):

#include <algorithm>                 // For std::swap and std::transform
#include <functional>                // For std::mem_fun_ref
#include <random>                    // For std::discrete_distribution
#include <vector>                    // For std::vector
size_t
get_items(std::vector<Item>& results, const std::vector<Item>& items)
{
    // Copy the items to the results vector. All operations should be
    // done on it, rather than the original items vector.
    results.assign(items.begin(), items.end());

    // Create the fitness values vector, immediately allocating
    // the number of doubles required to match the size of the
    // input item vector.
    std::vector<double> fitness_vals(results.size());

    // Use some STL "magic" ...
    // This will iterate over the items vector, calling the
    // getFitness() method on each item, and storing the result
    // in the fitness_vals vector.
    std::transform(results.begin(), results.end(),
                   fitness_vals.begin(),
                   std::mem_fun_ref(&Item::getFitness));

    //
    std::mt19937& rng = getRng();
    for (size_t i=0; i < results.size(); ++i) {
        std::discrete_distribution<int> dist(fitness_vals.begin() + i, fitness_vals.end());
        unsigned int pick = dist(rng);
        std::swap(fitness_vals[ii], fitness_vals[pick]);
        std::swap(results[i], results[pick]);
    }

    return (results.size());
}

Instead of returning the results vector, the caller provides a vector into which the results should be added. Also, the original vector (passed as the second parameter) remains unchanged. If this is not something that concerns you, you can always pass just the one vector and work with it directly.

I don't see a way to not have the fitness values vector; the discrete_distribution constructor needs to have the begin and end iterators, so from what I can tell, you will need to have this vector.

The rest of it is basically the same, with the return value being the number of items in the result vector, rather than the vector itself.

This example makes use of a number of STL features (algorithms, containers, functors) which I have found to be useful and part of my day-to-day development.

---

Edit: the call to items.erase() is superfluous; items.begin() + N where N == items.size() is equivalent to items.end(). The call to items.erase() would equate to a no-op.