6
\$\begingroup\$

I have a really huge file¹ with 17 million records in it.

Here is a sample of the file:

Actor Movie
1,2
2,2
3,1
4,3
2,3
#include <chrono>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
#include<list>
#include<queue>
#include<fstream>
#include<sstream>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include<cstring>
#include <future>
#include <iostream>


using namespace std;
std::string lPath;
static uint64_t highest_actor = 2000000; 
static uint64_t highest_movie = 1200000;
static int64_t fin_count = 0;
std::vector<std::future<int64_t>> futures;



static vector<uint64_t> *movie_map = new vector<uint64_t>[1200000];
static vector<uint64_t> *actor_movie_map = new vector<uint64_t>[2000000];

void BFS_OneLevel(std::queue<uint64_t> &Q,std::vector<bool> &visited_act,std::vector<bool> &visited_mov,std::vector<uint64_t> &dist)
{
    auto Q_size = Q.size();
    for (int i =0; i< Q_size; ++i)
    {
        uint64_t top = Q.front();
        Q.pop();
        std::vector<uint64_t>& moviesOfTop = actor_movie_map[top]; //vector of movies the actor 'top' has been in
        auto currentDist = dist[top];
        //cout<<"Top is: "<<top<<endl;
        for (auto& movie : moviesOfTop) // replace all moviesOfTop[i] below with movie
        {
            //cout << moviesOfTop[i] << "Movies of top"  << endl;
            if(!visited_mov[movie])
            {
                //cout<<"Movies: "<<movie<<endl;
                visited_mov[movie] = true;
                std::vector<uint64_t>& actorsInMovie = movie_map[movie];
                for (auto& actor : actorsInMovie) //iterating over actors in movie[i]
                {
                    if(!visited_act[actor])
                    {
                        //cout<<"Actors: "<<actor<<endl;
                        Q.push(actor);
                        dist[actor] = currentDist + 1;
//                        prev_node[actor]=top;
                        visited_act[actor] = true;
                    }
                }
            }
        }
    }

}

int64_t BFS(uint64_t start, uint64_t goalnode)
{
    if (start == goalnode)
        return 0;

    //cout << "Alive" << endl;
    std::vector<bool> f_visited_mov(highest_movie, false);
    std::vector<bool> f_visited_act(highest_actor, false);
    std::vector<bool> b_visited_mov(highest_movie, false);
    std::vector<bool> b_visited_act(highest_actor, false);
//    std::vector<int64_t> b_prev_node(highest_actor, -1);
//    std::vector<int64_t> f_prev_node(highest_actor, -1);
    std::queue<uint64_t> f_Q;
    std::queue<uint64_t> b_Q;
    f_Q.push(start); //push starting actor in queue
    b_Q.push(goalnode); //push starting actor in queue

    //cout << "Alive" << endl;
    f_visited_act[start] = true;
    b_visited_act[goalnode] = true;
//    f_prev_node[start]=start;
//    b_prev_node[goalnode]=goalnode;
    ////cout << "Alive" << endl;
    //uint64_t* prev_node = new uint64_t[highest_actor];
    std::vector<uint64_t> f_dist(highest_actor, 0);
    std::vector<uint64_t> b_dist(highest_actor, 0);
    //vector<uint64_t> prev_node[num_act];
    //cout << "Alive" << endl; 
    //memset(prev_node,-1,highest_actor); // setting all values to -1
    //cout << "Alive after memset" << endl;
    // uint64_t flag = 0;
    // dist[start] = 0;
    while(!f_Q.empty() && !b_Q.empty())
    {
        BFS_OneLevel(f_Q,f_visited_act,f_visited_mov,f_dist);
        BFS_OneLevel(b_Q,b_visited_act,b_visited_mov,b_dist);
//        BFS_OneLevel(f_Q,f_visited_act,f_visited_mov,f_dist,f_prev_node);
//        BFS_OneLevel(b_Q,b_visited_act,b_visited_mov,b_dist,b_prev_node);
       // cout<<"BFS One done"<<endl;

        std::vector<int64_t> common_node;
        //int count=0;
        for (int64_t i =0; i<highest_actor;++i)
        {
            if (b_visited_act[i] && f_visited_act[i])
            {
                common_node.push_back(f_dist[i]+b_dist[i]);
                //cout<<"Common_Node found: "<<i<<" --- "<<f_dist[i]+b_dist[i]<<endl;
            }
        }
        if(!common_node.empty())
        {
            int64_t min=common_node[0];
            for (long long i : common_node) {
                if(i < min)
                    min= i;
            }
            /*int64_t nodecheck1=min; int64_t nodecheck2=min;
            int flag=1;
            while(flag!=0)
            {
                cout<<"Path starting from mid: "<<nodecheck1<<"  "<<nodecheck2<<endl;
                nodecheck1=f_prev_node[nodecheck1];
                nodecheck2=b_prev_node[nodecheck2];
                if(nodecheck1==start && nodecheck2 ==goalnode)
                    break;
            }*/
            return min;
        }
    }

    return -1;
}


int main()
{

    cout << "prog start " << endl ;
    std::string lPath = "playedin.csv"; 

    std::ifstream file(lPath);

    string dummyline;
    std::getline(file,dummyline);
        int64_t fir,sec;
    while(file >> fir 
    && file.ignore(std::numeric_limits<std::streamsize>::max(), ',')
    && file >> sec){
       movie_map[sec].push_back(fir);
        actor_movie_map[fir].push_back(sec);

    }
    cout << "movie map ready " << endl ;


    futures.push_back(async(launch::async,BFS,3,4));
    futures.push_back(async(launch::async,BFS,4,5));



    cout<<"Ans: "<< endl;
    for(auto &e : futures) {
     std::cout <<"Ans: "<< e.get() << std::endl;
   }

}

This program parses CSV and uses bidirectional BFS to find the shortest degree of connection between the actors. At the moment it parses 17 million recorded and finishes two graph searches in about 5 seconds. I am trying to optimize the file reading further by using memory maps to read the file. Any inputs to optimize this code is welcome.

I do not want to use the normal way of reading file because of the large size of the file. Please suggest a way of implementing this so that the whole file reading and preparing map for 17 million records should happen in less than 2-3 seconds.I understand that the expectation is little too much, but I am sure it is possible. I am really looking at the most efficient way of doing this.


¹ The file can be downloaded at link

\$\endgroup\$
  • \$\begingroup\$ You forgot to add the input file \$\endgroup\$ – sehe Feb 1 '18 at 16:59
  • 3
    \$\begingroup\$ 17 Million. Huge? I would say middling to big. \$\endgroup\$ – Martin York Feb 1 '18 at 18:14
14
\$\begingroup\$

It looks like you found a pretty nice approach there already.

A few general things stand out:

  • Using globals
  • Magical constants and unsafe C-style arrays/raw pointers:

    static vector<uint64_t> *movie_map = new vector<uint64_t>[1200000];
    static vector<uint64_t> *actor_movie_map = new vector<uint64_t>[2000000];
    

    I'd suggest using std::vector again, because they can keep track of their own size, instead of using the same magic constants all over your code.

    By the way, it looks like you should have used highest_actor and highest_movie there anyways

  • Mixing signed and unsigned integers in comparisons. In particular, in all the loops, use size_t (note your compiler should really warn you about these. Are you not using -Wall -Wextra -pedantic?)

  • A lot of duplicated type identifiers. They lack expressiveness, and make it hard to see where bugs are (e.g. whether using uint64_t vs int64_t was really on purpose)
  • A lot of duplicated logic
    • regarding the "hybrid" BFS state across movies and actors,
    • as well as the backwards and forwards search state
  • The loop inside BFS_OneLevel looks very suspicious: it's almost always an error to iterate a container under modification (in this case, items are being popped as well as pushed in the loop body). Only when I fully understood the code, I was able to work-out that the code was actually ok, but only because i isn't actually used and Q_size reflects the number of items popped (from the front) while new items are always pushed at the end.
  • Use the standard library! This piece of code

    if(!common_node.empty())
    {
        int64_t min=common_node[0];
        for (long long i : common_node) {
            if(i < min)
                min= i;
        }
        /*int64_t nodecheck1=min; int64_t nodecheck2=min;
        int flag=1;
        while(flag!=0)
        {
            cout<<"Path starting from mid: "<<nodecheck1<<"  "<<nodecheck2<<endl;
            nodecheck1=f_prev_node[nodecheck1];
            nodecheck2=b_prev_node[nodecheck2];
            if(nodecheck1==start && nodecheck2 ==goalnode)
                break;
        }*/
        return min;
    }
    

    really calls for standard library algorithm use:

    if (!common_node.empty()) {
        return *std::min_element(common_node.begin(), common_node.end());
    }
    
  • A lot of the code makes assumptions about the validity of indices. In production code I would usually suggest replacing all of the container[idx] instances with the bounds-checking variants container.at(idx). Of course, good testing/review could remove the need, and since the objective here is to optimize the performance, I'd suggest to only keep the .at() style inside the parsing - because it's better to fail early than to continue with Undefined Behaviour in case the hard-coded capacities don't suffice.

While cleaning up the code (remove globals, duplication, unused code, bad naming) and running some benchmarks using the supplied input file, I found:

  1. A bug in your line 97 (the && should be ||); your code might never complete, for some inputs
  2. The birectional search does not in practice improve the speed (note; worst-case behaviour will be improved, but at the cost of complexity)
  3. boost::small_vector yields significant speed up (on average, there are <=10 relations per vertex)
  4. Destructing the maps takes significant time.

    This is one of those rare occasions where I'd suggest purposefully leaking the memory since you know the program will be terminating anyways.

Exposition Of Cleaned Up Code

Taking the above suggestions to heart, I'd start by cutting unneeded headers:

#include <algorithm>
#include <fstream>
#include <future>
#include <iostream>
#include <queue>
#include <string>
#include <vector>

Introducing some useful, expressive, typedefs:

using Id        = uint64_t;
using Distance  = int64_t;
using Ids       = std::vector<Id>;
using Adjacency = std::vector<Ids>;

Later, it will be easy to replace any of these like e.g.

 using Ids = boost::container::small_vector<Id, 10>;

Grouping your data with the logic, e.g.:

class Data {
  private:
    Adjacency movie_map { 1200000 },
              actor_map { 2000000 };

    using ColorMap = std::vector<bool>;
    using Queue = std::deque<Id>;

    struct BFS_State;

  public:
    explicit Data(std::string const& fname) { Parse(fname); }

    Distance BFS(Id start, Id goalnode) const;
    Distance BidiBFS(Id start, Id goalnode) const;

  private:
    bool BF_Step(BFS_State& state) const;
    bool BF_Visit(Queue& nodes, BFS_State& state, Id goalnode = -1) const;
    void Parse(std::string const& fname);
};

Note that I added BFS in addition to BidiBFS because I think it's worth considering the increased complexity of the bidirectional algorithm vs. the effective performance gain

The BFS State

I've defined this as simply the "grouping" of things you have prefixed in b_* and f_* flavours.

struct BFS_State {
    BFS_State(size_t actors, size_t movies)
        : visited_act(actors), 
          visited_mov(movies),
          dist(actors, 0)
    { }

    Queue queue;
    ColorMap visited_act, visited_mov;
    std::vector<Distance> dist;

    bool Enqueue(Id actor, Distance distance = 0) {
        if (visited_act[actor]) 
            return false;
        visited_act[actor] = true;

        queue.push_back(actor);
        dist[actor] = distance;
        return true;
    }
};

The algorithm kernel can now look much simpler:

Distance BidiBFS(Id start, Id goalnode) const {
    if (start == goalnode)
        return 0;

    BFS_State 
        forward { actor_map.size(), movie_map.size() },
        back { actor_map.size(), movie_map.size() };

    forward.Enqueue(start);
    back.Enqueue(goalnode);

    while (BF_Step(forward) || BF_Step(back)) {

        std::vector<Distance> common_node;
        for (Id i = 0; i < actor_map.size(); ++i) {
            if (back.visited_act[i] && forward.visited_act[i]) {
                common_node.push_back(forward.dist[i] + back.dist[i]);
            }
        }

        if (!common_node.empty()) {
            return *std::min_element(common_node.begin(), common_node.end());
        }
    }

    return -1;
}

Note this is still basically exactly the same algorithm (modulo the bug you had in the while condition), but it is now much clearer what is happening, and why.

Note that I moved the logic to check for previously-visited actors inside Enqueue to avoid duplicating that logic: when reviewing your code I had to think really hard whether this block of code was actually necessary/correct:

std::queue<uint64_t> f_Q;
std::queue<uint64_t> b_Q;
f_Q.push(start); //push starting actor in queue
b_Q.push(goalnode); //push starting actor in queue

//cout << "Alive" << endl;
f_visited_act[start] = true;
b_visited_act[goalnode] = true;

BF_Step

BF_Step is basically your BFS_OneLevel method, but

  • it addresses the iffy loop over a mutating queue
  • it returns true or false to indicate whether all queued nodes have been processed, so you can simply write

    while (BF_Step(fwd) || BF_Step(bck)) {
    

    without "knowing" about the implementation specifics of the queue.

Here it is:

bool BF_Step(BFS_State& state) const {
    if (state.queue.empty())
        return false;

    Queue local_queue;
    std::swap(local_queue, state.queue);

    BF_Visit(local_queue, state);
    return true;
}

As you can see, we made the intent of the loop clear: we swap the contents of the queue with an empty one. We then loop over all previously queued nodes (the local_queue). At the end of the step there might be new queued items, but none of the originally queued nodes will be.

If there weren't any items to begin with, we return false.

BF_Visit

What happened here? I extracted the logic that was in the BFS_OneLevel loop. I will admit I only did this after implementing a non-bidirectional version of the BF search. The BF_Visit looks like your original code:

bool BF_Visit(Queue& nodes, BFS_State& state, Id goalnode = -1) const {
    // note that `nodes` can alias `state.queue` if it's not a bidirectional search
    // returns true if goalnode reached (not used for bidi search)
    while (!nodes.empty()) {
        Id top = nodes.front();
        nodes.pop_front();

        if (top == goalnode)
            return true;

        for (Id movie : actor_map[top]) {
            if (state.visited_mov[movie]) continue;
            state.visited_mov[movie] = true;

            for (Id actor : movie_map[movie]) {
                state.Enqueue(actor, state.dist[top] + 1);
            }
        }
    }

    return false;
}

The subtle differences are:

  • it optionally terminates early when a goalnode is reached (this is useful in the single-direction BFS)
  • It uses potentially seperate queus for pushing vs. iterating. This means that when BF_Step calls it, it can visit the local_queue nodes, but when BFS calls it, it may just continue until no more nodes get pushed (and the queue is drained).

BFS - Bonus

To complete the picture, here's how a uni-directional BFS looks based on the same building blocks (BFS_State, BF_Visit):

Distance BFS(Id start, Id goalnode) const {
    if (start == goalnode)
        return 0;

    BFS_State state { actor_map.size(), movie_map.size() };
    state.Enqueue(start);

    if (BF_Visit(state.queue, state, goalnode))
        return state.dist[goalnode];

    return -1;
}

That's pretty elegant!

Data::Parse - style only

This is basically your code, but

  • using a lamda to reduce duplicated code and increase legibility
  • using .at(i) instead of the unchecked [i] indexing
void Parse(std::string const& fname) {
    std::ifstream file(fname);

    auto skip_to = [&file](char ch) -> std::istream& {
        return file.ignore(std::numeric_limits<std::streamsize>::max(), ch);
    };

    skip_to('\n');
    Id fir, sec;

    while (file >> fir && skip_to(',') && file >> sec) {
        movie_map.at(sec).push_back(fir);
        actor_map.at(fir).push_back(sec);
    }
}

main - style only

Little has changed, though

  • I did notice that exiting the program could take up to 0.8 seconds, so I made Data instance leaked on purpose
  • You can now easily choose between BidiBFS and BFS
int main() {
    std::unique_ptr<Data> data(timed("Movie map created", [] { return new Data("playedin.csv"); }));

    std::vector<std::future<Distance> > queries;
    queries.push_back(std::async(std::launch::async, [&data] { return data->/*Bidi*/BFS(3, 4); }));
    queries.push_back(std::async(std::launch::async, [&data] { return data->/*Bidi*/BFS(4, 5); }));

    for (auto& result : queries) {
        std::cout << "Ans: " << result.get() << std::endl;
    }

    data.release(); // leaked on purpose, takes ~800ms less (~400ms with small_vector)
    if (data) timed("Destruct data", [&data] { data.reset(); });
}

The timed facility is a really simple general purpose wrapper:

#include <chrono>

template <typename F> struct Defer { F f; ~Defer() { f(); } };
template <typename F> Defer<F> defer(F f) { return {f}; }

template <typename F> auto timed(char const* caption, F f) -> decltype(f()) {
    using C = std::chrono::high_resolution_clock;
    static constexpr std::chrono::duration<double, std::chrono::milliseconds::period> ms(1.0);

    auto s = C::now();
    auto finally = defer([=]{ std::cout << caption << ": " << (C::now() - s)/ms << "ms\n"; });

    return f();
}

Note It does what you expect it does, but it's a bit out of scope for this review. Note that it does weigh an additional 14 Lines Of Code, so in effect my cleaned up code is considerably shorter than the question code, even though it has more features and has become more readable.

PERFORMANCE ASSESSMENT #1

At this point, the code looks like this:

Live On Coliru

#include <algorithm>
#include <fstream>
#include <future>
#include <iostream>
#include <deque>
#include <string>
#include <vector>
#include <boost/container/small_vector.hpp>

using Id        = uint64_t;
using Distance  = int64_t;
using Ids       = boost::container::small_vector<Id, 10>; // std::vector<Id>;
using Adjacency = std::vector<Ids>;

class Data {
  private:
    Adjacency movie_map { 1200000 },
              actor_map { 2000000 };

    using ColorMap = std::vector<bool>;
    using Queue = std::deque<Id>;

    struct BFS_State {
        BFS_State(size_t actors, size_t movies)
            : visited_act(actors), 
              visited_mov(movies),
              dist(actors, 0)
        { }

        Queue queue;
        ColorMap visited_act, visited_mov;
        std::vector<Distance> dist;

        bool Enqueue(Id actor, Distance distance = 0) {
            if (visited_act[actor]) 
                return false;
            visited_act[actor] = true;

            queue.push_back(actor);
            dist[actor] = distance;
            return true;
        }
    };

  public:
    explicit Data(std::string const& fname) { Parse(fname); }

    Distance BFS(Id start, Id goalnode) const {
        if (start == goalnode)
            return 0;

        BFS_State state { actor_map.size(), movie_map.size() };
        state.Enqueue(start);

        if (BF_Visit(state.queue, state, goalnode))
            return state.dist[goalnode];

        return -1;
    }

    Distance BidiBFS(Id start, Id goalnode) const {
        if (start == goalnode)
            return 0;

        BFS_State 
            fwd { actor_map.size(), movie_map.size() },
            bck { actor_map.size(), movie_map.size() };

        fwd.Enqueue(start);
        bck.Enqueue(goalnode);

        while (BF_Step(fwd) || BF_Step(bck)) {

            std::vector<Distance> common_node;
            for (Id i = 0; i < actor_map.size(); ++i) {
                if (bck.visited_act[i] && fwd.visited_act[i]) {
                    common_node.push_back(fwd.dist[i] + bck.dist[i]);
                }
            }

            if (!common_node.empty()) {
                return *std::min_element(common_node.begin(), common_node.end());
            }
        }

        return -1;
    }

  private:
    bool BF_Step(BFS_State& state) const {
        if (state.queue.empty())
            return false;

        Queue local_queue;
        std::swap(local_queue, state.queue);

        BF_Visit(local_queue, state);
        return true;
    }

    bool BF_Visit(Queue& nodes, BFS_State& state, Id goalnode = -1) const {
        // note that `nodes` can alias `state.queue` if it's not a bidirectional search
        // returns true if goalnode reached (not used for bidi search)
        while (!nodes.empty()) {
            Id top = nodes.front();
            nodes.pop_front();

            if (top == goalnode)
                return true;

            for (Id movie : actor_map[top]) {
                if (state.visited_mov[movie]) continue;
                state.visited_mov[movie] = true;

                for (Id actor : movie_map[movie]) {
                    state.Enqueue(actor, state.dist[top] + 1);
                }
            }
        }

        return false;
    }

    void Parse(std::string const& fname) {
        std::ifstream file(fname);

        auto skip_to = [&file](char ch) -> std::istream& {
            return file.ignore(std::numeric_limits<std::streamsize>::max(), ch);
        };

        skip_to('\n');
        Id fir, sec;

        while (file >> fir && skip_to(',') && file >> sec) {
            movie_map.at(sec).push_back(fir);
            actor_map.at(fir).push_back(sec);
        }
    }
};

#include <chrono>
#include <memory>

template <typename F> struct Defer { F f; ~Defer() { f(); } };
template <typename F> Defer<F> defer(F f) { return {f}; }

template <typename F> auto timed(char const* caption, F f) -> decltype(f()) {
    using C = std::chrono::high_resolution_clock;
    static constexpr std::chrono::duration<double, std::chrono::milliseconds::period> ms(1.0);

    auto s = C::now();
    auto finally = defer([=]{ std::cout << caption << ": " << (C::now() - s)/ms << "ms\n"; });

    return f();
}

int main() {
    std::unique_ptr<Data> data(timed("Movie map created", [] { return new Data("playedin.csv"); }));

    std::vector<std::future<Distance> > queries;
    queries.push_back(std::async(std::launch::async, [&data] { return data->/*Bidi*/BFS(3, 4); }));
    queries.push_back(std::async(std::launch::async, [&data] { return data->/*Bidi*/BFS(4, 5); }));

    for (auto& result : queries) {
        std::cout << "Ans: " << result.get() << std::endl;
    }

    data.release(); // leaked on purpose, takes ~800ms less (~400ms with small_vector)
    if (data) timed("Destruct data", [&data] { data.reset(); });
}

The timings for your test case are now:

Movie map created: 4087.69ms
Ans: 4
Ans: 3

real    0m4.431s
user    0m4.352s
sys     0m0.184s

The original timings on my system were nearly identical to yours (5.9s). That's a 25% performance increase. Not bad

OPTIMIZING

Two optimizations applied:

Using small_vector for the adjacency containers

Because many actors will have played in < 10 movies, it may make sense to cut down on memory allocation costs there. small_vector is a nice candidate as it gracefully degrades to allocating behaviour if required.

using Ids = boost::container::small_vector<Id, 10>;

Using Memory Mapped Files And Spirit

Taking the approach from my answer over at [SO]: https://stackoverflow.com/questions/48525833/how-to-parse-csv-in-c-using-boost-memory-maps/48533015#48533015 I changed the implementation of Data::Parse into the equivalent:

#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/iostreams/device/mapped_file.hpp>

void Data::Parse(std::string const& fname) {
    boost::iostreams::mapped_file_source mfs(fname);

    struct Handler {
        Data* _this;

        void operator()(uint64_t fir, uint64_t sec) const {
            _this->movie_map.at(sec).push_back(fir);
            _this->actor_map.at(fir).push_back(sec);
        }
    };

    boost::phoenix::function<Handler> handle { Handler{this} };

    using namespace boost::spirit::qi;
    if (!phrase_parse(mfs.begin(), mfs.end(),
        *(char_ - eol) >> eol >> (uint_ >> ',' >> uint_)[handle(_1, _2)] % eol, blank))
    {
        throw std::runtime_error("Parse failed\n");
    }
}

Note that qi::phrase_parse with qi::blank as a skipper makes it so that whitespace is ignored (like your istream code did).

PERFORMANCE ASSESSMENT #2

This indeed slashes the runtime further:

Movie map created: 1456.61ms
Ans: 4
Ans: 3

real    0m1.790s
user    0m1.772s
sys     0m0.116s

That's a net improvement of 70% overall. Not bad :) The final code looks like this:

Live On Coliru

#include <algorithm>
#include <fstream>
#include <future>
#include <iostream>
#include <deque>
#include <string>
#include <vector>
#include <boost/container/small_vector.hpp>

using Id        = uint64_t;
using Distance  = int64_t;
using Ids       = boost::container::small_vector<Id, 10>; // std::vector<Id>;
using Adjacency = std::vector<Ids>;

class Data {
  private:
    Adjacency movie_map { 1200000 },
              actor_map { 2000000 };

    using ColorMap = std::vector<bool>;
    using Queue = std::deque<Id>;

    struct BFS_State {
        BFS_State(size_t actors, size_t movies)
            : visited_act(actors), 
              visited_mov(movies),
              dist(actors, 0)
        { }

        Queue queue;
        ColorMap visited_act, visited_mov;
        std::vector<Distance> dist;

        bool Enqueue(Id actor, Distance distance = 0) {
            if (visited_act[actor]) 
                return false;
            visited_act[actor] = true;

            queue.push_back(actor);
            dist[actor] = distance;
            return true;
        }
    };

  public:
    explicit Data(std::string const& fname) { Parse(fname); }

    Distance BFS(Id start, Id goalnode) const {
        if (start == goalnode)
            return 0;

        BFS_State state { actor_map.size(), movie_map.size() };
        state.Enqueue(start);

        if (BF_Visit(state.queue, state, goalnode))
            return state.dist[goalnode];

        return -1;
    }

    Distance BidiBFS(Id start, Id goalnode) const {
        if (start == goalnode)
            return 0;

        BFS_State 
            fwd { actor_map.size(), movie_map.size() },
            bck { actor_map.size(), movie_map.size() };

        fwd.Enqueue(start);
        bck.Enqueue(goalnode);

        while (BF_Step(fwd) || BF_Step(bck)) {

            std::vector<Distance> common_node;
            for (Id i = 0; i < actor_map.size(); ++i) {
                if (bck.visited_act[i] && fwd.visited_act[i]) {
                    common_node.push_back(fwd.dist[i] + bck.dist[i]);
                }
            }

            if (!common_node.empty()) {
                return *std::min_element(common_node.begin(), common_node.end());
            }
        }

        return -1;
    }

  private:
    bool BF_Step(BFS_State& state) const {
        if (state.queue.empty())
            return false;

        Queue local_queue;
        std::swap(local_queue, state.queue);

        BF_Visit(local_queue, state);
        return true;
    }

    bool BF_Visit(Queue& nodes, BFS_State& state, Id goalnode = -1) const {
        // note that `nodes` can alias `state.queue` if it's not a bidirectional search
        // returns true if goalnode reached (not used for bidi search)
        while (!nodes.empty()) {
            Id top = nodes.front();
            nodes.pop_front();

            if (top == goalnode)
                return true;

            for (Id movie : actor_map[top]) {
                if (state.visited_mov[movie]) continue;
                state.visited_mov[movie] = true;

                for (Id actor : movie_map[movie]) {
                    state.Enqueue(actor, state.dist[top] + 1);
                }
            }
        }

        return false;
    }

    void Parse(std::string const& fname);
};

#include <chrono>
#include <memory>

template <typename F> struct Defer { F f; ~Defer() { f(); } };
template <typename F> Defer<F> defer(F f) { return {f}; }

template <typename F> auto timed(char const* caption, F f) -> decltype(f()) {
    using C = std::chrono::high_resolution_clock;
    static constexpr std::chrono::duration<double, std::chrono::milliseconds::period> ms(1.0);

    auto s = C::now();
    auto finally = defer([=]{ std::cout << caption << ": " << (C::now() - s)/ms << "ms\n"; });

    return f();
}

int main() {
    std::unique_ptr<Data> data(timed("Movie map created", [] { return new Data("playedin.csv"); }));

    std::vector<std::future<Distance> > queries;
    queries.push_back(std::async(std::launch::async, [&data] { return data->/*Bidi*/BFS(3, 4); }));
    queries.push_back(std::async(std::launch::async, [&data] { return data->/*Bidi*/BFS(4, 5); }));

    for (auto& result : queries) {
        std::cout << "Ans: " << result.get() << std::endl;
    }

    data.release(); // leaked on purpose, takes ~800ms less (~400ms with small_vector)
    if (data) timed("Destruct data", [&data] { data.reset(); });
}

#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/iostreams/device/mapped_file.hpp>

void Data::Parse(std::string const& fname) {
    boost::iostreams::mapped_file_source mfs(fname);

    struct Handler {
        Data* _this;

        void operator()(uint64_t fir, uint64_t sec) const {
            _this->movie_map.at(sec).push_back(fir);
            _this->actor_map.at(fir).push_back(sec);
        }
    };

    boost::phoenix::function<Handler> handle { Handler{this} };

    using namespace boost::spirit::qi;
    if (!phrase_parse(mfs.begin(), mfs.end(),
        *(char_ - eol) >> eol >> (uint_ >> ',' >> uint_)[handle(_1, _2)] % eol, blank))
    {
        throw std::runtime_error("Parse failed\n");
    }
}
\$\endgroup\$

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.