Как бы я сделал этот алгоритм менее избыточным? - PullRequest
Новая
       56

Как бы я сделал этот алгоритм менее избыточным?

1 голос
/ 27 апреля 2020

Я довольно новичок в C и не могу понять, как сделать функцию number_within_k_degrees() менее избыточной. Он посещает одни и те же узлы графа снова и снова, даже если они уже были посещены. Я подумал удалить начальную настройку всех значений на false, чтобы немного ее уменьшить, однако я не думаю, что это много значит. Любые советы о том, как уменьшить или устранить лишнюю работу, будут очень полезны. Спасибо 

void find_reachable_recursive(struct person *current, int steps_remaining,
                              bool *reachable){
    // mark current root person as reachable
    reachable[person_get_index(current)] = true;
    // now deal with this person's acquaintances
    if (steps_remaining > 0){
        int num_known = person_get_num_known(current);
        for (int i = 0; i < num_known; i++){
            struct person *acquaintance = person_get_acquaintance(current, i);
            find_reachable_recursive(acquaintance, steps_remaining - 1, reachable);
        }
    }
}

// computes the number of people within k degrees of the start person
int number_within_k_degrees(struct person *start, int total_people, int k){
    bool *reachable;
    int count;

    // maintain a boolean flag for each person indicating if they are visited
    reachable = malloc(sizeof(bool) * total_people);
    for (int i = 0; i < total_people; i++){
        reachable[i] = false;
    }

    // now search for all people who are reachable with k steps
    find_reachable_recursive(start, k, reachable);

    // all visited people are marked reachable, so count them
    count = 0;
    for (int i = 0; i < total_people; i++){
        if (reachable[i] == true){
            count++;
        }
    }
    return count;
}

1 Ответ

1 голос
/ 27 апреля 2020

Я решил удалить начальную настройку всех значений на false, чтобы немного ее уменьшить

Это, очевидно, очень плохая идея: для нужно , чтобы Инициализирован (false) для правильности.

Реальная проблема заключается в том, что вы никогда не проверяете , был ли узел еще посещен. Поскольку уже просмотренная заметка не нуждается в повторной обработке, ее можно немедленно прервать: 

void find_reachable_recursive(struct person *current, int steps_remaining,
                              bool *reachable){
    const int pindex = person_get_index(current);
    if (reachable[pindex]) return;
    // mark current root person as reachable
    reachable[pindex] = true;
    … rest of the code

Некоторые дополнительные предложения по улучшению:

  1. Не объявлять переменные в начало ваших функций, объявите их там, где вы их инициализируете. Это улучшает удобочитаемость, объединяя объявление и использование переменных.
  2. Вместо вызова malloc с последующим установкой значений на false в aal oop, используйте calloc.
  3. Не используйте логические литералы в тестах. Код, такой как if (reachable[i] == true), является избыточным и должен быть записан как if (reachable[i]).
...