Een van de dingen die ik mis bij het schrijven van programma’s in C is een woordenboekgegevensstructuur. Wat is de handigste manier om er een in C te implementeren? Ik ben niet op zoek naar prestaties, maar het gemak om het helemaal opnieuw te coderen. Ik wil ook niet dat het generiek is — zoiets als char*→intis voldoende. Maar ik wil wel dat het een willekeurig aantal items kan opslaan.
Dit is meer bedoeld als oefening. Ik weet dat er bibliotheken van derden beschikbaar zijn die men kan gebruiken. Maar bedenk even dat ze niet bestaan. Wat is in een dergelijke situatie de snelste manier om een woordenboek te implementeren dat aan de bovenstaande vereisten voldoet.
Antwoord 1, autoriteit 100%
Sectie 6.6 van De C-programmeertaalpresenteert een eenvoudig woordenboek (hashtabel) data structuur. Ik denk niet dat een bruikbare woordenboekimplementatie eenvoudiger kan worden dan dit. Voor uw gemak reproduceer ik de code hier.
struct nlist { /* table entry: */
struct nlist *next; /* next entry in chain */
char *name; /* defined name */
char *defn; /* replacement text */
};
#define HASHSIZE 101
static struct nlist *hashtab[HASHSIZE]; /* pointer table */
/* hash: form hash value for string s */
unsigned hash(char *s)
{
unsigned hashval;
for (hashval = 0; *s != '\0'; s++)
hashval = *s + 31 * hashval;
return hashval % HASHSIZE;
}
/* lookup: look for s in hashtab */
struct nlist *lookup(char *s)
{
struct nlist *np;
for (np = hashtab[hash(s)]; np != NULL; np = np->next)
if (strcmp(s, np->name) == 0)
return np; /* found */
return NULL; /* not found */
}
char *strdup(char *);
/* install: put (name, defn) in hashtab */
struct nlist *install(char *name, char *defn)
{
struct nlist *np;
unsigned hashval;
if ((np = lookup(name)) == NULL) { /* not found */
np = (struct nlist *) malloc(sizeof(*np));
if (np == NULL || (np->name = strdup(name)) == NULL)
return NULL;
hashval = hash(name);
np->next = hashtab[hashval];
hashtab[hashval] = np;
} else /* already there */
free((void *) np->defn); /*free previous defn */
if ((np->defn = strdup(defn)) == NULL)
return NULL;
return np;
}
char *strdup(char *s) /* make a duplicate of s */
{
char *p;
p = (char *) malloc(strlen(s)+1); /* +1 for ’\0’ */
if (p != NULL)
strcpy(p, s);
return p;
}
Merk op dat als de hashes van twee strings botsen, dit kan leiden tot een O(n)opzoektijd. U kunt de kans op botsingen verkleinen door de waarde van HASHSIZEte verhogen. Raadpleeg het boek voor een volledige bespreking van de datastructuur.
Antwoord 2, autoriteit 18%
De snelstemanier zou zijn om een reeds bestaande implementatie te gebruiken, zoals uthash .
En als u echthet zelf wilt coderen, kunnen de algoritmen van uthashworden onderzocht en hergebruikt. Het heeft een BSD-licentie, dus afgezien van de vereiste om de copyrightmelding over te brengen, bent u vrijwel onbeperkt in wat u ermee kunt doen.
Antwoord 3, autoriteit 9%
Voor een gemakkelijke implementatie is het moeilijk te verslaan naïef zoeken door een array. Afgezien van wat foutcontrole, is dit een volledige implementatie (niet getest).
typedef struct dict_entry_s {
const char *key;
int value;
} dict_entry_s;
typedef struct dict_s {
int len;
int cap;
dict_entry_s *entry;
} dict_s, *dict_t;
int dict_find_index(dict_t dict, const char *key) {
for (int i = 0; i < dict->len; i++) {
if (!strcmp(dict->entry[i], key)) {
return i;
}
}
return -1;
}
int dict_find(dict_t dict, const char *key, int def) {
int idx = dict_find_index(dict, key);
return idx == -1 ? def : dict->entry[idx].value;
}
void dict_add(dict_t dict, const char *key, int value) {
int idx = dict_find_index(dict, key);
if (idx != -1) {
dict->entry[idx].value = value;
return;
}
if (dict->len == dict->cap) {
dict->cap *= 2;
dict->entry = realloc(dict->entry, dict->cap * sizeof(dict_entry_s));
}
dict->entry[dict->len].key = strdup(key);
dict->entry[dict->len].value = value;
dict->len++;
}
dict_t dict_new(void) {
dict_s proto = {0, 10, malloc(10 * sizeof(dict_entry_s))};
dict_t d = malloc(sizeof(dict_s));
*d = proto;
return d;
}
void dict_free(dict_t dict) {
for (int i = 0; i < dict->len; i++) {
free(dict->entry[i].key);
}
free(dict->entry);
free(dict);
}
Antwoord 4, autoriteit 2%
GLib en gnulib
Dit is waarschijnlijk uw beste keuze als u geen specifiekere vereisten heeft, aangezien ze algemeen verkrijgbaar, draagbaar en waarschijnlijk efficiënt zijn.
-
GLib: https://developer.gnome.org/glib/door GNOME-project. Verschillende containers gedocumenteerd op: https://developer.gnome.org/glib /stable/glib-data-types.htmlinclusief “Hash Tables” en “Balanced Binary Trees”. Licentie: LGPL
-
gnulib: https://www.gnu.org/software/gnulib/door het GNU-project. Het is de bedoeling dat u de broncode in uw code kopieert. Verschillende containers gedocumenteerd op: https://www.gnu.org/software/gnulib /MODULES.html#ansic_ext_containerinclusief “rbtree-list”, “linkedhash-list” en “rbtreehash-list”. GPL-licentie.
Zie ook: Zijn er openstaande bron C-bibliotheken met gemeenschappelijke gegevensstructuren?
Antwoord 5, autoriteit 2%
Het verbaast me dat niemand hsearch/hcreatenoemde verzameling bibliotheken die weliswaar niet beschikbaar is op Windows, maar door POSIX is verplicht en daarom beschikbaar is in Linux / GNU-systemen.
De link heeft een eenvoudig en compleet basisvoorbeeld dat het gebruik heel goed uitlegt.
Het heeft zelfs een draadveilige variant, is gebruiksvriendelijk en zeer performant.
Antwoord 6, autoriteit 2%
Maak een eenvoudige hash-functie en enkele gekoppelde lijsten met structuren, afhankelijk van de hash, wijs toe in welke gekoppelde lijst de waarde moet worden ingevoegd. Gebruik de hash ook om deze op te halen.
Ik heb enige tijd geleden een eenvoudige implementatie gedaan :
...
#define K 16 // ketencoëfficiënt
struct dict
{
teken * naam; /* naam van sleutel */
int-waarde; /* waarde */
struct dict *volgende; /* linkveld */
};
typedef struct dict dict;
dict *tabel[K];
int geïnitialiseerd = 0;
void putval ( char *,int);
ongeldig init_dict()
{
geïnitialiseerd = 1;
int ik;
for(i=0;iname = (char *) malloc (strlen(key_name)+1);
ptr->val = sval;
strcpy (ptr->naam,sleutelnaam);
ptr->next = (struct dict *)tabel[hsh];
tafel[hsh] = ptr;
}
int getval ( char *key_name )
{
int hsh = hash(sleutelnaam);
dict *ptr;
for (ptr = tabel[hsh]; ptr != (dict *) 0;
ptr = (dict *)ptr->volgende)
if (strcmp (ptr->naam,sleutelnaam) == 0)
retour ptr->val;
retourneer -1;
}
Antwoord 7
hier is een snel hulpmiddel, ik heb het gebruikt om een ‘Matrix'(sruct) van een string te krijgen.
je kunt ook een grotere array hebben en de waarden ervan wijzigen:
typedef struct { int** lines; int isDefined; }mat;
mat matA, matB, matC, matD, matE, matF;
/* an auxilary struct to be used in a dictionary */
typedef struct { char* str; mat *matrix; }stringToMat;
/* creating a 'dictionary' for a mat name to its mat. lower case only! */
stringToMat matCases [] =
{
{ "mat_a", &matA },
{ "mat_b", &matB },
{ "mat_c", &matC },
{ "mat_d", &matD },
{ "mat_e", &matE },
{ "mat_f", &matF },
};
mat* getMat(char * str)
{
stringToMat* pCase;
mat * selected = NULL;
if (str != NULL)
{
/* runing on the dictionary to get the mat selected */
for(pCase = matCases; pCase != matCases + sizeof(matCases) / sizeof(matCases[0]); pCase++ )
{
if(!strcmp( pCase->str, str))
selected = (pCase->matrix);
}
if (selected == NULL)
printf("%s is not a valid matrix name\n", str);
}
else
printf("expected matrix name, got NULL\n");
return selected;
}
Antwoord 8
Een hashtabel is de traditionele implementatie van een eenvoudig ‘woordenboek’. Als je niet om snelheid of grootte geeft, gewoon google ernaar. Er zijn veel vrij beschikbare implementaties.
hier is de eerste die ik zag— in één oogopslag, het lijkt me oké. (Het is vrij eenvoudig. Als je echt wilt dat het een onbeperkte hoeveelheid gegevens bevat, moet je wat logica toevoegen om het tabelgeheugen opnieuw te “localiseren” terwijl het groeit.)
veel succes!
Antwoord 9
Hashen is de sleutel. Ik denk dat je hiervoor een opzoektabel en een hash-sleutel gebruikt. Je kunt veel hash-functies online vinden.
Antwoord 10
De snelste methode is het gebruik van een binaire boom. Het slechtste geval is ook alleen O(logn).
Antwoord 11
Bovendien kunt u Google CityHash gebruiken:
#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>
#include <string.h>
#include <byteswap.h>
#include "city.h"
void swap(uint32* a, uint32* b) {
int temp = *a;
*a = *b;
*b = temp;
}
#define PERMUTE3(a, b, c) swap(&a, &b); swap(&a, &c);
// Magic numbers for 32-bit hashing. Copied from Murmur3.
static const uint32 c1 = 0xcc9e2d51;
static const uint32 c2 = 0x1b873593;
static uint32 UNALIGNED_LOAD32(const char *p) {
uint32 result;
memcpy(&result, p, sizeof(result));
return result;
}
static uint32 Fetch32(const char *p) {
return UNALIGNED_LOAD32(p);
}
// A 32-bit to 32-bit integer hash copied from Murmur3.
static uint32 fmix(uint32 h)
{
h ^= h >> 16;
h *= 0x85ebca6b;
h ^= h >> 13;
h *= 0xc2b2ae35;
h ^= h >> 16;
return h;
}
static uint32 Rotate32(uint32 val, int shift) {
// Avoid shifting by 32: doing so yields an undefined result.
return shift == 0 ? val : ((val >> shift) | (val << (32 - shift)));
}
static uint32 Mur(uint32 a, uint32 h) {
// Helper from Murmur3 for combining two 32-bit values.
a *= c1;
a = Rotate32(a, 17);
a *= c2;
h ^= a;
h = Rotate32(h, 19);
return h * 5 + 0xe6546b64;
}
static uint32 Hash32Len13to24(const char *s, size_t len) {
uint32 a = Fetch32(s - 4 + (len >> 1));
uint32 b = Fetch32(s + 4);
uint32 c = Fetch32(s + len - 8);
uint32 d = Fetch32(s + (len >> 1));
uint32 e = Fetch32(s);
uint32 f = Fetch32(s + len - 4);
uint32 h = len;
return fmix(Mur(f, Mur(e, Mur(d, Mur(c, Mur(b, Mur(a, h)))))));
}
static uint32 Hash32Len0to4(const char *s, size_t len) {
uint32 b = 0;
uint32 c = 9;
for (size_t i = 0; i < len; i++) {
signed char v = s[i];
b = b * c1 + v;
c ^= b;
}
return fmix(Mur(b, Mur(len, c)));
}
static uint32 Hash32Len5to12(const char *s, size_t len) {
uint32 a = len, b = len * 5, c = 9, d = b;
a += Fetch32(s);
b += Fetch32(s + len - 4);
c += Fetch32(s + ((len >> 1) & 4));
return fmix(Mur(c, Mur(b, Mur(a, d))));
}
uint32 CityHash32(const char *s, size_t len) {
if (len <= 24) {
return len <= 12 ?
(len <= 4 ? Hash32Len0to4(s, len) : Hash32Len5to12(s, len)) :
Hash32Len13to24(s, len);
}
// len > 24
uint32 h = len, g = c1 * len, f = g;
uint32 a0 = Rotate32(Fetch32(s + len - 4) * c1, 17) * c2;
uint32 a1 = Rotate32(Fetch32(s + len - 8) * c1, 17) * c2;
uint32 a2 = Rotate32(Fetch32(s + len - 16) * c1, 17) * c2;
uint32 a3 = Rotate32(Fetch32(s + len - 12) * c1, 17) * c2;
uint32 a4 = Rotate32(Fetch32(s + len - 20) * c1, 17) * c2;
h ^= a0;
h = Rotate32(h, 19);
h = h * 5 + 0xe6546b64;
h ^= a2;
h = Rotate32(h, 19);
h = h * 5 + 0xe6546b64;
g ^= a1;
g = Rotate32(g, 19);
g = g * 5 + 0xe6546b64;
g ^= a3;
g = Rotate32(g, 19);
g = g * 5 + 0xe6546b64;
f += a4;
f = Rotate32(f, 19);
f = f * 5 + 0xe6546b64;
size_t iters = (len - 1) / 20;
do {
uint32 a0 = Rotate32(Fetch32(s) * c1, 17) * c2;
uint32 a1 = Fetch32(s + 4);
uint32 a2 = Rotate32(Fetch32(s + 8) * c1, 17) * c2;
uint32 a3 = Rotate32(Fetch32(s + 12) * c1, 17) * c2;
uint32 a4 = Fetch32(s + 16);
h ^= a0;
h = Rotate32(h, 18);
h = h * 5 + 0xe6546b64;
f += a1;
f = Rotate32(f, 19);
f = f * c1;
g += a2;
g = Rotate32(g, 18);
g = g * 5 + 0xe6546b64;
h ^= a3 + a1;
h = Rotate32(h, 19);
h = h * 5 + 0xe6546b64;
g ^= a4;
g = bswap_32(g) * 5;
h += a4 * 5;
h = bswap_32(h);
f += a0;
PERMUTE3(f, h, g);
s += 20;
} while (--iters != 0);
g = Rotate32(g, 11) * c1;
g = Rotate32(g, 17) * c1;
f = Rotate32(f, 11) * c1;
f = Rotate32(f, 17) * c1;
h = Rotate32(h + g, 19);
h = h * 5 + 0xe6546b64;
h = Rotate32(h, 17) * c1;
h = Rotate32(h + f, 19);
h = h * 5 + 0xe6546b64;
h = Rotate32(h, 17) * c1;
return h;
}