Оценка улучшений в программе на языке C с использованием хеш-таблиц: взгляд новичка

Я новичок в программировании на C и пытаюсь понять различия между двумя программами, которые проверяют наличие повторяющихся элементов в массиве, используя хэш-таблицы с библиотекой uthash. Я заметил некоторые различия в их реализации и не уверен, что изменения в Программе 1 действительно являются улучшениями по сравнению с Программой 2. Не могли бы вы помочь мне понять эти различия и их последствия?

Программа 1

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "uthash.h"

typedef struct {
    int key;
    UT_hash_handle hh;
} hash_table;

bool containsDuplicate(int* nums, int numsSize) {
    if (numsSize == 1) {
        return false;
    }

    hash_table *hash = NULL;
    hash_table *elem = NULL;
    bool flag = false;

    for (int i = 0; i < numsSize; i++) {
        HASH_FIND_INT(hash, &nums[i], elem);

        if (!elem) {
            elem = (hash_table *)malloc(sizeof(hash_table));
            elem->key = nums[i];
            HASH_ADD_INT(hash, key, elem);
        } else {
            flag = true;
            break;
        }
    }

    hash_table *tmp;
    HASH_ITER(hh, hash, elem, tmp) {
        HASH_DEL(hash, elem);
        free(elem);
    }

    return flag;
}

Программа2

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "uthash.h"

typedef struct {
    int key;
    UT_hash_handle hh;
} hash_table;

hash_table *hash = NULL, *elem, *tmp;

bool containsDuplicate(int* nums, int numsSize){
    if (numsSize == 1) {
        return false;
    }

    bool flag = false;

    for (int i=0; i<numsSize; i++) {
        HASH_FIND_INT(hash, &nums[i], elem);

        if (!elem) {
            elem = malloc(sizeof(hash_table));
            elem->key = nums[i];
            HASH_ADD_INT(hash, key, elem);
        } else {
            flag = true;
            break;
        }
    }

    HASH_ITER(hh, hash, elem, tmp) {
        HASH_DEL(hash, elem); free(elem);
    }

    return flag;
}

С точки зрения новичка, основные различия, которые я вижу, заключаются в следующем:

  • Программа 1 объявляет хеш-таблицу локально в функции containsDuulate, а программа 2 объявляет ее глобально.
  • Программа 1 явно освобождает хеш-таблицу в конце функции, что также делается в программе 2, но с глобальной хеш-таблицей.

Я пытаюсь понять:

  • Действительно ли изменения в Программе 1 являются улучшениями по сравнению с Программой 2?
  • Каковы последствия использования локальной и глобальной хеш-таблицы с точки зрения управления памятью и поведения функций?
  • Существуют ли потенциальные проблемы с использованием глобальной хэш-таблицы для нескольких вызовов функций?
  • Какой подход обычно считается лучшим для такого новичка, как я, и почему?

Вопрос не обязательно ограничивается хеш-таблицами. Вы можете спросить его о любом другом типе/структуре данных, и ответ всегда будет одинаковым. Избегайте глобальных данных.

n. m. could be an AI 16.07.2024 06:06
Стоит ли изучать PHP в 2026-2027 годах?
Стоит ли изучать PHP в 2026-2027 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
1
78
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

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

Если у вас есть другие варианты использования хеш-таблицы, то имеет смысл сохранить ее, а не делать деталью реализации containsDuplicate(). Построение хеш-таблицы стоило O(n), но только O(1) чтобы проверить, присутствует ли уже новое значение. Ни одна программа в настоящее время не поддерживает это.

Не используйте void * из malloc(). Это может скрыть проблемы с типом.

Предпочитайте sizeof *elem вместо sizeof(hash_table). Первый является чисто механическим и приводит к меньшему дублированию.

Если это ответило на ваш вопрос, примите его, нажав на галочку рядом с ним.

Allan Wind 17.07.2024 00:20

Другие вопросы по теме