typestar

hash_index.c en C

Un índice de palabras sobre una tabla hash encadenada, con conteos y cierre limpio.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BUCKETS 32

typedef struct Entry {
    char *word;
    int count;
    struct Entry *next;
} Entry;

typedef struct {
    Entry *buckets[BUCKETS];
    size_t unique;
} Index;

static size_t hash(const char *key) {
    size_t h = 5381;
    for (const char *p = key; *p != '\0'; p++) {
        h = h * 33u + (unsigned char) *p;
    }
    return h % BUCKETS;
}

static int index_add(Index *ix, const char *word) {
    size_t slot = hash(word);
    for (Entry *e = ix->buckets[slot]; e != NULL; e = e->next) {
        if (strcmp(e->word, word) == 0) {
            e->count++;
            return 1;
        }
    }

    Entry *entry = malloc(sizeof *entry);
    if (entry == NULL) {
        return 0;
    }
    size_t n = strlen(word) + 1;
    entry->word = malloc(n);
    if (entry->word == NULL) {
        free(entry);
        return 0;
    }
    memcpy(entry->word, word, n);
    entry->count = 1;
    entry->next = ix->buckets[slot];
    ix->buckets[slot] = entry;
    ix->unique++;
    return 1;
}

static void index_free(Index *ix) {
    for (size_t i = 0; i < BUCKETS; i++) {
        Entry *e = ix->buckets[i];
        while (e != NULL) {
            Entry *next = e->next;
            free(e->word);
            free(e);
            e = next;
        }
        ix->buckets[i] = NULL;
    }
    ix->unique = 0;
}

int main(void) {
    Index ix;
    memset(&ix, 0, sizeof ix);

    char text[] = "the quick brown fox the lazy dog the end";
    for (char *word = strtok(text, " "); word; word = strtok(NULL, " ")) {
        if (!index_add(&ix, word)) {
            fprintf(stderr, "out of memory\n");
            index_free(&ix);
            return 1;
        }
    }

    printf("%zu unique words\n", ix.unique);
    for (size_t i = 0; i < BUCKETS; i++) {
        for (Entry *e = ix.buckets[i]; e != NULL; e = e->next) {
            if (e->count > 1) {
                printf("%-8s %d\n", e->word, e->count);
            }
        }
    }

    index_free(&ix);
    return 0;
}

Cómo funciona

  1. La tabla es dueña de sus claves, así que cada entrada se libera al final.
  2. Las cadenas mantienen juntas las colisiones en un mismo bucket.
  3. El reporte recorre cada bucket para hallar las palabras más frecuentes.

Palabras clave y builtins usados aquí

El intento, en números

Líneas
91
Caracteres a escribir
1632
Tokens
571
Ritmo de tres estrellas
105 tpm

Al ritmo de tres estrellas de 105 tokens por minuto, este intento toma unos 326 segundos.

Escribe este fragmento

Paso 2 de 2 en Bis; paso 20 de 20 en Estructuras de datos y algoritmos.

← Anterior