Читать CSV и использовать двунаправленный поиск в ширину, чтобы найти кратчайший связей между субъектами


У меня есть очень огромный файл file1 с 17 миллионов записей в нем.

Вот пример файла:

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;
   }

}

Эта программа парсит CSV и использует двунаправленный поиск в ширину, чтобы найти кратчайший степень связи между субъектами. На данный момент он анализирует 17 миллионов записан и заканчивается двумя поиски графа в 5 секунд. Я пытаюсь оптимизировать файл для чтения с помощью карты памяти, чтобы прочитать файл. Любые входные данные для оптимизации этого кода можно только приветствовать.

Я не хочу использовать обычный способ чтения файла из-за большого размера файла. Пожалуйста, предложите способ реализации этого, так что весь файл читает и готовит карту за 17 миллионов записей должно происходить менее чем за 2-3 секунды.Я понимаю, что ожидание-это слишком много, но я уверен, что это возможно. Я реально смотрю на самый эффективный способ сделать это.


1 файл можно скачать по ссылке



Комментарии
1 ответ

Похоже, вы нашли хороший подход уже есть.

Несколько общих вещей выделяются:


  • Использование Globals

  • Магические константы и небезопасных стиле C массивы/необработанные указатели:

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

    Я хотел бы предложить, используя std::vector опять же, потому что они могут отслеживать их собственный размер, а не при помощи той же магии константы на всем протяжении вашего кода.


    Кстати, похоже, что вы должны были использовать highest_actor и highest_movie там

  • Смешивание знаковых и беззнаковых целых чисел в сравнения. В частности, во всех циклах использования size_t (Примечание ваш компилятор действительно должны предупредить вас о них. Вы не используете -Wall -Wextra -pedantic?)

  • Много повторяющихся идентификаторов типа. Им не хватает выразительности, и сделать это трудно, чтобы увидеть, где ошибки (например, используя uint64_t против int64_t действительно по назначению)

  • Большое дублирование логики


    • что касается "гибридного" БФС состояние в разных фильмах и актерах,

    • а также вперед и назад государство поиск


  • Петли внутри BFS_OneLevel выглядит очень подозрительно: это почти всегда ошибка для прохода контейнера под модификации (в данном случае детали извлекаются, а также толкнул в теле цикла). Только когда я полностью понял код, я смог потренироваться, что код был на самом деле хорошо, но только потому, что i фактически не используется и Q_size отражает количество элементов выскочил (с фронта), а новинки всегда толкают в конце.

  • Используйте стандартную библиотеку! Этот кусок кода

    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;
    }

    действительно призывает к стандартной библиотеке используется алгоритм:

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

  • Много код делает предположения о достоверности показателей. В рабочем коде я обычно предлагаю заменить все container[idx] экземпляры с границами-проверка вариантов container.at(idx). Конечно, хорошее тестирование/обзор может устранить потребность, и поскольку цель заключается в оптимизации производительности, я хотел бы предложить, чтобы только сохранить .at() стиль внутри разбора - потому что лучше не раньше, чем продолжать неопределенное поведение в случае жестко мощностей не хватает.

Во время чистки код (удалить глобальные переменные, дублирования, неиспользуемый код, плохой нейминг) и запустив несколько тестов с помощью прилагаемого входного файла, я нашел:


  1. Ошибка в строке 97 (в && должно быть ||); код может никогда не завершить, для некоторых входов

  2. В birectional поиск не на практике улучшить скорость (примечание; в худшем случае поведение будет быть улучшено, но за счет сложности)

  3. boost::small_vector дает существенное ускорение (в среднем, есть <=10 связей каждой вершины)

  4. Уничтожение карты занимает значительное время.

    Это один из тех редких случаев, когда я предлагаю целенаправленно утечка памяти, так как вы знаете, программа будет прерывание в любом случае.


Экспозиция Подчистил Код

Принимая вышеуказанные предложения к сердцу, я бы начал резать ненужные заголовки:

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

Представляем некоторые полезные, выразительный, определения типов:

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


Позже, его можно будет легко заменить любой из них, как напр.

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

Группирование данных с логикой, например:

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);
};


Обратите внимание, что я добавил BFS в дополнение к BidiBFS потому что я считаю, это стоит учитывать возросшую сложность двунаправленного алгоритма и эффективной производительностью

В БФС государства

Я определил это как "группировка" из того, что ты в начале b_* и f_* ароматизаторы.

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;
}
};

Ядро алгоритм может выглядеть намного проще:

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;
}

Обратите внимание, что это все еще в основном тот же самый алгоритм (по модулю ошибка у вас в while условие), но теперь стало намного понятнее, что происходит, и почему.

Обратите внимание, что я перенес логику для проверки ранее посещаемых субъектами внутри Enqueue чтобы избежать дублирования, что логику: при рассмотрении вашего кода мне пришлось хорошенько подумать, является ли этот блок кода был на самом деле надо/правильно:

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 в основном ваш BFS_OneLevel способ, но


  • в нем рассматриваются сомнительный цикл по мутирующий очереди

  • она возвращает true или false, чтобы указать, является ли очереди все узлы были обработаны, так что вы можете просто написать

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

    не "зная" об особенностях осуществления очереди.


Вот это:

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;
}

Как вы можете видеть, мы сделали умысел цикла ясно: поменять местами содержимое очереди с пустой. Мы тогда цикл по всем ранее очереди узлы (в local_queue). В конце шага может быть новых элементов в очереди, но ни один из первоначально очереди узлы будут.

Если не было никаких пунктов, чтобы начать с, мы возвращаемся false.

BF_Visit

Что здесь произошло? Я извлек логика, которая была в BFS_OneLevel петли. Я признаю, я сделал это только после реализации не-двунаправленный вариант поиска БФ. В BF_Visit похоже, что ваш оригинальный код:

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;
}

Тонкие различия:


  • опционально он прекращается досрочно, когда goalnode достигается (это полезно в одном направлении БФС)

  • Он использует потенциально отдельная queus для толкания и переборе. Это означает, что при BF_Step называет это, он может посетить local_queue узлы, но когда BFS называет это, он может просто продолжать, пока больше узлов толкают (и очереди сливают).

BFS - бонус

Для полноты картины, вот как однонаправленный БФС выглядит основана на тех же строительных блоков (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;
}

Это очень элегантный!

Data::Parse - стиль только

Это в основном коде, но


  • используя лямбда, чтобы уменьшить дублирование кода и повысить удобочитаемость

  • используя .at(i) вместо бесконтрольно [i] индексация

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 - стиль только

Немного изменилась


  • Я заметил, что при выходе из программы могут занимать до 0,8 секунд, поэтому я сделал Data экземпляр слил специально

  • Теперь вы можете легко выбрать между BidiBFS и 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(); });
}

В timed объект очень простой общего назначения оболочки:

#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();
}


Обратите внимание, он делает то, что вы ожидаете, что он делает, но это немного выходит за рамки данного обзора. Обратите внимание, что он весит еще 14 строк кода, так что по сути мой подчистили код значительно короче, чем код в вопрос, даже если он имеет больше возможностей и стал более удобным для чтения.

ОЦЕНКА ПРОИЗВОДИТЕЛЬНОСТИ #1

На данный момент код выглядит так:

Жить На 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(); });
}

Тайминги на ваш тест сейчас:

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

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


Оригинальные тайминги на моей системе были почти идентичные вашим (5,9 с). Это 25% прирост производительности. Не плохо

Оптимизация

Применяются два способа оптимизации:

Используя small_vector по смежности контейнеров

Потому что многие актеры играли в < 10 фильмов, возможно, имеет смысл, чтобы сократить расходы, есть выделения памяти. small_vector хороший кандидат, поскольку он ухудшает изящно, выделяя поведение при необходимости.

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

Используя Отображаемые В Память Файлы И Дух

Принимая подход из моего ответа на [так]: https://stackoverflow.com/questions/48525833/how-to-parse-csv-in-c-using-boost-memory-maps/48533015#48533015 я изменил реализации Data::Parse в эквиваленте:

#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");
}
}


Обратите внимание , что qi::phrase_parse с qi::blank как шкипер делает это так, что пробел игнорируется (как ваш istream кодекса).

ОЦЕНКА ЭФФЕКТИВНОСТИ #2

Это действительно сокращает в дальнейшем время выполнения:

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

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

Это чистое улучшение 70% в целом. Не плохо :) окончательный код выглядит так:

Жить На 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");
}
}

14
ответ дан 1 февраля 2018 в 05:02 Источник Поделиться