5
\$\begingroup\$

[NOTE] This question can be depreciated in favor of version 0.3.

This is a code revision of a previous post and works well.

Code has been reworked to be far more clear and concise, thanks to reviewer suggestions. Redundant and unnecessary data structures have been removed, and code has been made more consistent with C++11.

The purpose of this code is to produce a universe of points, randomly generated around predetermined centroids, provided as a vector of vectors. The final product is a file of sample points, to be used for fake data analysis in another program. The objective here was brevity and speed - I feel the code could be vastly concisified, but it is working.

Detailed description of the primary algorithm parameters is in the .h.

My goal is two-fold: speed and conciseness (in code). Speed takes precedence over conciseness, but thankfully they tend to go hand in hand.

clustergen.h

#include <string>
#include <vector>
#include <iostream>
#include <fstream>
#include <sstream>
#include <random>
#include <chrono>

#ifndef CLUSTERGEN_H
#define CLUSTERGEN_H

// POINT GENERATION - COMMON USER DEFINED VARIABLES
double const PT_BOUND = 10;   // Defines the +/- around a centroid for point generation if UNIFORM
double const PT_SD = 5;       // Defines the stddev around a centroid for point generation if NORMAL

// PRIMARY ALGORITHM
void clustergen(unsigned int k, std::vector<std::vector<double>> &c, std::string file_out, std::string file_rpt, bool csv, bool norm);
// Produces [k] points in [file_out]; all points are separated by line breaks
// If [csv] = 0, dimensions for each point are whitespace-separated
// If [csv] = 1, dimensions for each point are comma-separated
// [c] is a vector of vectors; it's size is the number of centroids
// The first insertion in [c] sets dimensional precedence; dimensional mismatches are always omitted/avoided.

#endif //CLUSTERGEN_H

clustergen.cpp

#include "clustergen.h"

void clustergen(unsigned int k, std::vector<std::vector<double>> &c, std::string file_out, std::string file_rpt, bool csv, bool norm) {

    std::default_random_engine gen(std::chrono::system_clock::now().time_since_epoch().count());   // Random seed
    std::ofstream fout(file_out);                // This is the useful output of all points
    std::ofstream rout(file_rpt);                // Report file to avoid console output
    std::vector<unsigned int> ct(c.size(), 0);   // Independent counting vector for reporting
    auto ct_iter = ct.begin();                   // Counting vector iterator - used below primary for()

    rout << "CLUSTERGEN STATUS REPORT FOLLOWS..." << std::endl;   // Begin reporting to file

    for (auto c_iter = c.begin(); k > 0; --k) {
        if (c_iter == c.end()) { c_iter = c.begin(); }       // Continuously loop through cluster vec until k = 0
        if (ct_iter == ct.end()) { ct_iter = ct.begin(); }   // Continuously loop through counting vec until k = 0

        for (auto d_iter = c_iter->begin(); d_iter != c_iter->end(); ++d_iter) {
            if (norm) {
                // Point generation occurs NORMALLY distributed around centroid
                std::normal_distribution<double> distr(*d_iter, PT_SD);
                fout << distr(gen);
            } else {
                // Point generation occurs UNIFORMLY distributed around centroid
                std::uniform_real_distribution<double> distr(*d_iter - PT_BOUND, *d_iter + PT_BOUND);
                fout << distr(gen);
            }

            std::vector<double>::iterator temp_d_iter = d_iter;   // Used to peek at the next dimensional element

            if (++temp_d_iter != c_iter->end()) { (csv == 0) ? (fout << " ") : (fout << ","); }   // WS or CSV
            else if (k > 1) { fout << std::endl; }   // Line break on all but last line
        }
        ++c_iter;
        ++(*ct_iter);
        ++ct_iter;
    }
    // Reporting to file follows
    unsigned int ct_tot = 0;
    unsigned int i = 0;
    for (ct_iter = ct.begin(); ct_iter != ct.end(); ++ct_iter) {
        rout << std::endl << *ct_iter << " points ";
        rout << ((norm) ? "normally" : "uniformly");
        rout << " distributed around centroid " << ++i << " ...";
        ct_tot += *ct_iter;
    }
    rout << std::endl << std::endl << ct_tot << " total points assigned.";
}

main.cpp

#include "clustergen.h"

int main() {
    std::vector<std::vector<double>> v = {{0,0}, {50,30}, {100,120}};
    clustergen(11, v, "clustergen_out.dat", "clustergen_report.dat", 1, 0);
    // Will generate 11 points around the three given centroids in vector [v]
    // Points will be CSV and UNIFORMLY distributed.
}
\$\endgroup\$
  • \$\begingroup\$ Please note, this question can be depreciated in favor of version 0.3. \$\endgroup\$ – Miller Aug 16 '17 at 20:01
3
\$\begingroup\$

This code looks pretty good, but here are some things that may help you further improve it.

Separate interface from implementation

The interface goes into the .h file and the implementation goes into the .cpp file. Part of the interface is the required headers. What you have is not wrong, but I generally keep only the header files necesary for the interface in the .h file and anything that's not visible goes into the .cpp file. In this case, that means that <string> and <vector> would stay in the .h file and all other #includes go into the .cpp file. Also, if you put the include guard as the very first line of the file, the preprocessor may be sped up slightly because it doesn't have to scan the #include files.

Consider using an object

The PT_BOUND and PT_SD constants are described in the comments as user-defined variables and are required for clustergen(), but any user wanting to change them would have to touch the include file. Instead, I'd suggest using an object that contains the constants and defining a constructor that takes those two constants as parameters. This, for example:

class Cluster {
    double const PT_BOUND;
    double const PT_SD;

public:
    Cluster(double pt_bound = 10, double pt_sd = 5) :
        PT_BOUND{pt_bound}, 
        PT_SD{pt_sd}
    {}
    void gen(unsigned int k, std::vector<std::vector<double>> &c, std::string file_out, std::string file_rpt, bool csv, bool norm) const;
};

Split the function into smaller pieces

Right now, the function opens two files, cycles through the passed points generating each coordinate individually and writes both data and report. I'd suggest breaking those into individual functions. For example, I'd suggest creating a function to generate points around and individual point. Here's one way to write it (as an object member function):

std::vector<std::vector<double>> Cluster::around(const std::vector<double> &p, unsigned n) const {
    static std::default_random_engine gen{std::random_device{}()};
    std::vector<std::vector<double>> res;
    res.reserve(n);
    for ( ; n; --n) {
        std::vector<double> point;
        point.reserve(p.size());
        for (const auto t : p) {
            point.push_back(std::uniform_real_distribution<double>{t- PT_BOUND, t + PT_BOUND}(gen));
        }
        res.push_back(point);
    }
    return res;
}

Note that the random engine is static so it's only initialized once. Not only is this a more flexible function generally, it makes your original much easier to write.

Re-order the operations for better modularity

Instead of cycling through each point multiple times to create the random clustered points, you could instead create the points around each cluster first. That makes it easier to use functions like the one above. Here's how a refactored gen might look:

void Cluster::gen(unsigned int k, std::vector<std::vector<double>> &c, std::string file_out, std::string file_rpt, bool csv, bool norm) const {
    std::vector<std::vector<double>> pts;
    pts.reserve(k);
    const unsigned n = k / c.size();
    unsigned rem = k % c.size();
    for (const auto &point : c) {
        auto cloud = around(point, n + (rem ? 1 : 0));
        pts.insert(pts.end(), cloud.begin(), cloud.end());
        if (rem) 
            --rem;
    }
    print(file_out, pts, (csv ? ',' : ' '));
    report(file_rpt, c, k, norm);
}

The around() function (there's probably a better name!) is shown above. The print and report functions are each only a few lines long and quite simple.

Pass ostream& rather than file names

Instead of passing a file name as a string, it's often advantageous to use a more flexible interface by passing a std::ostream&. That allows things such as using a stringstream for output.

Reconsider the interface

At the moment, the main function has a lot of parameters:

void clustergen(unsigned int k,   // desired number of random points
                std::vector<std::vector<double>> &c,  // cluster loci
                std::string file_out,   // data file name
                std::string file_rpt,   // report file name
                bool csv,               // csv or space
                bool norm);             // norm or uniform dist

It's a lot to track. Rather than have one function do everything with multiple options, consider instead separating the generation of the points from the reporting, as I've hinted at above. Also, instead of passing a bool for csv, I'd suggest passing a separation character instead, so that if someone wanted to have, say, a tab delimited output, that could trivially be accommodated. In that same vein, but with a little more complexity, consider passing in a random function rather than only having two fixed distributions. I show how that might work in the next suggestion.

Don't unnecessarily restrict user flexibility

This goes for a lot of things already mentioned in which relatively small changes could be made to accommodate much more flexibility (and presumably usefulness) of your code. One in particular, that I thought might be worth illustrating in more detail is in passing in a function instead of having just two fixed distributions selected via a passed bool. Here's how I'd do it:

std::vector<std::vector<double>> Cluster::around(const std::vector<double> &p, 
        unsigned n, 
        std::function<double(double)> &rnd) 
{
    std::vector<std::vector<double>> res;
    res.reserve(n);
    for ( ; n; --n) {
        std::vector<double> point;
        point.reserve(p.size());
        for (const auto t : p) {
            point.push_back(rnd(t));
        }
        res.push_back(point);
    }
    return res;
}

This now uses std::function which provides a great deal of flexibility in how this is used. For example, we might want to use a multimodal distribution such that each number is normally distributed around three values \$\{ x-n, x, x+n \}\$. With \$x\$ being the original coordinate and \$n\$ being some supplied constant. Here's one way to do that:

static double my_dist(double mean, double stddev, double ringdist) {
    static std::default_random_engine gen{std::random_device{}()};
    std::bernoulli_distribution a{0.25};
    std::bernoulli_distribution b{0.5};
    if (a(gen)) {  // flip a coin
        return std::normal_distribution<double>{mean,stddev}(gen);  // inner
    }
    // outer
    return mean+(b(gen) ? 1 : -1)*std::normal_distribution<double>{ringdist,stddev}(gen);
}

You may have noticed that this function takes three parameters, while the std::function above only takes one. We can use std::bind to make that work. Here's a complete program:

int main() {
    std::vector<std::vector<double>> v = {{0,0}, {50,30}, {0,100}};
    unsigned k = 10000;
    const auto file_out{"clustergen_out.dat"};
    std::vector<std::vector<double>> pts;
    pts.reserve(k);
    const unsigned n = k / v.size();
    unsigned rem = k % v.size();
    double bound = 2;
    double ring = 10;
    std::function<double(double)> rnd{std::bind(my_dist, std::placeholders::_1, bound, ring)};
    for (const auto &point : v) {
        auto cloud = Cluster::around(point, n + (rem ? 1 : 0), rnd);
        pts.insert(pts.end(), cloud.begin(), cloud.end());
        if (rem) 
            --rem;
    }
    Cluster::print(file_out, pts, ' ');
}

Note that because we no longer need the parameters PT_BOUND or the like, all of the Cluster class member functions can be static (or alternatively, just group them in a namespace). We use std::bind to bind the function arguments and then create the requisite std::function to actuallly pass to the around function. Here's a plot of the resulting data: data plot

I had originally thought that it would be interesting to do something like a 2-d version of an electron's radial probability function, but with this code we only get nine clumps instead of concentric rings because we're considering each coordinate individually rather than computing over the entire vector of coordinates. There are a number of ways to effect such a change, but I'll leave that to you.

\$\endgroup\$
  • 1
    \$\begingroup\$ Edward - this is gorgeous, thank you! Here's the argument that's going on in my head: I was avoiding going OO with this program for conciseness' sake. The impetus behind this is that I'm going to produce two wrappers - one to intake a file of centroids, the other to randomly produce a set of centroids (<- this will require a whole other set of user inputs), however I'm starting to see that this will need to be objectified... \$\endgroup\$ – Miller Aug 13 '17 at 15:42
  • 1
    \$\begingroup\$ And put the include guard before the includes to save some compilation time. \$\endgroup\$ – Emily L. Aug 13 '17 at 15:52
2
\$\begingroup\$

Put the #includes inside the header guards:

#ifndef CLUSTERGEN_H
#define CLUSTERGEN_H

#include <string>
#include <vector>
#include <iostream>
#include <fstream>
#include <sstream>
#include <random>
#include <chrono>

You don't need all these #includes in the header. As you only use std::vector and std::string inside the header, I would expect your includes in the header to be

#include <string>
#include <vector>

void clustergen(unsigned int k, std::vector<std::vector<double>> &c, std::string file_out, std::string file_rpt, bool csv, bool norm);

That's quite a long line, you may want to wrap it:

void clustergen(unsigned int k, std::vector<std::vector<double>> &c,
        std::string file_out, std::string file_rpt,
        bool csv, bool norm);

But then, from here it is clear that you are taking filenames that you will open inside the function to write to. This is not ideal. As a user, I'd want to use std::istream or std::ostream:

// requires #include <ostream>
void clustergen(unsigned int k, std::vector<std::vector<double>> &c,
        std::ostream& file_out, std::ostream& file_rpt,
        bool csv, bool norm);

Your parameter order is also strange. Currently it looks like this:

void clustergen(<arguments essential to computation>,
                <arguments for IO>,
                <argument essential for computation>);

It makes sense to put similar arguments together like so:

void clustergen(unsigned int k, std::vector<std::vector<double>> &c, bool norm,
        std::ostream& file_out, std::ostream& file_rpt, bool csv);

Also, as you do not ever change c, you should take it by const&:

void clustergen(unsigned int k, const std::vector<std::vector<double>> &c, bool norm,
        std::ostream& file_out, std::ostream& file_rpt, bool csv);

Finally, your function arguments aren't very self-explanatory. What is k? What is c? The names should describe what they are (e.g. centroids instead of c).


for (auto c_iter = c.begin(); k > 0; --k) {
    if (c_iter == c.end()) { c_iter = c.begin(); }       // Continuously loop through cluster vec until k = 0
    if (ct_iter == ct.end()) { ct_iter = ct.begin(); }   // Continuously loop through counting vec until k = 0

These lines indicate that something is a bit off with your loop and with the scope of your variables. It's abnormal to have the initialization part of a for loop be unrelated to the other 2 parts. What you really want is for this to look like so:

while (k > 0) { // can be for (; k > 0; --k) {
    auto c_iter = c.begin();
    auto ct_iter = ct.begin(); // note that "ct" isn't a good name either

    ...
    --k; // This wouldn't be here if you used the for (;...) variant, which may be less error-prone
}

for (auto d_iter = c_iter->begin(); d_iter != c_iter->end(); ++d_iter) {

You are using C++11. Use a range-based for loop:

for (auto d_value : *c_iter) {

This does mean that your temp_d_iter will have to change, but I find it much more readable to just keep an index/iterator separate from the for loop. Alternatively, I would loop by index. Iterator loops are just hard to read.

On that note, though, you should write this:

std::vector<double>::iterator temp_d_iter = d_iter;

as

auto temp_d_iter = d_iter;

// Reporting to file follows

This comment shows that you should split your function in to a couple functions. The "reporting to file" should be another function.


One thing to note is that you rarely want to use std::endl. stream << std::endl is equivalent to stream << '\n' << std::flush. You almost never need to flush the stream. In your case, every use of std::endl can be replaced with outputting a newline.


The entire inner loop basically does this:

  1. Generate data
  2. Write comma separated data to file on one line, leaving out the last comma

The first part is basically std::generate:

std::vector<double> data(c_iter->size());
if (norm) {
    std::normal_distribution<double> distr(*d_iter, PT_SD);
    std::generate(data.begin(), data.end(), distr);
} else {
    std::uniform_real_distribution<double> distr(*d_iter - PT_BOUND, *d_iter + PT_BOUND);
    std::generate(data.begin(), data.end(), distr);
}

Once you have this, you can also extract it into a function (e.g. generate_line(...)).

The second part is an algorithm known as "join". While there isn't one in the standard library, it's not too hard to write your own or find one online:

fout << some_library::join(data.begin(), data.end(), ",") << '\n';
\$\endgroup\$
  • 2
    \$\begingroup\$ Good review! For the last point about join, there is one in the experimental namespace that may or may not be implemented on your particular compiler: See std::experimental::ostream_joiner. \$\endgroup\$ – Edward Aug 12 '17 at 2:24
  • \$\begingroup\$ Thank you Justin! This is awesome - I'm going to implement some of this over the next few days and repost. \$\endgroup\$ – Miller Aug 13 '17 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.