Социальная сеть найти друга


Ниже приведен код, который находит в социальной сети друга (т. е. друзья друзей и так далее). Определение друзьями, ФФ как W1 друг W2, то есть должно быть расстояние Левенштейна равно 1. Он работает нормально, с меньшим словарем, но занимает много времени с большим словарем.

Нужна проверка кода и консультации.

#include <stdio.h>
#include <string>
#include <vector>
#include <queue>
#include <fstream>  
#include <iostream>  
#include <sstream>
#include <iterator>
#include <algorithm>
#include <set>

class BkTree {
    public:
        BkTree();
        ~BkTree();
        void insert(std::string m_item);
        void get_friends(std::string center, std::deque<std::string>& friends);
    private:
        size_t EditDistance( const std::string &s, const std::string &t );
        struct Node {
            std::string m_item;
            size_t m_distToParent;
            Node *m_firstChild;
            Node *m_nextSibling;
            Node(std::string x, size_t dist);        
            bool visited;
            ~Node();
        };
        Node *m_root;
        int   m_size;
    protected:
};

BkTree::BkTree() {
    m_root = NULL; 
    m_size = 0;
}

BkTree::~BkTree() { 
    if( m_root ) 
        delete m_root; 
}

BkTree::Node::Node(std::string x, size_t dist) {
    m_item         = x;
    m_distToParent = dist;
    m_firstChild   = m_nextSibling = NULL;
    visited        = false;
}

BkTree::Node::~Node() {
    if( m_firstChild ) 
        delete m_firstChild;
    if( m_nextSibling ) 
        delete m_nextSibling;
}

void BkTree::insert(std::string m_item) {
    if( !m_root ){
        m_size = 1;
        m_root = new Node(m_item, -1);
        return;
    }
    Node *t = m_root;
    while( true ) {
        size_t d = EditDistance( t->m_item, m_item );
        if( !d ) 
            return;
        Node *ch = t->m_firstChild;
        while( ch ) {
            if( ch->m_distToParent == d ) { 
                t = ch; 
                break; 
            }
            ch = ch->m_nextSibling;
        }
        if( !ch ) {
            Node *newChild = new Node(m_item, d);
            newChild->m_nextSibling = t->m_firstChild;
            t->m_firstChild = newChild;
            m_size++;
            break;
        }
    }
}

size_t BkTree::EditDistance( const std::string &left, const std::string &right ) {
    size_t asize = left.size();
    size_t bsize = right.size();
    std::vector<size_t> prevrow(bsize+1);
    std::vector<size_t> thisrow(bsize+1);

    for(size_t i = 0; i <= bsize; i++)
        prevrow[i] = i;

    for(size_t i = 1; i <= asize; i ++) {
        thisrow[0] = i;
        for(size_t j = 1; j <= bsize; j++) {
            thisrow[j] = std::min(prevrow[j-1] + size_t(left[i-1] != right[j-1]), 
                    1 + std::min(prevrow[j],thisrow[j-1]) );
        }
        std::swap(thisrow,prevrow);
    }
    return prevrow[bsize];
}

void BkTree::get_friends(std::string center, std::deque<std::string>& flv) {
    if( !m_root ) return ;
    std::queue< Node* > q;
    q.push( m_root );

    while( !q.empty() ) {
        Node *t = q.front(); 
        q.pop();
        if ( !t ) continue;
        size_t d = EditDistance( t->m_item, center );
        if( d == 1 ) { 
            if ( t->visited == false ) {
                flv.push_back(t->m_item);
                t->visited = true;
            }
        }
        Node *ch = t->m_firstChild;
        q.push(ch);
        while( ch ) {
            if( ch->m_distToParent >=  1 )
                q.push(ch);
            ch = ch->m_nextSibling;
        }
    }
    return;
}

int main( int argc, char **argv ) {
    BkTree *pDictionary = new BkTree();

    std::ifstream dictFile("word.list");
    std::string line; 
    if (dictFile.is_open()) {
        while (! dictFile.eof() ) {               
            std::getline (dictFile,line);
            if ( line.size()) {
                pDictionary->insert(line);
            }
        }
        dictFile.close();
    }
    std::deque<std::string>  flq;
    pDictionary->get_friends("aa", flq);
    int counter = 0;
    while ( !flq.empty()) {
        counter++;
        std::string nf = flq.front();
        flq.pop_front();
        pDictionary->get_friends(nf, flq);
    } 
    std::cout << counter << std::endl;
    return 0;
}


786
2
задан 16 июня 2011 в 11:06 Источник Поделиться
Комментарии
3 ответа

Моя первая мысль заключается в том, что вам может понадобиться профиль код и увидеть, где больше всего времени тратится.

Моя вторая мысль приходит из изучения кода. Вы делаете большое ХХХ[я] или похожие внутри петли, где я просто инкрементируется. Для меня, что предполагает использование итератора (СТД::вектор::итератор). ХХХ[я] часто может привести к больше вычислений, чем простым приращением итератора.

1
ответ дан 16 июня 2011 в 05:06 Источник Поделиться

Вот несколько советов:

Цикл чтения из файла лучше записать так:

{
std::ifstream dictFile("word.list");
std::string line;
while (std::getline (dictFile,line))
{
if (line.size())
pDictionary->insert(line);
}
}

Далее, большинство методов принимают СТД::строка по значению - что может быть дороже в зависимости от вашего компилятора, вы можете быть лучше передает ссылку вместо того, чтобы (вы, кажется, чтобы смешивать и сочетать).

Далее, в узел конструктора, рекомендуется использовать член intialization списка членов, а не в теле конструктора. Почему это актуально, в вашем подходе, член построена и позже назначенного.

Это может сделать разницу, теперь, когда это сделано, как @jwernerny говорит, и он может показать, где ваши истинные горячие точки. Для профилировщика, если это Windows и Visual Studio, можно профилировщик Интел (я предполагаю, что это домашнее задание, поэтому вы, вероятно, можете использовать ознакомительную версию) - это очень хорошо на выявление горячих точек.

1
ответ дан 17 июня 2011 в 10:06 Источник Поделиться

Это может быть потому, что вы используете очередь для хранения ваших узлов в Q в get_friends. Вы делаете поиск в ширину, то есть много вставок и удалений. Обратите внимание, что по ширине можно использовать последн-в-первом-вне очереди, в которой вы можете очень эффективно моделировать, используя предварительно выделенный вектор.

0
ответ дан 16 августа 2011 в 12:08 Источник Поделиться