@ Gene : I think your remove() function takes O(n) time in case if all n numbers hash to same bucket.
Could you please elaborate on unbiased_hash() function? Can't we do it like this : rand() % TABLE_SIZE coz rand() generates uniformly distribution of numbers. On Fri, Nov 4, 2011 at 1:47 AM, Gene <[email protected]> wrote: > Often you can get optimal performance with unusual combinations of > operations by combining data structures. Here you can get O(1) for all > operations by combining a hash table and a bag of pointers in an > array. The hash table references bag elements by index, and the bag > elements point back at hash table entries. Random lookups occur in > the bag array. Here is a quick C toy to show what I mean. There are > other possible implementations. > > #include <stdio.h> > #include <stdlib.h> > > typedef struct key_pair_s { > struct key_pair_s *next; > unsigned value, bag_index; > } KEY_PAIR; > > typedef struct table_s { > KEY_PAIR *buckets[1007], *bag[10000]; > unsigned size; > } TABLE; > > #define ARRAY_SIZE(A) (sizeof A/sizeof *A) > > void init_table(TABLE *table) > { > unsigned i; > for (i = 0; i < ARRAY_SIZE(table->buckets); i++) > table->buckets[i] = NULL; > table->size = 0; > } > > unsigned hash(unsigned key) > { > return key % ARRAY_SIZE(((TABLE*)42)->buckets); > } > > int Remove(TABLE *table, int value) > { > KEY_PAIR *p, *q; > unsigned h = hash(value); > for (q = NULL, p = table->buckets[h]; p; q = p, p = p->next) > if (p->value == value) { > if (q) > q->next = p->next; > else > table->buckets[h] = p->next; > // Move last element into hole in bag. Update hash table. > q = table->bag[--table->size]; > table->bag[p->bag_index] = q; > q->bag_index = p->bag_index; > free(p); > return 1; > } > return 0; > } > > void Insert(TABLE *table, int value) > { > // Put a new key pair in the hash table. > KEY_PAIR *p = malloc(sizeof *p); > unsigned h = hash(value); > p->next = table->buckets[h]; > table->buckets[h] = p; > p->value = value; > > // Allocate a new bag element for this pair. > p->bag_index = table->size++; > table->bag[p->bag_index] = p; > } > > #define N_RAND (RAND_MAX + 1) > > unsigned unbiased_rand(unsigned n) > { > unsigned r, m = N_RAND - N_RAND % n; > do r = rand(); while (r >= m); > return r % n; > } > > void GetRandomElement(TABLE *table, unsigned *value) > { > if (table->size > 0) > *value = table->bag[unbiased_rand(table->size)]->value; > } > > void Print(TABLE *table) > { > unsigned i; > > printf("table:"); > for (i = 0; i < table->size; i++) > printf(" %u", table->bag[i]->value); > printf("\n"); > } > > int main(void) > { > TABLE table[1]; > unsigned i, values[10]; > char cmd; > > init_table(table); > for (i = 0; i < ARRAY_SIZE(values); i++) { > values[i] = rand(); > Insert(table, values[i]); > } > > for (;;) { > Print(table); > printf("cmd [arg]> "); > scanf(" %c", &cmd); > switch(cmd) { > case 'i': > scanf("%u", &i); > Insert(table, i); > printf("Inserted %u\n", i); > break; > case 'r': > scanf("%u", &i); > if (Remove(table, i)) > printf("Removed %u\n", i); > else > printf("Couldn't find %u\n", i); > break; > case 'g': > i = 0; > GetRandomElement(table, &i); > printf("Random element: %u\n", i); > break; > case 'q': > return 0; > default: > printf("Unknown command\n"); > break; > } > } > } > > On Nov 2, 4:52 pm, shady <[email protected]> wrote: > > does anyone knows how much is the complexity of operations erase and > > pop_back in case of Vector(STL) > > what would you choose : > > > > Design a data structure where the following 3 functions are optimised: > > > > 1. Insert(n) > > 2. GetRandomElement() > > 3. Remove(n) > > > > Write a class, and implement the functions. Give complexity of each of > these > > > > what would you choose, insertion can always be done in O(1), but what > about > > getrandomelement().... if we use simple arrays than for those > > > > 1. -> O(1) > > > > 2. -> O(1) > > > > 3. -> O(n) > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Mohit -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
